Reversi DS is an open source (GPL licensed) reversi game for the Nintendo DS. It features an intelligent computer opponent and an intuitive touch screen interface. It is developed to run on the Nintendo DS using 3rd party homebrew capable media or on Nintendo DS emulators. It is programmed in C++ and uses devkitPro. Releases are tested on the DS Lite and DeSmuME. The project was started by Darren Earl in the Fall of 2009.
Reversi is a classic 2 player boardgame traditionally played on an 8 by 8 cell board. Pieces are uniform and two sided--each side being colored one of two colors. Opposing pieces are flipped if they are trapped between the played piece and another piece of the same color already present on the board. A player must flip pieces on his turn, otherwise it is forfeited. The winner is the player with the most pieces of his color on the board when no moves are available.
Reversi DS contains an intelligent computer player which uses proven methods of Artificial Intelligence game playing. It is similar is spirit (but not in sophistication or strength) to Deep Blue, the famous chess playing computer. The method it uses is the "Minimax algorithm with Alpha Beta pruning." Minimax is an exhaustive search of all possible moves for several turns and selects the sequence with the largest minimal value. Since this algorithm cannot usually search to the end of the game, it must evaluate intermediate board positions. Alpha-beta pruning is an improvement of Minimax which logically eliminates branches of the search which cannot affect the solution. This allows the minimax to be perform searches at greater depths in a timely manner than would be possible without. The quality and characteristics of the board evaluation and the depth in turns of the search determine the strength and characteristics of the opponent.