4. AI Algorithms

Xiangqi, just as the orthodox Chess, is one of the games with 'perfect information', where both players know the complete state of the board at any time during the game. Therefore, basic techniques for implementing a orthodox chess computer player can be used in this project.

The difficulty in implementing an intelligent agent for Xiangqi, however, lies in the fact that the number of valid moves and possible board positions are greater than in the orthodox chess. Especially, a very powerful technique using 'bitboards' can not be used, where each bit value in a 64-bit long data type represents one of the 64 board positions, since Xiangqi requires 9 x 10 = 90 positions. In order to have reasonably acceptable performance, the computer player is designed such that it is very flexible to add, remove, or modify the algorithms.

        4.1 UML Diagram

In Single Player Mode, a PlayerAI object instantiates a variation of an AISearchAgent with different parameters depending on the difficulty level chosen by the user. Using the Strategy design pattern, Online Xiangqi implements two types of such agents using different search techniques: the iterative alphabeta pruning algorithm and the MTD(f) algorithm.

In order to speed up the search, two tables are provided to the search agent: the transposition table and the history table. A transposition table is a repository of past search results that the agent can query and bypass a search if a suitable entry is stored for a specific position. The history table, implemented as a Singleton pattern,  is a simple 90 x 90 array of integer counters; when the search algorithm decides that a certain move has proven useful, it will ask the history table to increase its value.  The values stored in the table will then be used to sort moves and make sure that more historically powerful ones will be tried first

Move generation is done primarily by accessing pre-processed move sequences using the methods in the MoveListGenerator class. Board evaluation at a particular state is carried out by the BoardEvaluator object, with a simpler but faster material value method, that merely adds up relative scores on what pieces the player has, and an evaluate function that implements a more elaborate but slower evaluation function.