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!

Oldest 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
 
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

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