DEV Community

Jaeheon Shim
Jaeheon Shim

Posted on

I wrote an unbeatable Tic-Tac-Toe AI in Java

I just wrote a Java program that cannot lose at a game of Tic-Tac-Toe. Your best hope is to tie it in a game.
You can find the full code here: github.com

It works by using the minimax algorithm. I'll be writing an article about this on my personal blog soon.

I would appreciate it very much if you could take a peek at the code and tell me what you think. Any feedback would be very much appreciated!

Top comments (8)

Collapse
 
nestedsoftware profile image
Nested Software • Edited

The basic idea seems to be correct (though I have not run the code).

I'm not very fond of initializing the values to +100/-100. Instead, I'd recommend extracting the logic to a function that returns the correct value.

I'd also suggest removing the boolean parameter that determines whether you are doing min or max: You can derive this from whose turn it is, which is known from the board position alone.

The logic that computes the value of a move depending on whether we are doing min or max can be combined together (note how it's almost the same in each case): You can extract this logic into a min or max strategy that will return either the minimum or the maximum, and that way you can combine all the rest of the code together.

Beyond that, for testing, I think it would be good to run this code both as X and as O against itself and against an opponent that plays random legal moves. Then you can calculate the statistics of the results for each of the cases.

Also, I think it would be interesting to time this code to see how long it takes it to play a game. It looks as though it is currently doing a recursive computation for each move, so there will be a lot of the same positions being re-evaluated over and over again. I'm not sure how slow that would make this code in Java, but it would be interesting to find out.

Note: Make sure to be aware of the code of conduct. You can post a full article here about your project, and also provide a link to the same article on your personal blog. However, you shouldn't post an article that's basically just a straight up link without meaningful content of its own.

Collapse
 
bsagortest profile image
bsagortest

2 | |


1 | |


0 | |
0 1 2

Enter position (x, y): 1,2
2 |O|


1 | |


0 | |
0 1 2

AI is playing...
2 X|O|


1 | |


0 | |
0 1 2

Enter position (x, y): 1,1
2 X|O|


1 |O|


0 | |
0 1 2

AI is playing...
2 X|O|


1 |O|


0 |X|
0 1 2

Enter position (x, y): 0,0
2 X|O|


1 |O|


0 O|X|
0 1 2

AI is playing...
2 X|O|X


1 |O|


0 O|X|
0 1 2

Enter position (x, y): 1,0
2 X|O|X


1 |O|


0 O|O|
0 1 2

=======================
Game Finished!
2 X|O|X


1 |O|


0 O|O|
0 1 2

YOU WON?!

Collapse
 
jaeheonshim profile image
Jaeheon Shim

Oh yeah, so... I forgot to make it check to see if you're placing your piece in a spot that is already filled (facepalm)

Collapse
 
suchitrakartic profile image
suchitrakarthik

2 | |


1 | |


0 | |
0 1 2

Enter position (x, y): 1,1
2 | |


1 |O|


0 | |
0 1 2

AI is playing...
2 X| |


1 |O|


0 | |
0 1 2

Enter position (x, y): 0,2
2 O| |


1 |O|


0 | |
0 1 2

AI is playing...
2 O|X|


1 |O|


0 | |
0 1 2

Enter position (x, y): 2,0
2 O|X|


1 |O|


0 | |O
0 1 2

=======================
Game Finished!
2 O|X|


1 |O|


0 | |O
0 1 2

YOU WON?!

Collapse
 
jaeheonshim profile image
Jaeheon Shim

This is because you placed a piece in a spot that already has a piece, I forgot to check for that in my code

Collapse
 
juankruiz profile image
Juan Carlos Ruiz Pacheco

If you run 2 instances playing against each other one of them is going to loose. So, is not unbeatable. ¯\(ツ)

Collapse
 
diek profile image
diek

Are you sure? Are not they going to play forever?

Collapse
 
jaeheonshim profile image
Jaeheon Shim

Wouldn't they just tie every time