一种生成残局数据库的倒推算法

A Retrograde Algorithm for Generating Endgame Databases

通过研究爱恩斯坦棋的一种倒推算法,实现爱恩斯坦棋局面胜率的可推导化,借助倒推算法对爱恩斯坦棋局面胜率进行相关计算,解决如何建立爱恩斯坦棋残局库的问题。为了方便胜率的计算,将已走胜率作为胜率生成的目标,提出将若干个已知胜率且复杂度低的局面进行倒推收敛,从而得到复杂度高的局面计算方法,证明了“任一局面都可由若干个已胜局面通过倒推收敛的方法,计算出误差仅受数据类型的精度影响的准确胜率”的理论,并在此理论基础上设计出能够按局面复杂度来逐个标记各个不存在的局面,计算所有需要的存在局面,生成各个局面胜率的倒推算法。最后在数据储存量有限的情况下,构造出部分数据的储存替代方法,尽可能降低所需数据的存储量,使倒推算法在能够计算出残局库的条件下,可以配合其他局面评估算法提升其程序的获胜概率。

By studying an inverse calculation method of Einstein chess,we can deduce the winning rate of Einstein chess,calculate the winning rate of Einstein chess with the help of retrograde algorithm,and solve the problem of how to establish the endgame databases of Einstein chess.We take the walking winning rate as the goal of the winning rate generation,and set the concept of situation complexity to calculate easily,in order to facilitate the calculation of the winning rate.We calculate several situations with known winning rate and low complexity by retrograde algorithm to get the situation with high complexity and winning rate.At the same time,it is proved that the winning rate of any situation can be calculated by the method of retrograde algorithm,and calculated accuracy winning rate error is only affected by the accuracy of the data type.On the basis of this theory,we design the situation complexity which can mark each nonexistent situation one by one according to the complexity of the situation and generate all the necessary existing situations.Finally,in the case of limited data storage,we construct an alternative method to store part of the data,in order to reduce the storage of the required data as much as possible.Under the condition that the retrograde algorithm can calculate the endgame databases,it can cooperate with other situation evaluation algoritms to improve the winning rate of its program.