Tic-tac-toe - slow minimax

1

Hi,

I have finally completed my tic-tac-toe using react-redux.

For the hard difficulty setting I try to do something like the minimax algorithm.

What I do first, is create a tree with all possible combinations of game boards, and then just move along the tree while the game progresses.
The only issue I have is that it can be a bit slow when generating the tree. This is especially a problem for users in mobile devices. And, we all know how nowadays everyone is super impatient :stuck_out_tongue:

Do you have any suggestions of alternative approaches which could help speed up the load time?

The live app is here: https://zelite.github.io/tic-tac-toe/

Here is the code to create the tree of all boards: https://github.com/zelite/tic-tac-toe/blob/master/src/tree.js

And here are the functions which do most of the work on boards: https://github.com/zelite/tic-tac-toe/blob/master/src/board.js (checking empty cells, adding symbols and so on).

1 Like
2

I don’t know much about the min-max algorithm but, based on a quick read on Wiki, have you considered not generating the entire tree to begin with?

Alternatively, would it be possible to use symmetry to minimise the number of boards generated? For example, there are really only three unique moves in the first turn, two or five unique moves in the second turn… etc.

I didn’t know anything about min-max algorithms at the time I did this project but I think the approach I may be more efficient than the min-max algorithm because certain scenarios basically mean that there is only one move if the AI is not to lose. What I did was to prioritise moves like this:

1. In the first two turns, take the grid in the center if it’s not already taken—this grid has the highest degree of freedom, hence the potential to win
2. Place a winning move if possible
3. Block a player’s winning move if there is one
4. Always try to force the player to defend by creating a potentially winning move—one has to make sure that doing so doesn’t force the player to place a marker in a grid that will lead to an certain win for the player

I hope that helps. :slight_smile:

1 Like
3

Do you have any suggestions of alternative approaches which could help speed up the load time?

The most consuming task for the Minimax is looking through the number of possibilities.
And the simplest solution to greatly minimise this task overload is by reducing those possibilities:

  • You may create a small function for a performance boost in which it makes the first move only for the AI from a list of “best” possible initial moves. (You could find those moves by using your AI)

  • You could, for example, use some sort of a “helping” search algorithm like the alpha-beta.

  • Also, ensure you calculate valid board states only not all 3^9 board states.

    Note: This can be done by breaking out from your loop early or setting a base case inside your recursion when certain conditions are met.

Goodluck.

2 Likes