Introduction

Game player strategies have been investigated extensively throughout the generations. Strategies developed have usually been problem specific, and researchers have invested comparatively little time in developing methods that duplicate human procedures. This paper studies the very well known game of chess, which has relatively simple rules but difficult to master and has had many past matches published that can be used as resources for the inference. The area of chess and chess research is very wide with numerous papers and books written on the subject. Many papers that analyse different aspects of the game have been published, covering opening moves, positional play, attacking play, endplay, etc.[2]. The mere fact that so much can be written on a game, having so few rules, is a statement about its complexity and a reason why there is intense interest in developing intelligent computer systems, which determine the best move. A problem with brute force techniques is, their progressive depth and intensity creates diminished returns in performance [19][30]. This means more intelligent programs must be generated if greater efficiency gains are to be made.

The aim is to look at a set of games and then be able to infer the strategy used in deciding which move to make. The object of this paper is to find enough distinguishing factors, in the various methods people approach the game of chess; to ascertain, from just the data, the strategy they used. This is a difficult problem, it simulates reading a person's mind, as it means the evaluation functions and/or the search strategy must be inferred to get an idea of what an individual is most likely to do, given a particular circumstance. This makes the problem of finding brute force techniques for playing games comparatively easy [35]. It is hoped that the procedures used in this treatise could then be used for other areas to help find the strategies employed there. This would be useful in areas, as in the game 'Go', where few computer players can match a master player. In general, it would be useful to be able to find a strategy for any problem that requires a large domain of possible choices. The larger the realm of possibilities, the greater the time required to find the best choice, and hence a good search strategy can then reduce the time required, while still finding the best alternative.

This paper also attempts to give more insight into the field of Artificial Intelligence (AI) by developing a program that actually elaborates understanding of the strategies that are being used, rather than implementing the classic brute force techniques. Algorithms such as M* have been shown to work quite well and even better than that of the minimax algorithm for chess (currently one of the best brute force algorithms), provided that the opponent's strategy is known [4]. M* is a minimax algorithm that instead of using the same method of evaluation for both the current player and the opponent, it uses the opponents strategy when evaluating the opponents moves. This means that the knowledge of an opponent's strategy is very important and the focus of this thesis.
[4] The main problem with current computer programs is that they use a relatively inefficient way of searching through the search space [21]. They generally use a dumb scan that looks at all the possibilities, but might have some way of stopping a search down a useless path. Programs, like Hoyle that are able to play up to 18 different games, among them being Lose Tic-Tac-Toe and Achi and use only shallow search strategies, have been shown to mimic human strategies a lot closer than deep game tree searches and have demonstrated the ability to become expert in the different games [26].

This paper will look firstly at the previous work done by Jansen et al. and then expand on it. The initial stage examines the simple inference model and then the more advanced one to four ply quiescent model. This is where some extra work is performed to show the fitness of the model between different chessmasters. From here, in looking at the strategy which is actually used, a completely different area will be examined. This involves the generation of five strategies and then inferring which of these was most likely implemented in a particular game. An analysis is then carried out on the accuracy required in inferring evaluation functions when finding a search strategy. This will then move onto the inference with chessmasters and finding the depth that they go to.