After reading the previous week’s study, we concluded that we couldn’t implement the A* algorithm. The reasons that we couldn’t implement it are the heuristic function explanation which is oversimplified and the mechanism of how A* works which is fundamentally different than how congklak is played. Therefore, we decided to move from A* to Minimax algorithm.

Disclaimer: Pruning will be explained next week, as we were focusing on the vanilla Minimax.

For those who haven’t known, the Minimax algorithm works based on the zero-sum game theory. So essentially, the min and the max player will choose the most optimal decision based on the opponent’s most optimal decision. It’s a DFS type algorithm that works its way down to the leaf and returns the value upward to the root.

The Minimax class contains depth, maxPlayer, expandedNode, and pruning. Depth is used to determine until which deep the AI goes to for finding the decision. maxPlayer is used to determine the if the AI is max or min. ExpandedNode is used to count how many nodes have been processed in total. Pruning will be used to determine if the AI uses pruning or not.

This method is used within the main Minimax algorithm to find every available path to go through based on the given node.

This method is created due to the possibility of the congklak’s player having a free turn to play. This checks if the given node has a free turn for the current player and return the free turn boolean for later if-else statement, the number of possible child, and the child data themselves.

This method is created to check whether the given node is on the same level as 0 or the node is a terminal condition. If the node meets it, it will return True.

This is the heuristic value used by the Minimax. If the AI plays as the maximizing player, it will return the P1’s house and if the AI plays as the min one, it will return the P2’s house.

Commit move method is called in the game environment by the AI to initiate the finding of the most optimal path.

Minimax method accepts the congklak data/node, the depth of the game, maximizing/minimizingPlayer as boolean, freeTurn boolean to determine if the current Minimax function is handling a free turn, freeTurnData for the data needed by the free turn, alpha and beta for pruning ability.

this if-else is used to check whether the current node meets the terminal condition and return the heuristic value of the node.

in the Minimax method, the code is divided into 2 part mainly, the maximizing player part and the minimizing player part. Both are almost the same.

Depending on the current state of the turn, the number of possible children and the data based on the current node can be gotten in 2 different way. The 1st one is by accepting the free turn data as this method is only applicable if the current node right now is derived from free turn. Else, it will execute the checkLegalMoves() to find any available path.

If there is no number of the possible children, it will end the turn and calling another Minimax() of the opponent’s.

If there exists the number of possible children, it will check one by one the possible children.

Each possible child will be checked if it has a free turn. If a free turn exists, it will get the data needed for the free turn’s node manipulation and calling a Minimax() with the current possible child and the free turn data as its arguments. The Minimax() will return the value of the child and the direction of it.

After getting the value and the direction of the currently processed child node, it will be compared with the current best value. If it meets it, it will be stored as the new best value and the best direction.