基于赛制组织的遗传变异棋局样例生成算法

Genetic Mutation Game Sample Generation Algorithm Based on Tournament Organization

计算机棋类游戏的研究目标是人工智能选手的智力提高,而学习样例对棋局局面的代表性,在很大程度上决定了选手的智力水平,但学习样例的产生方式和优劣判定一直未能引起足够重视.针对自对弈棋局样例产生中的选手筛选问题,本文提出了一种将体育赛制(混合赛制、循环赛制、淘汰赛制)和遗传算法结合的学习样例生成算法,来规范选手筛选过程并从而提高高质量样例的产生效率.该算法引入成熟公正的体育赛制组织形式为人工智能选手匹配和淘汰对手,将优胜者之间的对局做为学习样例,并使用遗传变异方法使选手逐代进化.在西洋跳棋上的实验结果表明,本文提出的样例生成算法可以有效产生样例;在样本规模综合指标T的评价下,混合赛制和循环赛制产生的学习样例具有更高质量;基于样例训练的选手能力对比表明,循环赛制最适合于西洋跳棋游戏的样例产生.

The research goal of computer board games is to improve the intelligence of artificial intelligence players,and the representation of learning examples to the chess situation largely determines the intelligence level of players,but the generation of learning examples and the judgment of pros and cons have not attracted enough attention.Aiming at the problem of player selection in the generation of samples from chess games,this paper proposes a learning sample generation algorithm that combines the sports competition system(mixed system,round robin system,knockout system)and genetic algorithm to standardize the selection process of players and improve the production efficiency of high-quality samples.The algorithm introduces a mature and fair organizational form of sports competition,which is artificial intelligence players match and eliminate opponents,takes the match between the winners as a learning example,and uses genetic mutation method to make the players evolve generation by generation.The experimental results on checkers show that the proposed algorithm can produce samples effectively.Under the evaluation of the comprehensive indicator T of sample size,the learning samples produced by the mixed system and the round robin system have higher quality.The comparison of the players′abilities based on the sample training shows that the round robin system is most suitable for the sample generation of checkers.