Tic-Tac-Toe banner

Tic-Tac-Toe

Created by: Nawab-AS
3 devlogs
6h 52m 8s

A simple tic-tac-toe game using the min-max algorithm for AI

Demo Repository

README

Loading README...
Nawab-AS
Nawab-AS shipped Tic-Tac-Toe
about 7 hours ago

Shipped this project!

I created a simple Tic-Tac-Toe game with an AI

I know it seems simple, but in actuality, its quite beautifully complex.

The basis of the project is a Tic-Tac-Toe game with an AI (easy, medium, and hard), and a resizable board (3x3 to 6x6).

The complexity of this project comes from the AI, which uses the minimax algorithm. Normally, on a 3x3 board, this wouldn’t be much of a hassle, however the complexity grows as the number of spaces grow exponentially.

While the minimax algorithm is quite fast, making it solve a 6x6 board allows for (6*6)! possibilities (approximately 3.7 followed by 40 zeros). As a result of this, I had to implement some limitations that allow for moves to happen in >1.5s, but the cost of intelligence (hence, no ‘impossible’ difficulty), until then, the ‘hard’ bot can fail to even see immediate losing moves.

  1. Alpha-Beta Pruning. Basically, instead of solving every possibility, it stops whenever a possibility branch contains an un-optimal position (losing position), perfering optimal routes.

  2. General Tendency of the center. I mean, ig that’s where most of the stuff happen for boards >3x3.

  3. A time limit. Kinda self-explanatory, really bad for ‘smartness’.

Overall, I think I really understood a lot about how different game AIs work. One thing I really found interesting while making this project is the calculus, which I found quite elegant for its purpose.

Nawab-AS
Nawab-AS worked on Tic-Tac-Toe
1 day ago
2h 45m logged

I added the ability to change the size of the board, upto 6x6. This came with many complications due to the amount of computation required to calculate all results. I won’t go into all the details but basically, the fewer moves that are already on the board, the more number of total ‘routes’ that can occur, such that on the first move, the computer has to calculate (6*6 - 1)! (arround 1, followed by 40 zeros) combinations.

I managed to optimize the algorithm with alpha-beta pruning, a time limit for 1.5s per move, and a general preferance of the center. This comes with the cost of an ‘impossible’ hardness being infeasible in the browser, atleast without some WebAssembly, somthing I don’t want to do as of right now. Because of this, the effectiveness of the hardness setting will vary greatly depending on your CPU’s strength (or more specifically, the single thread speed). Until then, the hard setting will fail to block immediate winning moves on larger boards.

Anyways, thats enough yapping. Enjoy!

0
Nawab-AS
Nawab-AS worked on Tic-Tac-Toe
4 days ago
2h 49m logged

After a lot of debugging I managed to push a few new features:

  1. Dynamic SVG win animations. A dash showing the winning combination along with enlargening of the letters.
  2. The tic-tac-toe AI. Took a while to read the wikipedia and implement (ngl, now that I know calculus, the math is genuienly interesting. you should read it some time). Available in 3 modes: easy, medium, and hard.

Future improvements:

  • Better CSS
  • Cooler win effects
0
Nawab-AS
Nawab-AS worked on Tic-Tac-Toe
4 days ago
1h 17m logged

I created a simple and minimalistic tic-tac-toe game template. I initally created this with vanilla JS but after state managent complications, I changed to Vue (via CDN). During this time, I didn’t use any AI (yes, this includes css).

Features:

  • Simple interactive interface
  • Reactive ‘action’ button

To be implemented:

  • The actual AI part
  • Better CSS
  • Effects after winning, maybe?
Attachment
0