Abstract
Programmers have used the Alpha - Beta algorithm since the 1960's to enable computers to play games classified as 2 player, zero-sum with perfect information (Marsland 1986). Chess, Othello, Checkers and Go are examples of this genre of game. Specifically, amongst all elite computer chess programs, the Alpha - Beta algorithm is used (Computer Chess Rating List). The acceptance of the Alpha - Beta algorithm is so universal that many introductory texts and books on artificial intelligence include information on it.
An alternative to the Alpha - Beta algorithm was proposed by Aske Plaat in the mid 1990's (Plaat, A., et al. 1995). Initial testing on this algorithm demonstrated that Memory Enhanced Test Driver with initial guess f or MTD(f) has the potential to out-perform the Alpha - Beta algorithm. However, since then MTD(f) has not seen widespread acceptance as a legitimate alternative to Alpha - Beta.
The research presented in this paper will outline possible reasons why the MTD(f) algorithm has thus far not been successfully implemented in a state of the art chess program. A new enhancement to MTD(f) will then be introduced. The results from a series of tests using the open source chess program Crafty v23.0 will then be presented. These results indicate that the enhanced version of MTD(f) outperforms the Alpha - Beta version of Crafty.
| Original language | English |
|---|---|
| Number of pages | 5 |
| Publication status | Published - 2010 |
| Event | 15th International Computer Games Conference - Louisville, United States Duration: 28 Jul 2010 → 31 Jul 2010 Conference number: 15th |
Conference
| Conference | 15th International Computer Games Conference |
|---|---|
| Abbreviated title | CGAMES 2010 |
| Country/Territory | United States |
| City | Louisville |
| Period | 28/07/10 → 31/07/10 |
Keywords
- MTD(f)
- Computer chess
- Alpha - beta