A new enhancement to MTD(f)

Eric Stock, David J. King

Research output: Contribution to conferenceAbstract

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 languageEnglish
Number of pages5
Publication statusPublished - 2010
Event15th International Computer Games Conference - Louisville, United States
Duration: 28 Jul 201031 Jul 2010
Conference number: 15th

Conference

Conference15th International Computer Games Conference
Abbreviated titleCGAMES 2010
CountryUnited States
CityLouisville
Period28/07/1031/07/10

Fingerprint Dive into the research topics of 'A new enhancement to MTD(f)'. Together they form a unique fingerprint.

Cite this