Review of Kalah Game research and the proposition of a novel heuristic-deterministic algorithm compared to tree-search solutions and human decision-making

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F20%3A10245844" target="_blank" >RIV/61989100:27240/20:10245844 - isvavai.cz</a>

Alternative codes found

RIV/70883521:28140/20:63526265

Result on the web

<a href="https://www.mdpi.com/2227-9709/7/3/34#cite" target="_blank" >https://www.mdpi.com/2227-9709/7/3/34#cite</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/INFORMATICS7030034" target="_blank" >10.3390/INFORMATICS7030034</a>

Result language

angličtina

Original language name

Review of Kalah Game research and the proposition of a novel heuristic-deterministic algorithm compared to tree-search solutions and human decision-making

Original language description

The Kalah game represents the most popular version of probably the oldest board game ever-the Mancala game. From this viewpoint, the art of playing Kalah can contribute to cultural heritage. This paper primarily focuses on a review of Kalah history and on a survey of research made so far for solving and analyzing the Kalah game (and some other related Mancala games). This review concludes that even if strong in-depth tree-search solutions for some types of the game were already published, it is still reasonable to develop less time-consumptive and computationally-demanding playing algorithms and their strategies Therefore, the paper also presents an original heuristic algorithm based on particular deterministic strategies arising from the analysis of the game rules. Standard and modified mini-max tree-search algorithms are introduced as well. A simple C++ application with Qt framework is developed to perform the algorithm verification and comparative experiments. Two sets of benchmark tests are made; namely, a tournament where a mid-experienced amateur human player competes with the three algorithms is introduced first. Then, a round-robin tournament of all the algorithms is presented. It can be deduced that the proposed heuristic algorithm has comparable success to the human player and to low-depth tree-search solutions. Moreover, multiple-case experiments proved that the opening move has a decisive impact on winning or losing. Namely, if the computer plays first, the human opponent cannot beat it. Contrariwise, if it starts to play second, using the heuristic algorithm, it nearly always loses. (C) 2020 by the authors.

Czech name

—

Czech description

—

Type

J_SC - Article in a specialist periodical, which is included in the SCOPUS database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Informatics

ISSN

2227-9709

e-ISSN

—

Volume of the periodical

7

Issue of the periodical within the volume

3

Country of publishing house

CH - SWITZERLAND

Number of pages

27

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

2-s2.0-85092458546