Awari game score database

This provides supplementary material to this original publication: John W. Romein, Henri E. Bal (2003): "Solving the Game of Awari using Parallel Retrograde Analysis", IEEE Computer, Vol. 36, No. 10 The paper describes a method to compute the full game state of the African board game Awari. Awari involves placing 48 seeds in 12 pits, and players take turns fetching the seeds out of one of their 6 pits, and spreading ("sowing") them counter-clockwise over the other pits. A player captures stones by sowing the last stone into an opponent’s pit so that it contains either two or three stones. If the second-to-last pit is also an opponent’s pit containing two or three stones, the player captures these stones as well, and so on, moving clockwise until reaching the player’s own pit or an opponent’s pit with fewer than two or more than three stones. The paper discusses the challenge to compute the best possible move from an arbitrary position, of which there are about 889 billion (actually 889,063,398,406 to be precise). The computational effort is significant, as are the memory and storage requirements, yet with special techniques, it was possible to tackle this on a cluster of 72 compute nodes over 20 years ago. Nowadays it is possible to compute the same data on a single compute node, provided it has enough memory (e.g., 1 TB). This repository contains the full Awari score databases to make them available for further research, e.g., deep learning approaches to learn playing the game automatically (though likely not perfectly) by modern approaches like Alpha Zero. NOTE: the storage requirements for the full database are significant, in total taking up over 800 GB. It is possible to download only a subset of the database for just up to a certain number of seeds. This would still allow analyzing board positions with up to that number of seeds on the board. In subdirectory Awari-Python there is sample code to retrieve the score of an arbitrary position.

本材料为下述原创出版物的补充资料：John W. Romein与Henri E. Bal（2003）发表于《IEEE计算机》（IEEE Computer）第36卷第10期的论文《使用并行逆向分析求解奥瓦里（Awari）棋盘游戏》。该论文提出了一种计算非洲传统棋盘游戏奥瓦里完整博弈状态的方法。奥瓦里的规则为：在12个棋坑中放置48枚棋子，双方玩家轮流从己方的6个棋坑中取出所有棋子，随后按逆时针方向将棋子依次播撒至其余棋坑中。当玩家将最后一枚棋子播撒至对手的棋坑且该坑恰好存有2或3枚棋子时，即可俘获该坑内的所有棋子；若紧邻该坑的前一个棋坑同样为对手所有且存有2或3枚棋子，则玩家可一并俘获该坑棋子，以此类推，沿顺时针方向持续俘获，直至抵达己方棋坑，或对手棋坑内棋子数不足2或多于3枚时停止。该论文探讨了从任意棋盘局面求解最优走法的挑战——此类局面总数约为8890亿（精确值为889063398406）。其计算量、内存与存储开销均十分可观，但借助特殊技术，早在20余年前，研究团队便已在由72个计算节点组成的集群上完成了此类计算。如今，仅需配备足够内存（例如1 TB）的单台计算节点即可完成相同数据的计算。本仓库包含完整的奥瓦里评分数据库，以供后续研究使用，例如采用深度学习方法通过Alpha Zero等现代技术自动学习该游戏的玩法（尽管可能无法达到完美水平）。注意：完整数据库的存储开销较大，总容量超过800 GB。用户可仅下载特定棋子数以内的数据库子集，这仍可用于分析棋盘上棋子数不超过该阈值的局面。在子目录Awari-Python中，提供了用于检索任意棋盘局面评分的示例代码。