0
$\begingroup$

I was reading online that Tic Tac Toe has a state space of 3^9 = 19,683. From my basic understanding, this sounds too large to use with Q Learning, as the Q table would be huge?

If that is the case, can you suggest other (non-NN) algorithms I could use to create a TTT bot to play against a human player?

| improve this question | |
$\endgroup$
0
$\begingroup$

In the case of TicTacToe, you can make use of game theory. The entire search space can be denoted by a game tree. You bot must now be able to maximize the chance of winning.

You can make use of the Maximin algorithm. This is still computationally intensive on large search spaces. To improve the efficiency Alpha-Beta pruning can be applied to reduce the number of nodes in the Game tree.

These are core AI concepts and will always perform better than neural networks on dully defined and relatively smaller search spaces. Neural networks perform better when it's too difficult to compute all the possible combinations of a game at a certain state.

You can have a look at this to build a TicTacToe bot.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Would you also suggest the Maximin algorithm for games with even larger state space; for example, Chess? $\endgroup$ – mason7663 Mar 30 at 8:36
  • 1
    $\begingroup$ No. The Miaximin algorithm requires the entire search space to be properly defined. Incase of chess this is not possible as there are too many possibilities. This is also due to the fact that the different pieces follow different movement rules. This is the main reason why developing chess agents is very challenging. $\endgroup$ – skillsmuggler Mar 30 at 9:10
  • 1
    $\begingroup$ In the case of chess, yes the search space is too large. Both in terms of space complexity and time complexity. Have a look at this should give you an idea of the complexity of the task. $\endgroup$ – skillsmuggler Mar 30 at 11:55
  • 1
    $\begingroup$ For connect 4, you can consider it to be a relatively small search space. This again depends on the computing resources. For connect 4 you can make use of Minimax. $\endgroup$ – skillsmuggler Mar 30 at 11:57
  • 1
    $\begingroup$ It's an algorithm. In theory it can be used for all 0/1 games. The threshold is determined by your computing resources. A larger state space requires more resources. If you have them available, you can make use of Minimax. In case of chess, even super computers do not have enough computing power to implement Minimax. $\endgroup$ – skillsmuggler Apr 2 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.