3
$\begingroup$

I have implemented a 3d Tic Tac Toe game with AI, where the computer is unbeatable.

The only thing is that the board looks like this:

_ _ _
 _ _
_ _ _

rather than this:

_ _ _
_ _ _
_ _ _

There are a total of 3 boards stacked on top of each other, and any lines of 3 x's or o's grant a point. When the board is full, all points are tallied and the winner is announced.

I used the minimax algorithm with alpha-beta pruning.

But my algorithm is only able to get the optimal move if the board is full to a certain degree. When there are less moves, it takes a really, really long time to find the optimal move.

Is there some way to speed up my minimax? I have already researched ways to speed up minimax, but I need an answer specifically related to my situation.

Is it possible to solve to optimal move quickly using minimax? Or do I have to use a different algorithm?

EDIT: Please note that the game uses gravity, like in the connect-four game. I.e. the x's and y's stack.

$\endgroup$
  • $\begingroup$ You can try to establish a maximum depth of search so that the computer doesn´t look beyond a certain point $\endgroup$ – rotia Nov 21 '16 at 20:59
  • $\begingroup$ I've tried that, any depth greater than 6 takes a long time, but a depth of 6 does not give an optimal move, and it is possible to win. $\endgroup$ – Wizard Nov 21 '16 at 21:00
  • 1
    $\begingroup$ So you do not have a winner only points count? Do you take symmetric solutions as the same? Did you tried creating opening moves book? $\endgroup$ – Evil Nov 21 '16 at 21:11
  • $\begingroup$ Well, I have the opening move set. An idea I had was to only check for moves on the first level if there are no moves yet on levels 2 and 3. But if the player makes a move onto those levels early, then this idea is pretty much null and void. $\endgroup$ – Wizard Nov 21 '16 at 21:18
1
$\begingroup$

You could precompute the optimal move for all possible configurations, and store that in a lookup table. Once that's done (and it only needs to be done once), it would make your program extremely fast at runtime.

Your board has a total of 24 cells (8 cells at each level, times 3 levels), so there are at most a total of $3^{24}$ possible calculations. Therefore, as a naive upper bound, your table will need to have at most $3^{24}$ entries.

In fact, due to gravity plus the fact that you don't need to store configurations where one player has already won, there will be many fewer configurations that you need to store in your table. Call a configuration relevant if no one has won yet, and it is a reachable configuration (i.e., it doesn't violate the gravity rules). Then your table can be stored as a dictionary/map: for each relevant configuration, it stores the optimal move when in that configuration and which player will win assuming optimal play (first-player win, second-player win, tie). Now your job is to precompute that dictionary, with one element per relevant configuration.

It is possible to show that the number of relevant configurations is at most $13^8 \approx 2^{29.6}$: in particular, the number of configurations that satisfies gravity and has no vertical win is $13^8$. This is only an upper bound; the true number of relevant configurations is even smaller still, as this estimate doesn't take into account that there's no need to store any configuration containing a horizontal or diagonal win.

To speed up the precomputation, you can avoid repeating effort (i.e., use "dynamic programming"). For instance, one approach would be to start by enumerating all relevant configurations containing 23 full cells and compute the optimal move for each; then enumerate all relevant configurations containing 22 full cells and compute the optimal move for each; and so on. At each stage, when you compute the optimal move, you add it to the table along with who ultimately wins. Notice that this makes it very easy to compute the optimal move at each stage, since you only need to search at depth 1 and then you can immediately look up what will happen thereafter in the table.

The running time of the precomputation will be some small constant times $N$, where $N$ is the number of relevant configurations. We know that $N$ is smaller than $2^{29.6}$, and probably substantially smaller. Therefore, I expect this precomputation to be something you could run within a few days on a modern PC, and store on the filesystem in a reasonable amount of space.

As a further optimization, you can use symmetry to further reduce the number of configurations you need to compute or store. In particular, given any configuration, you can find a bunch of other equivalent configurations through symmetry (flip horizontally, flip vertically, rotate). For each set of equivalent configurations, you only need to consider and store one. In particular, given a configuration, the first thing you'd do is map it to a canonical equivalent configuration (so that all equivalent configurations map to the same canonical); then you only need to compute or store canonical configurations in the lookup table. I suspect this will reduce $N$ by a factor of 8 or so.

$\endgroup$

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.