CHAPTER 1

1. INTRODUCTION

Computer Game Playing is one of the oldest areas of endeavor in Artificial Intelligence. However, most research in Computer Game-Playing has been focused on a small number of specific games (most notably chess, checkers, backgammon, Othello and go). The result has been the development of programs capable of playing a single game very well, yet can play no other. Not enough research has been done in the way of general game playing. There is a need for more research on a general theory of game playing, in particular theory that is suitable for implementation. This paper is a step in that direction.

This paper defines an original class of games, called Simple War Games. This class includes both deterministic and non-deterministic games. This class contains games that are comparable in complexity to checkers and chess. This paper also describes several example games.

We developed the program WAR, which is capable of playing any Simple War Game. The program uses a unique algorithm, which we created to evaluate moves in Simple War Games. The program also has a learning component that uses a genetic algorithm. This paper describes the evaluation algorithm and the results of the learning process.

The thesis is organized in the following manner. Chapter 2 examines the area of computer game playing. Chapter 3 introduces the class of games called Simple War Games. Chapter 4 describes WAR, a program to play Simple War Games. Chapter 5 presents the results of several runs of WAR on different games and gives an analysis of its performance. Chapter 6 relates our program to other programs capable of playing more than a single game. Chapter 7 concludes with a summary of the thesis contributions and presents direction for future research.

The Appendices contain the following information: Appendix A describes the parameters required to define a specific Simple War Game instance. Appendix B is a description of four sample games SIMPLE, KING, CHESSLIKE, TANK. Appendix C contains descriptions for several games mentioned in the thesis.