graded 30/30 on 03.06.2022
with Tytus Pikies, PhD Eng.
The task is composed of two parts. The first one is to implement an engine of a generalized version of tic-tac-toe. The second one is to implement a program solving the game using min-max algorithm (https://en.wikipedia.org/wiki/Minimax).
The generlized version of tic-tac-toe, i.e. the family of games NMK (https://en.wikipedia.org/wiki/M,n,k-game), accepts 3 parameters: N, M, and K, where:
- (N x M) is the size of a board,
- The value (K) determines the victory condition. That is, K neighbouring fields forming a continues horizontal or vertical or diagonal line section give a victory.
It is required to implement a deterministic generator of moves which adds a token of a player (representing the move of the player) (for example a cross, a circle, or white or black token) starting in left upper corner, first passing all the columns and then proceeding to the next row. In the assignment the tokens of the first player (Player 1) are marked as '1', the tokens of the second player (Player 2) as '2', and empty fields as '0'. Hence in the basic version of tic-tac-toe (NMK 3,3,3) the generated moves for an empty initial board are (keep in mind that the order is important):
100 010 001 000 000 000 000 000 000 000 000 000 100 010 001 000 000 000 000 000 000 000 000 000 100 010 001
The engine of the game should allow to:
- Generate all the moves.
- Mark the state of the game. That is, it should produce an answer if the game has ended and the player won/tied/lost.
In the enhanced version, if one of the generated states is final (one of the players won or the board is full [which means tie]), then the engine should generate only one state. If there are a few states possible, then it should generate only the first win/tie state. Observe that if the newly generated state is win, then it can be only the win state for the active player; it is not possible, that the active player induces the winning of the opponent by her move.
For example all states for an initial state (Player 1 is active) for
102 012 000
are:
112 102 102 102 102 012 112 012 012 012 000 000 100 010 001
Only the last one is win state for Player 1, and in the enhanced version of engine only it should be generated.
In the second part of the assignment it is required to implement am algorithm solving some, not necessarily initial, state of the NMK game. One can use Minmax or Negmax with some enhancements. Observe that in the case of this family of games the solution is always determined, because it is 2-players game, without randomness, and without hidden information. Hence it is possible to determine if the game ends in winning (losing) of a player or in a tie.
The first enhancement for Minmax is to end the min search in the case of finding -1 or max search in the case of finding 1, because the results cannot be enhanced. The second enhancement is the observation that there are situations that a player has winning move in the next move (provided that the situation did not appeared earlier for the opponent). Precisely it is possible that there is a sequence of (K-1) tokens which can be completed on both ends. Consider the example for a game (4,4,3):
0000 0110 0200 0002
Player 1 is active and it can be seen that Player 2 cannot win. If Player 2 puts a token on the left,
0000 2110 0200 0002
then Player 1 puts a token on the right.
0000 2111 0200 0002
If Player 2 puts the token on the right,
0000 0112 0200 0002
then Player 1 puts the token on the left.
0000 2110 0200 0002
Hence, finding such a situation can be marked as a danger for one of the players. If in the future we find such a game state and the opponent of the player constructing such a situation, i.e. the player that becomes endangered, did not win in a given move, then the endangered player cannot win in future.
The program should handle 3 moves:
- GEN_ALL_POS_MOV N M K ActivePlayer - generate all possible moves and the number of moves.
Examples:
Input:
GEN_ALL_POS_MOV 3 3 3 2 1 0 0 0 0 0 0 0 0
Output:
8 1 2 0 0 0 0 0 0 0
1 0 2 0 0 0 0 0 0
1 0 0 2 0 0 0 0 0
1 0 0 0 2 0 0 0 0
1 0 0 0 0 2 0 0 0
1 0 0 0 0 0 2 0 0
1 0 0 0 0 0 0 2 0
1 0 0 0 0 0 0 0 2
Input:
GEN_ALL_POS_MOV 3 3 3 1 1 2 0 0 0 0 0 0 0
Output:
7 1 2 1 0 0 0 0 0 0
1 2 0 1 0 0 0 0 0
1 2 0 0 1 0 0 0 0
1 2 0 0 0 1 0 0 0
1 2 0 0 0 0 1 0 0
1 2 0 0 0 0 0 1 0
1 2 0 0 0 0 0 0 1
- GEN_ALL_POS_MOV_CUT_IF_GAME_OVER N M K ActivePlayer - generate all feasible moves and the number of such moves. If one of the moves results in win or tie, then generate only the first such a move:
Input:
GEN_ALL_POS_MOV_CUT_IF_GAME_OVER 3 3 3 1
0 2 1 2 2 1 0 1 0
Output:
1 0 2 1 2 2 1 0 1 1
Input:
GEN_ALL_POS_MOV_CUT_IF_GAME_OVER 3 3 3 1
1 2 1 2 2 1 0 1 2
Output:
1 1 2 1 2 2 1 1 1 2
3 SOLVE_GAME_STATE N M K ActivePlayer - solving the game and stating one of the possible answers: FIRST_PLAYER_WINS, SECOND_PLAYER_WINS, BOTH_PLAYERS_TIE.
Examples:
Input:
SOLVE_GAME_STATE 3 3 3 2 1 0 0 0 0 0 0 0 0
Output:
BOTH_PLAYERS_TIE
Input:
SOLVE_GAME_STATE 3 3 3 1 1 2 0 0 0 0 0 0 0
Output:
FIRST_PLAYER_WINS
All the tests used in the assignment are available at e-nauczanie (e-learning) platform.