Evolving computer chinese chess using guided learning

Abstract

This chapter explores the feasibility of using genetic algorithms to improve the evaluation of Chinese chess programs. A game engine that uses the negascout search algorithm in combination with internal iterative deepening search is developed. As a means to enhance the search process, techniques such as nullmove- pruning, futility pruning, razoring and selective search extensions are used. Unnecessary expensive re-searches for the negascout are avoided through move ordering techniques, which are governed by the Most Valuable Victim (MVV) / Least Valuable Attacker (LVA), killer and history heuristics. To evaluate the game positions at any point of time, a static evaluation function (using hand-tuned weights) is utilized in conjunction with quiescent search, whose weights are tuned by a genetic algorithm using a population of chromosomes. Moves taken from grandmasters' games are used as training data to evaluate the fitness of chromosomes during evolution. This is determined based on the number of 'correct' moves made by the program. The evolved programs are benchmarked against the un-evolved version and random online human players. Results show that evolution with guided learning does improve the playing strength of the Chinese chess program significantly. © 2009 Springer-Verlag Berlin Heidelberg.