I worked on the AI part, where you can choose to play as a tiger or goat and challenge the computer depending on different levels. It was my first time implementing AI, which was very challenging, but I learned a lot. The algorithm used is only used to select the best move for the computer when a player chooses to play against computer.
Initially, I wanted to learn TensorFlow.js and implement the AI part for this game, but since we had very limited time and I had a lot to learn for that. So I used one of the popular algorithms for the basic AI implementation, Minimax algorithm. A minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. It is used in decision making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. It is widely used in two-player turn-based games such as Tic-Tac-Toe, Backgammon, Chess, etc.
In Minimax the two players, tiger and goat are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to do the opposite and get the lowest score possible. When we play with the computer, goat is a minimizer and the tiger is a maximizer. So basically, if the player chooses to play as a goat, the computer will be tiger and will try to score maximum score as possible and vice versa. I have set 3 levels: easy, medium and hard as depth level 1,2 and 3 respectively where the depth level indicates how many levels should the computer evaluate the score recursively for each movement of a player.
For example, If the player chose the hard mode, then the depth level is 3, now if the player chose to play as a goat, then the computer becomes tiger. So, the algorithm tries to maximize the score for tiger, the highest score will be selected as the best move for the computer. Imagine you are looking at the tree graph, the initial point is the move made by a player and every move will be represented as a node. So now the computer lists all the possible moves of the tiger as level 1. Say, there are 10 moves tiger can go in level 1. So in the 1st level of the tree, there are 10 nodes. In the second level, the computer will try to list all the possible moves for the goat as a prediction, for each tiger move the computer has made on the first level. Say, for each node in 10 nodes of the first level, the computer lists 8 goat moves, so that’s like 10x8 possible move combinations. Similarly, for each goat move in the second level, the computer will list all the tiger moves as a prediction in the third level. Say, for each move, in level 2 the computer lists 6 tiger moves in level 3. Now there are total 10x8x6 possible combination in 3rd step of gameplay.
Since there is only have 3 levels in hard mode, and the leaf node in the tree representation will be level 3. Now the computer evaluates all the possible moves and calculates the score for each move. The scoring system is based on multiple factors such as if the tiger is surrounded and has no moves, the number of dead goats, if in next move the goat will die, etc. So the 3rd level is the move of tiger, which means, in the tree the leaf node that has the maximum score will be chosen and will pass the value to second level nodes. Meaning that the score will be compared among all the nodes in level 3 that has come from level 2 in the tree. So only the maximum score node will be chosen and the score is sent to level 2 to re-compare. Similarly, all the second nodes has a score now. Now, these scores will be compared amongst all the nodes that have come from the same parent node from level 1. Since the level 2 is goat move prediction, so the minimum score will be chosen and sent to level 1. Now all the 10 possible tiger move node has an individual value, the maximum score will be chosen amongst all and will be selected as the best move for the computer.
Similar logic is applied for medium and easy game mode, where the depth level is only 2 and 1. Basically, the depth levels represent how many steps ahead should computer think and evaluate the possible movements. Since the example only contains 10x8x6 possible movements which is a very small number, the actual game can have a large number of possible movements. So computing all the nodes will be very time-consuming, therefore I’ve used another algorithm called alpha-beta pruning.
Alpha-beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games. It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
The game, baghchal, is quite popular in Nepal, and there has been very few implementation of AI for this game. I did a lot of research on minimax and alpha-beta pruning, and got the opportunity to learn and implement for this project.