| Author |
How to calculate number of nodes
|
Ashish Schottky
Ranch Hand
Joined: Dec 29, 2009
Posts: 93
|
|
I have programmed tic-tac-toe using min-max algorithm.
In min max the number of nodes traversed is W^d where W is the number of leaves at particular depth d.
Thus for my program d=9 on empty board playing first.
I placed a variable called as 'nodes' in evaluation method.
and then incremented it every time using node++.
then the final number I got from computer was 549945. So I got W as 4.343 .
Is my result correct?
|
 |
Stephan van Hulst
Bartender
Joined: Sep 20, 2010
Posts: 2771
|
|
Actually, W would be 9 on an empty board, since at d = 1, you have 9 nodes. (Actually, you only have three because you only have to check the center, a corner, and an edge).
The result you get from simply counting nodes is completely dependent on how "naïve" your scheme is.
What is it you're trying to figure out?
|
 |
Ashish Schottky
Ranch Hand
Joined: Dec 29, 2009
Posts: 93
|
|
Thanks for taking interest in my query.
I am trying to findout the total number of legal positions that a regular board of tictactoe can have(Right now I am not counting on reduction due to symmetries and reflections).
Just total number of legal moves for an empty board of tictactoe till its end.
|
 |
Stephan van Hulst
Bartender
Joined: Sep 20, 2010
Posts: 2771
|
|
So what's wrong with traversing the nodes recursively and counting the nodes like you do?
You can make a very simple formula that calculates all the permutations of the board, but determining how many of those are legal is going to be hard without recursion.
|
 |
Ashish Schottky
Ranch Hand
Joined: Dec 29, 2009
Posts: 93
|
|
Thanks again.
Actually I am confused with the fact that only 9! legal positions are allowed in tictactoe
(upper bound).
But then the searched nodes are far too more than 9!(326880)
|
 |
Stephan van Hulst
Bartender
Joined: Sep 20, 2010
Posts: 2771
|
|
|
Then obviously your evaluation method isn't working properly. What code are you using?
|
 |
 |
|
|
subject: How to calculate number of nodes
|
|
|