Multi-dimensional tic tac toe

[pkdvalis]

Hi, I’ve been working on a 3d tic tac toe, which I expanded a bit into multi-dimensional (2D + 3 different board sizes, 3x3, 4x4 and 5x5x5 for example)

So you can make 3 in a row vertically as well.

I’ve implemented the minimax algorithm with alpha beta pruning for the computer AI, but it gets too slow at higher dimensions (4x4x4). Here is the live game and code:

https://3-dads-tactical-tuba-time.vercel.app/

https://github.com/pkdvalis/3-Dads-Tactical-Tuba-Time

Enable minimax with “Medium” or “Hard” difficulty. I use a fallback algorithm on 4x4x4 board and 5x5x5 which is faster. You can confirm if minimax is running in the console it should say “Running minimax depth 5”

Questions for feedback:

1. Is there a better or faster algorithm I could use?
   Pruning improved performance a lot, 3x3x3 is now playable where it used to take 3 minutes to pick the first move. 4x4x4 still takes 1 minute to make it’s first move. Controlling the maximum depth helps but it’s either too slow, or the moves are too bad.

2. When the player moves, it waits until the computer has made it’s move before rendering both moves. How could I render the player move first before the computer is thinking? More noticeable on 3x3x3 (on Medium or Hard difficulty)

Any other advice for improvement or how to organize my code is greatly appreciated. There might also be bugs I haven’t seen yet.

I noticed in this tutorial that more things seem to be rolled into objects which might make more readable code and I can pass an object as a prop instead of 50 variables, I might try this first.

JavaScript Tic Tac Toe Project Tutorial - Unbeatable AI w/ Minimax Algorithm

[Stabat]

Do you have a pen version of it? codepen loads faster. I have been having difficulties opening vercel and github. don’t know if it is network problem from my end but all works well. Anyway, I’ll keep trying and you’ll have my review once it opens

[pkdvalis]

Wow, that’s a bummer. I would imagine it’s something on your end. Those are pretty big sites, especially github of course.

The code has been broken up into many jsx files now, so I wouldn’t be able to put it on codepen.

I was able to load it into stackblitz:

Live app:
https://3dadstacticaltubatime-lo4n–5173–96435430.local-corp.webcontainer.io/

Code:
https://stackblitz.com/~/github.com/pkdvalis/3-Dads-Tactical-Tuba-Time

[Stabat]

I love the 3D dimension stuff. The sound too is really cool to play with.

I noticed a few problems.

On easy level on the 3's board, 2D and 3D, there is no computer move

When I play easy, I am the only one to make moves.

but for some reasons computer moves appear If I use the blockcenter option.

Not rendering properly in 3D mode

The 4 and 5 boards do not display all at once on my screen

No ending message on tie

If the game ends in a tie, it still shows X’s turn. there is no rule for tie

Why block the Center move?

blocking the center spot with an X gives an illusion to the player given he uses X. and it greatly reduces the probability of wining in the 2d mode in 3x3. given only 8 boxes are left to play

It looks like a straight line win but the middle is blocked.

Changing game options during game play

while playing, I can change game difficulty. I don’t know how that affects AI but I believe it is not proper. Again, I switch the board from 2D to 3D and back while playing even if the game is not complete. This option restarts the game on new board.

Difference between Medium and Hard

I don’t get to see much difference while playing Medium or hard on how AI moves.

and for the 2D board, maybe it should be 2D because it actually looks like 3D. the difference with 3D are just the extra layers which is cool for some complex tic tac toe gaming. I love that idea.

I believe there is still much to adjust. Why not start with these and let me know so we can move forward?

[pkdvalis]

Yes, it is a little buggy like this currently. Most of these can be solved by pressing “Reset” before you play. If you change the board dimensions a lot there is something not updating but if you press “Reset” it should be ready.

For example if you check “block center” you need to press “Reset” and it will be blocked with “Esc”.

It’s something with the way I’m rendering with React that I haven’t solved perfectly.

@Stabat

On easy level on the 3’s board, 2D and 3D, there is no computer move

This as well, try pressing “Reset” before you play.

Tie I haven’t implemented yet. It seems obvious when the tie occurs and the only thing to do is press Reset so it’s not a high priority.

@Stabat

I don’t get to see much difference while playing Medium or hard on how AI moves.

This is also something I haven’t quite worked out yet. I do have a few different algos but I haven’t quite worked out how to balance them yet. In theory you could give minimax different depths but it’s often only too easy or too slow.

Most of of the problems I’ve had are struggling with React and understanding rendering! It was good to learn React better but I know it would work better if I had written in vanilla JS…

@Stabat

and for the 2D board, maybe it should be 2D because it actually looks like 3D.

Hm, that is interesting. I might try this. The idea is that a 2D board is just one slice of the 3D board though, one layer.

I came very close to giving it a fourth dimension as well, I realized that the difference is just another field in the array [x,y], [x,y,z] and 4D would be [w,x,y,z]. It was too much to refactor at that point though. I still want to try that next. The code to check for a win will become huge.

It can help if you press f11 to fit the 5x5 board on the screen. You’re right though, it would be better if I can shrink it to fit…

On a smaller mobile screen some options are disabled because of this.

Thanks for your feedback! Good reminder of what still needs to be done.

[pkdvalis]

Oh, check this out, I found a tic tac toe game rendered on a rubik’s cube while I was researching:

https://simulatedgrowth.itch.io/cube-tac-toe

You can rotate the cube during the game, how crazy is that?

I was surprised how deep and how many varieties of tic tac toe there is while researching to make the game.

[Stabat]

Wow. With programming, I guess your imagination is your limit. I never even thought tic tac toe could be played in your 3D and now cube?. I am amazed.

[Zerazera]

Vite favicon – is this deliberate?

xMoves.jsx and oMoves.jsx are identical

Unnecessary useEffects – should track changes in size/dimension instead, or wrap setSize/setDimension with changes

Highlighting – Consider using state instead of directly modifying DOM

setGrid(App.jsx line 84) – Avoid directly modifying the state variable – create a copy instead

Reset game should also reset highlighting

Consider more semantic html tags (main, header, footer, etc.) p#title should be an h1

computerMove.jsx – blockxn1 isn’t called anywhere

Minimax – if (score === 10 || score === -10) OR if(Math.abs(score) === 10)

if(!isMovesLeft(board, size, levels)) instead of if(isMovesLeft(board, size, levels) === false)

Minmax – no use of depth? (A win sooner is worth more than a win later)

Consider using negamax instead of minimax (same result, more concise, easier to reason about)

Resizing the screen, clicking options and then resizing it again – end up with two different sets of options on the screen

3 x 3 x 3 hard – easy win along the center squares

1. Minimax is going to suffer when the problem space grows because of exponential growth of board states, and it is a brute force algorithm. Possible enhancements include transposition tables to prune already explored depths, and optimizing move order to prune faster. You could also look into writing a more strategic solver instead of minimax (Wikipedia has a strategy you can look at for this).

2. I believe this occurs because React is batching all of the state changes inside of your handleClick before rerendering. The answer is to decouple the computer move from your handleClick. You could, for example, watch for changes in grid state and then put your computer move logic in that block. Then it would be handleClick → rerender → computer move → rerender.