Abstract
The minimax algorithm is a search technique that is often used in two player perfect knowledge games like checkers, go, and chess. The algorithm assumes that both players will pick the optimal move. The trappy minimax algorithm recognizes that the human opponent may not be making the optimal move and will use that knowledge to set traps by looking for high-valued positions that have lower values at shallow search depths. The trappy minimax algorithm has shown to have success for games like Othello and Checkers. This project implements a checkers program using trappy minimax for use on the iPhone and will test its effectiveness compared to regular minimax. The minimax algorithm resembles a tree when viewed graphically. At the top level you may have MAX and then the next level would be MIN and then the next level is MAX, thus giving it the name minimax. At the MAX levels, the highest value node is taken. At the MIN levels, the lowest value node is taken. This back and forth technique in game play represents the two opponents trying to maximize their own game play as seen from the point of view of the computer. One problem with minimax is that it assumes that each player is going to choose the optimal move (highest value), but this can't always be since human opponents rarely consider every possibility when determining their move. The minimax algorithm has been used in many strategy games such as Go, Othello, Tic- Tac-Toe, checkers and chess. In each of these games, the computer has the advantage of looking ahead at possible moves that its opponent can make and in turn what moves it can make. This look ahead gives the computer the advantage of looking for moves that will lead to an optimal position that is X number of moves ahead. Knowing that the opponent may not look ahead that far, a computer could set a trap for its opponent. A trap in general for a game would be a move that appears to the opponent as a favorable move, but in fact leads to the computer being in a better position. In a game like chess, a trap can be as simple as the computer allowing a bishop to be captured because it will allow the opponents queen to be taken. This is a trap if the opponent is only capable of seeing as deep as winning the bishop. Trappy minimax has been implemented in previous masters' projects for the game of checkers and Othello. Each of these games had varying levels of effectiveness when using the trappy minimax technique. This project is unique in that it utilizes the iPhone for both the game, and for the collecting of results data.