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

Artificial intelligence
Computer program listings
Data storage equipment
Testing

Cite this

Stock, E., & King, D. J. (2010). A new enhancement to MTD(f). Abstract from 15th International Computer Games Conference, Louisville, United States.
Stock, Eric ; King, David J. / A new enhancement to MTD(f). Abstract from 15th International Computer Games Conference, Louisville, United States.5 p.
@conference{0471f17d56244a818aa2284370e2c8e9,
title = "A new enhancement to MTD(f)",
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.",
author = "Eric Stock and King, {David J.}",
year = "2010",
language = "English",
note = "15th International Computer Games Conference, CGAMES 2010 ; Conference date: 28-07-2010 Through 31-07-2010",

}

Stock, E & King, DJ 2010, 'A new enhancement to MTD(f)' 15th International Computer Games Conference, Louisville, United States, 28/07/10 - 31/07/10, .

A new enhancement to MTD(f). / Stock, Eric; King, David J.

2010. Abstract from 15th International Computer Games Conference, Louisville, United States.

Research output: Contribution to conferenceAbstract

TY - CONF

T1 - A new enhancement to MTD(f)

AU - Stock, Eric

AU - King, David J.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

M3 - Abstract

ER -

Stock E, King DJ. A new enhancement to MTD(f). 2010. Abstract from 15th International Computer Games Conference, Louisville, United States.