Heuristic method for tablebases: A Case Study of Thai chess endgame in King-Knight-Queen-King pattern

Authors

  • Thanapon Tudsuan คณะวิศวกรรมศาสตร์ สถาบันเทคโนโลยีพระจอมเกล้าเจ้าคุณทหารลาดกระบัง
  • Kietikul Jearanaitanakij Department of Computer Engineering, School of Engineering, King Mongkut's Institute of Technology Ladkrabang

Keywords:

Alpha-beta pruning, Heuristic, Endgame tablebases, Thai chess

Abstract

This research aims to develop the endgame tablebases and design the heuristic for playing Thai chess in King-Knight-Queen-King Pattern. The chasing side includes a King, a Knight, and a Queen, whereas the other has only a King (a total of four pieces). The heuristic designed in King-Knight-Queen-King Pattern consists of 5 tables as follows: 1) King Distance Table 2) Black King Table 3) White King Table 4) White Knight Table and 5) White Queen Table. Alpha-beta pruning was applied in this study. Iterative Deepening Depth-First Search with a depth of 10 was used to evaluate the heuristic. The researcher tested the program by competing with Senior Soft Thai Chess Master V3 of 100 games and recorded the results in 4 parts: 1) winning rate 2) the average number of times it took to win by checkmate 3) the average time per move counted at 10, 15, 20 moves and 4) the average length of checkmate per game. Afterward the results were compared with three methods consisting of 1) Quiescence search 2) Prorp program (adapted from Stockfish) and 3) National Thai chess players. After comparing the result with three methods, the findings showed that this research is most effective, which can be explained as follows: 1) winning rate is 100 percentage  2) the average number of times it took to win by checkmate is 34 moves 3) the average time per move counted at 10, 15, 20 moves are 3.908, 3.695, 3.400 second and 4) the average length of checkmate per game is 84.658 second. The result of the endgame tablebases, all the positions have 472,900 positions for checkmate. The longest checkmate is 36 moves (White to move and checkmate in 64-move rule).

References

V. Janko and M. Guid, Development of a program for playing progressive chess, in: Advances in Computer Games (ACG 2015), in: Lecture Notes in Computer Science, Vol. 9525, pp. 122–134, Springer, 2015.

W. Saletan, "Chess Bump: The triumphant teamwork of humans and computers," 11 May 2007. [Online]. Available: https://slate.com/technology/2007/05/the-triumphant-teamwork-of-humans-and computers.html. [Accessed 15 January 2020].

"CCRL 40/15," 11 January 2010. [Online]. Available: computerchess.org.uk. [Accessed 13 January 2020].

R. Gralla, "Kramnik plays Makruk Thai," 2004. [Online].Available: https://www.chessvariants.com /oriental.dir/thaikramnik.html. [Accessed 10 July 2020].

D.B. Pritchard and J.D. Beasley, The Classified Encyclopedia of Chess Variants, J. Beasley, UK, 2007.

Siamsport, "Siamsport," 22 October 2017. [Online]. Available: https://www.siamsport.co.th/column/detail/68156. [Accessed 29 January 2020].

M. Guid, M. Moˇzina, A. Sadikov and I. Bratko, "Deriving Concepts and Strategies from Chess Tablebases," Advances in Computer Games 12th International Conference ACG 2009, Pamplona, Spain, 2009.

O. Marckel, "Alpha-beta Pruning in Chess Engines," Minnesota, USA, 2017.

M. Luštrek, M. Gams and I. Bratko, "Is real-valued minimax pathological?," Elsevier, Vol. 170, No. 6, pp. 620-642, 2006.

E. A. Heinz, "Endgame Databases and Efficient Index Schemes for Chess," ICCA Journal, Vol. 22, No. 1, pp. 22-32, 1999.

A. Castelli, S. Progressivi and M. Eccellenti, (in Italian; "Progressive Chess. Excellent Checkmates"), Macerata-Italy, 1996.

A. Castelli, S. progressivi and F. di Partita, (in Italian; “Progressive Chess. Endgames”), Macerata-Italy, 1997.

G. M. Haworth, "Chess Endgame News: 7-man ‘Syzygy’ DTZ 50 EGTs," ICGA journal, Vol. 40, No. 10, pp. 1-2, 2019.

G. Breda, KRK Chess Endgame Database Knowledge Extraction and Compression, Darmstadt Germany, 2006.

L. Kocsis and C. Szepesvári, Bandit based Monte-Carlo planning, in: Machine Learning: ECML 2006, Springer, pp. 282–293, 2006.

D. E. Knuth and R. W. Moore, "Artificial Intelligence," Elsevier, Vol. 6, No. 4, pp. 293-326, 1975.

W. B. Putra and L. Heryawan, " Applying alpha-beta algorithm in a chess engine," Jurnal Teknosains, Vol. 6, No. 1, pp. 37-43, 2017.

G. Schrufer, "A Strategic Quiescence Search," ICCA Journal, Vol. 12, No. 1, pp. 3-9, 1989.

M. H. Winands, "Quiescence Search for Stratego," The 21st Benelux Conference on Artificial Intelligence, Eindhoven, 2009.

J. Schaeffer, "The History Heuristic," ICCA Journal, Vol. 6, No. 3, pp. 16-19, 1983.

V. Janko and M. Guid, "A program for Progressive chess," Elsevier, Vol. 644, No. 1, pp. 76-91, 2016.

D. M. J. Tax, R. Duin and D. D. Ridder, Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB, John Wiley & Sons, USA, 2004.

Downloads

Published

2021-06-22

How to Cite

[1]
T. Tudsuan and K. . Jearanaitanakij, “Heuristic method for tablebases: A Case Study of Thai chess endgame in King-Knight-Queen-King pattern”, Eng. & Technol. Horiz., vol. 38, no. 2, pp. 17–30, Jun. 2021.

Issue

Vol. 38 No. 2 (2021): April -June

Section

Research Articles

License

The published articles are copyrighted by the School of Engineering, King Mongkut's Institute of Technology Ladkrabang.

The statements contained in each article in this academic journal are the personal opinions of each author and are not related to King Mongkut's Institute of Technology Ladkrabang and other faculty members in the institute.
Responsibility for all elements of each article belongs to each author; If there are any mistakes, each author is solely responsible for his own articles.