A New Version Of Minimax That Doesn't Assume Best Move

V. Scott Gordon and Michael Vollmer, CSU Sacramento, CA

Stevenson Hall 1300
12:00 PM - 12:50 PM

At the core of every computer strategy game (such as in a chess program) is the minimax algorithm. Minimax works by assuming that both players always choose the best move. But that isn't how humans decide their moves - instead, humans try to set traps that lure the opponent into making a wrong move. We developed a "Trappy Minimax" algorithm to emulate this more human-like style, using a clever trick involving iterative deepening search. We then took a well-known existing chess program (ChessBrain), substituted trappy minimax, and tested both versions on ICC (Internet Chess Club). The "trappy" version achieved a significantly higher rating, even though it sometimes plays moves that, according to normal minimax, are flawed. The results call into question the most basic tenet of the minimax algorithm, and offer a powerful alternative.