Problem Definition
1. Learn what is a tic-tac-toe game and how to win it.
2. Implement minimax or alpha-beta pruning for a tic-tac-toe game AI to break the 4x4x4 game.
3. Compete with AI implemented from other and win a tournament with extra credits!
Method and Implementation
1. Minimax algorithm:
For designed AI algorithm implemented in the tic-tac-toe game, the minimax algorithm with alpha-beta pruning method is used to let AI try to win the game efficiently. Here is the pseudo-code for minimax methodology:
2. Heuristic value calculation:
heuristic value for each node can be defined as
The number of possible counter players winning lines minus the number of possible counter players winning lines.
Here is the pseudo-code for heuristic methodology:
Experiments
In order to show the effectiveness of our AI system. We designed 4 different experiments:
1. AI system with depth equals to 3 vs Random system.
2. AI system with depth equals to 3 vs AI system with depth equals to 1
3. AI system with depth equals to 3 vs AI system with depth equals to 2
4. AI system with depth equals to 3 vs AI system with depth equals to 3
Each experiment run 100 times. We also calculate average time of each steps of AI thinking.
Results
The experiment results table.
| Winning Rate | Draw Rate | Losing Rate | Player 1 Step Running time | Player 2 Step Running time | Player 1 Total Running time | Player 2 Total Running time | |
| Depth3_AI VS Random | 100% | 0% | 0% | 0.204s | 0.204s | 1.948s | 1.949s |
| Depth3_AI VS Depth1_AI | 98% | 2% | 0% | 0.139s | 0.142s | 1.606s | 1.553s |
| Depth3_AI VS Depth2_AI | 9% | 89% | 2% | 0.079s | 0.079s | 2.303s | 2.301s |
| Depth3_AI VS Depth3_AI | 2% | 93% | 5% | 0.116s | 0.116s | 3.476s | 3.476s |
Here are some examples of processes.
| Depth3_AI VS Random | Depth3_AI VS Depth1_AI | Depth3_AI VS Depth2_AI | Depth3_AI VS Depth3_AI |
| Depth3_AI Wins | Depth3_AI Wins | Draw | Draw |
|
num:64 player1:0,0,3 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [____] [____] [____] level(z) 3 [X___] [____] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [____] [____] [____] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ num:62 player1:0,0,0 level(z) 0 [X___] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [____] [____] [____] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [____] [____] [___O] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ num:60 player1:2,1,1 level(z) 0 [X___] [____] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [____] [____] [___O] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [__O_] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [____] [____] [___O] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ num:58 player1:2,1,2 level(z) 0 [X___] [__O_] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [____] [_X__] [___O] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [____] [_X__] [___O] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ num:56 player1:3,3,0 level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [____] [_X__] [___O] level(z) 3 [X__O] [____] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [____] [_X__] [___O] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ num:54 player1:1,2,1 level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [____] level(z) 2 [____] [____] [_X__] [___O] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [____] level(z) 2 [____] [____] [_X__] [O__O] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ num:52 player1:1,2,2 level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [____] level(z) 2 [____] [__X_] [_X__] [O__O] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [____] level(z) 2 [____] [__X_] [_X__] [OO_O] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ num:50 player1:3,2,2 level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [____] level(z) 2 [____] [__X_] [_X__] [OOXO] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [___O] level(z) 2 [____] [__X_] [_X__] [OOXO] level(z) 3 [X__O] [___O] [____] [____] ++++++++++++++++++++++++++++ num:48 player1:1,1,3 level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [___O] level(z) 2 [____] [__X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [___O] level(z) 2 [____] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [____] [____] ++++++++++++++++++++++++++++ num:46 player1:0,3,2 level(z) 0 [X___] [O_O_] [____] [___X] level(z) 1 [____] [__X_] [_X__] [___O] level(z) 2 [___X] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [___O] [___X] level(z) 1 [____] [__X_] [_X__] [___O] level(z) 2 [___X] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [____] [____] ++++++++++++++++++++++++++++ num:44 player1:2,1,0 level(z) 0 [X___] [O_O_] [_X_O] [___X] level(z) 1 [____] [__X_] [_X__] [___O] level(z) 2 [___X] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [____] [____] ++++++++++++++++++++++++++++ level(z) 0 [X___] [O_O_] [_X_O] [___X] level(z) 1 [_O__] [__X_] [_X__] [___O] level(z) 2 [___X] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [____] [____] ++++++++++++++++++++++++++++ num:42 player1:2,1,3 level(z) 0 [X___] [O_O_] [_X_O] [___X] level(z) 1 [_O__] [__X_] [_X__] [___O] level(z) 2 [___X] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [_X__] [____] ++++++++++++++++++++++++++++ (2,1,0)state: 1 (2,1,1)state: 1 (2,1,2)state: 1 (2,1,3)state: 1 Player1 Wins level(z) 0 [X___] [O_O_] [_X_O] [___X] level(z) 1 [_O__] [__X_] [_X__] [___O] level(z) 2 [___X] [O_X_] [_X__] [OOXO] level(z) 3 [X__O] [_X_O] [_X__] [____] |
num:64 player2:1,2,2 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [____] [____] [____] [____] ++++++++++++++++++++++++++++ num:63 player1:2,1,1 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [____] [____] [____] [____] ++++++++++++++++++++++++++++ num:62 player2:0,0,0 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [____] [____] [____] [____] ++++++++++++++++++++++++++++ num:61 player1:0,0,3 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [X___] [____] [____] [____] ++++++++++++++++++++++++++++ num:60 player2:3,3,3 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [X___] [____] [____] [___O] ++++++++++++++++++++++++++++ num:59 player1:2,1,2 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [_X__] [____] level(z) 2 [____] [__O_] [_X__] [____] level(z) 3 [X___] [____] [____] [___O] ++++++++++++++++++++++++++++ num:58 player2:1,2,1 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [__O_] [_X__] [____] level(z) 2 [____] [__O_] [_X__] [____] level(z) 3 [X___] [____] [____] [___O] ++++++++++++++++++++++++++++ num:57 player1:3,3,0 level(z) 0 [O___] [____] [____] [___X] level(z) 1 [____] [__O_] [_X__] [____] level(z) 2 [____] [__O_] [_X__] [____] level(z) 3 [X___] [____] [____] [___O] ++++++++++++++++++++++++++++ num:56 player2:2,2,1 level(z) 0 [O___] [____] [____] [___X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [____] [__O_] [_X__] [____] level(z) 3 [X___] [____] [____] [___O] ++++++++++++++++++++++++++++ num:55 player1:2,2,2 level(z) 0 [O___] [____] [____] [___X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [____] [__O_] [_XX_] [____] level(z) 3 [X___] [____] [____] [___O] ++++++++++++++++++++++++++++ num:54 player2:2,1,3 level(z) 0 [O___] [____] [____] [___X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [____] [__O_] [_XX_] [____] level(z) 3 [X___] [____] [_O__] [___O] ++++++++++++++++++++++++++++ num:53 player1:1,0,0 level(z) 0 [O___] [X___] [____] [___X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [____] [__O_] [_XX_] [____] level(z) 3 [X___] [____] [_O__] [___O] ++++++++++++++++++++++++++++ num:52 player2:3,0,0 level(z) 0 [O___] [X___] [____] [O__X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [____] [__O_] [_XX_] [____] level(z) 3 [X___] [____] [_O__] [___O] ++++++++++++++++++++++++++++ num:51 player1:0,3,3 level(z) 0 [O___] [X___] [____] [O__X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [____] [__O_] [_XX_] [____] level(z) 3 [X__X] [____] [_O__] [___O] ++++++++++++++++++++++++++++ num:50 player2:0,1,2 level(z) 0 [O___] [X___] [____] [O__X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [_O__] [__O_] [_XX_] [____] level(z) 3 [X__X] [____] [_O__] [___O] ++++++++++++++++++++++++++++ num:49 player1:3,0,3 level(z) 0 [O___] [X___] [____] [O__X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [_O__] [__O_] [_XX_] [____] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ num:48 player2:2,3,2 level(z) 0 [O___] [X___] [____] [O__X] level(z) 1 [____] [__O_] [_XO_] [____] level(z) 2 [_O__] [__O_] [_XXO] [____] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ num:47 player1:1,3,1 level(z) 0 [O___] [X___] [____] [O__X] level(z) 1 [____] [__OX] [_XO_] [____] level(z) 2 [_O__] [__O_] [_XXO] [____] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ num:46 player2:1,3,0 level(z) 0 [O___] [X__O] [____] [O__X] level(z) 1 [____] [__OX] [_XO_] [____] level(z) 2 [_O__] [__O_] [_XXO] [____] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ num:45 player1:3,2,1 level(z) 0 [O___] [X__O] [____] [O__X] level(z) 1 [____] [__OX] [_XO_] [__X_] level(z) 2 [_O__] [__O_] [_XXO] [____] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ num:44 player2:1,1,1 level(z) 0 [O___] [X__O] [____] [O__X] level(z) 1 [____] [_OOX] [_XO_] [__X_] level(z) 2 [_O__] [__O_] [_XXO] [____] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ num:43 player1:3,1,2 level(z) 0 [O___] [X__O] [____] [O__X] level(z) 1 [____] [_OOX] [_XO_] [__X_] level(z) 2 [_O__] [__O_] [_XXO] [_X__] level(z) 3 [X__X] [____] [_O__] [X__O] ++++++++++++++++++++++++++++ (3,0,3)state: 1 (3,1,2)state: 1 (3,2,1)state: 1 (3,3,0)state: 1 Player1 Wins level(z) 0 [O___] [X__O] [____] [O__X] level(z) 1 [____] [_OOX] [_XO_] [__X_] level(z) 2 [_O__] [__O_] [_XXO] [_X__] level(z) 3 [X__X] [____] [_O__] [X__O] |
num:64 player1:0,3,3 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [____] [____] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:63 player2:1,2,2 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:62 player1:2,2,2 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:61 player2:0,0,0 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:60 player1:3,0,3 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:59 player2:0,3,0 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:58 player1:1,1,1 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:57 player2:1,1,2 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:56 player1:0,0,3 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:55 player2:3,3,3 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:54 player1:1,2,0 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:53 player2:2,1,1 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [_O__] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:52 player1:2,2,1 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [_OX_] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:51 player2:2,0,3 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [_OX_] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:50 player1:3,3,0 level(z) 0 [O__O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:49 player2:3,2,1 level(z) 0 [O__O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:48 player1:2,3,2 level(z) 0 [O__O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:47 player2:0,1,0 level(z) 0 [OO_O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:46 player1:0,2,0 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:45 player2:1,2,3 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:44 player1:0,1,3 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [XX_X] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:43 player2:0,2,3 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:42 player1:2,1,2 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [_XXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:41 player2:2,0,2 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:40 player1:1,0,2 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:39 player2:1,3,1 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X_O] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:38 player1:2,0,0 level(z) 0 [OOXO] [__X_] [X___] [___X] level(z) 1 [____] [_X_O] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:37 player2:0,0,1 level(z) 0 [OOXO] [__X_] [X___] [___X] level(z) 1 [O___] [_X_O] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:36 player1:3,0,1 level(z) 0 [OOXO] [__X_] [X___] [___X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:35 player2:3,0,0 level(z) 0 [OOXO] [__X_] [X___] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:34 player1:3,2,2 level(z) 0 [OOXO] [__X_] [X___] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:33 player2:2,2,0 level(z) 0 [OOXO] [__X_] [X_O_] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:32 player1:2,2,3 level(z) 0 [OOXO] [__X_] [X_O_] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [X__O] ++++++++++++++++++++++++++++ num:31 player2:3,1,3 level(z) 0 [OOXO] [__X_] [X_O_] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:30 player1:3,1,0 level(z) 0 [OOXO] [__X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:29 player2:1,0,0 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:28 player1:1,0,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:27 player2:2,3,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OXO] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:26 player1:0,3,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:25 player2:3,3,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:24 player1:0,3,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [___X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:23 player2:0,0,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:22 player1:1,3,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:21 player2:1,2,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:20 player1:3,2,0 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:19 player2:2,1,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XO_O] ++++++++++++++++++++++++++++ num:18 player1:0,2,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XO_O] ++++++++++++++++++++++++++++ num:17 player2:3,3,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XO_O] ++++++++++++++++++++++++++++ num:16 player1:3,2,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:15 player2:1,1,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:14 player1:1,3,0 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:13 player2:1,3,2 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:12 player1:2,3,3 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:11 player2:1,0,1 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [OXOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:10 player1:2,1,0 level(z) 0 [OOXO] [O_XX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:9 player2:3,1,1 level(z) 0 [OOXO] [O_XX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [_OXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:8 player1:2,0,1 level(z) 0 [OOXO] [O_XX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [XOXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:7 player2:1,1,0 level(z) 0 [OOXO] [OOXX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [XOXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:6 player1:0,2,1 level(z) 0 [OOXO] [OOXX] [XXO_] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:5 player2:0,1,2 level(z) 0 [OOXO] [OOXX] [XXO_] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:4 player1:2,3,0 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:3 player2:3,1,2 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [_OXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:2 player1:0,1,1 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [OXXX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [_OXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:1 player2:3,0,2 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [OXXX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [OOXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ This is a draw. level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [OXXX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [OOXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] |
num:64 player1:0,3,3 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [____] [____] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:63 player2:1,2,2 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [____] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:62 player1:2,2,2 level(z) 0 [____] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:61 player2:0,0,0 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [____] ++++++++++++++++++++++++++++ num:60 player1:3,0,3 level(z) 0 [O___] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:59 player2:0,3,0 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [____] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:58 player1:1,1,1 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [__O_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:57 player2:1,1,2 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [___X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:56 player1:0,0,3 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X___] ++++++++++++++++++++++++++++ num:55 player2:3,3,3 level(z) 0 [O__O] [____] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:54 player1:1,2,0 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [____] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:53 player2:2,1,1 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [_O__] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:52 player1:2,2,1 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [_OX_] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [____] [X__O] ++++++++++++++++++++++++++++ num:51 player2:2,0,3 level(z) 0 [O__O] [__X_] [____] [____] level(z) 1 [____] [_X__] [_OX_] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:50 player1:3,3,0 level(z) 0 [O__O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [____] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:49 player2:3,2,1 level(z) 0 [O__O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__X_] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:48 player1:2,3,2 level(z) 0 [O__O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:47 player2:0,1,0 level(z) 0 [OO_O] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:46 player1:0,2,0 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [____] [O___] [X__O] ++++++++++++++++++++++++++++ num:45 player2:1,2,3 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [X__X] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:44 player1:0,1,3 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [XX_X] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:43 player2:0,2,3 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [__XX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:42 player1:2,1,2 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [_XXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:41 player2:2,0,2 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [_OO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:40 player1:1,0,2 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X__] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:39 player2:1,3,1 level(z) 0 [OOXO] [__X_] [____] [___X] level(z) 1 [____] [_X_O] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:38 player1:2,0,0 level(z) 0 [OOXO] [__X_] [X___] [___X] level(z) 1 [____] [_X_O] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:37 player2:0,0,1 level(z) 0 [OOXO] [__X_] [X___] [___X] level(z) 1 [O___] [_X_O] [_OX_] [__O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:36 player1:3,0,1 level(z) 0 [OOXO] [__X_] [X___] [___X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:35 player2:3,0,0 level(z) 0 [OOXO] [__X_] [X___] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [____] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:34 player1:3,2,2 level(z) 0 [OOXO] [__X_] [X___] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:33 player2:2,2,0 level(z) 0 [OOXO] [__X_] [X_O_] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O___] [X__O] ++++++++++++++++++++++++++++ num:32 player1:2,2,3 level(z) 0 [OOXO] [__X_] [X_O_] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [X__O] ++++++++++++++++++++++++++++ num:31 player2:3,1,3 level(z) 0 [OOXO] [__X_] [X_O_] [O__X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:30 player1:3,1,0 level(z) 0 [OOXO] [__X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:29 player2:1,0,0 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [__O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:28 player1:1,0,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OX_] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:27 player2:2,3,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O___] [_X_O] [_OXO] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:26 player1:0,3,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__X_] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:25 player2:3,3,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [____] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:24 player1:0,3,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [___X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:23 player2:0,0,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_O_] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:22 player1:1,3,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_X_O] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:21 player2:1,2,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OX_X] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:20 player1:3,2,0 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [O_X_] [XO_O] ++++++++++++++++++++++++++++ num:19 player2:2,1,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O__X] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XO_O] ++++++++++++++++++++++++++++ num:18 player1:0,2,2 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_O_] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XO_O] ++++++++++++++++++++++++++++ num:17 player2:3,3,1 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XO_O] ++++++++++++++++++++++++++++ num:16 player1:3,2,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [X_OX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:15 player2:1,1,3 level(z) 0 [OOXO] [O_X_] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:14 player1:1,3,0 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOO_] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:13 player2:1,3,2 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOX_] [XOXO] ++++++++++++++++++++++++++++ num:12 player1:2,3,3 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [_XOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:11 player2:1,0,1 level(z) 0 [OOXO] [O_XX] [X_O_] [OXXX] level(z) 1 [O__X] [OXOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:10 player1:2,1,0 level(z) 0 [OOXO] [O_XX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [_OXO] [X_OO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:9 player2:3,1,1 level(z) 0 [OOXO] [O_XX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [_OXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:8 player1:2,0,1 level(z) 0 [OOXO] [O_XX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [XOXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:7 player2:1,1,0 level(z) 0 [OOXO] [OOXX] [XXO_] [OXXX] level(z) 1 [O__X] [OXOO] [XOXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:6 player1:0,2,1 level(z) 0 [OOXO] [OOXX] [XXO_] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [O_XX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:5 player2:0,1,2 level(z) 0 [OOXO] [OOXX] [XXO_] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:4 player1:2,3,0 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [__XO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:3 player2:3,1,2 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [O_XX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [_OXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:2 player1:0,1,1 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [OXXX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [_OXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ num:1 player2:3,0,2 level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [OXXX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [OOXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] ++++++++++++++++++++++++++++ This is a draw. level(z) 0 [OOXO] [OOXX] [XXOX] [OXXX] level(z) 1 [OXXX] [OXOO] [XOXO] [XOOO] level(z) 2 [OOXX] [XOOO] [OXXX] [OOXO] level(z) 3 [XXOX] [XOOX] [OOXX] [XOXO] |
Discussion
Observations:
- The shallower layer the opponent player search, the more likely that AI system will win the game.
- The smaller the difference in depth of searching between two AI systems, the greater the probability of getting a draw.
- Deeper search always comsume exponentially more time.
- If pruning method is implemented, minimax algorithm will react obviously faster.
- When AI search deep enough, the easiness of such game limit the possibility of reflecting difference between two AI system.
Analysis:
- An AI system can be considered more intelligent such game generally, if it search deeper in searching tree.
- Its is of importance to make a wise trade-off between time efficiency and intelligence to design a good AI system.
Conclusions
In this assignment, we successfully design an AI gaming system which can beat random gaming system efficiently. The experiment results show the usefulness and efficiency of our AI gaming system.
Kaihong Wang and Qitong Wang usually discussed together and finished the assignment.
Credits and Bibliography
Reference:
https://en.wikipedia.org/wiki/Tic-tac-toe
https://en.wikipedia.org/wiki/3D_tic-tac-toe#cite_note-7