Printable View
I am interested in making a tic-tac-toe game only I want to possible make it using a 4x4 or larger board. I want to try and make it 1 player. I understand the concept of minimax trees but I was wondering how you go about making a tree that large because in a tree for a 4x4 board there's over 2.0x10^13 possible outcomes.
A few things to consider..
I don't really know what you mean by 1 player tic tac toe. I assume you just mean that is the style of the input, and that it's actually X and O playing against each other.
If you just want to do the 4x4 case, you can "psuedo bruteforce" it with memoization, there are only really 3^16 states before even reducing for symettry. It's a lot like this problem http://www.algorithmist.com/index.php/UVa_10838
On the other hand, not that I really understand mini-max trees, but the idea is that
A) you explore the tree, not store it.
B) you prune off parts of the search tree by estimating that certain parts of the search space are not good places to look, as they won't lead to a good solution.