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)
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.
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?!
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)
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?!
This is because you placed a piece in a spot that already has a piece, I forgot to check for that in my code
If you run 2 instances playing against each other one of them is going to loose. So, is not unbeatable. ¯\(ツ)/¯
Are you sure? Are not they going to play forever?
Wouldn't they just tie every time