Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

How to calculate number of nodes

 
Ashish Schottky
Ranch Hand
Posts: 93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 6081
71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 6081
71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 6081
71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Then obviously your evaluation method isn't working properly. What code are you using?
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic