Othello Game with A.I. Player

Othello Game with A.I. Player

Introduction

This program is a dialogable Othello game so that a human player can play Othello and have conversation with A.I. player during the game. The dialogable feature is motivated from a real-world game environment in which a human expresses something about the way the game is going. You can imagine a human player expressing glee, frustration, surprise, amazement, etc. So, why not A.I. player have this human touch as well? Both game playing engine and natural-language engine have been one of the mainstream of the development in the field of artificial intelligence. In this program, however, both of them have very limited capability since the main goal of the program is to demonstrate how they can be accomplished and motivate ourselves for further developments. Once again, it may be the simplest one to show the techniques for searching and natural-language interface.

Techniques

The A.I. engine uses famous minimax searching technique. The minimax algorithm is a method to minimize the expected maximum loss in alternate moves. For example, suppose that you are in max move and the opponent is in min move. So, you may want to play in the way the opponent - min has as large scores as possible whereas the opponent prefers the way you -"max" earn as low scores as possible. The algorithm, so called minimax, is a key technique for A.I. engine in 2 person zero sum game such as Checkers, Chess, Chinese Chess, and most of other board games or two player games. And also, it is commonly used in more complex games as well as general decision making application in the presence of uncertainty.

The A.I. player looks for all successors that are qualified by two properties: first, moving should be made in a free cell and, second, moving should be legally made in any of the free cells by flanking the opponents discs. Then, for each successor, the A.I. player applies minimax searching along with Alpha-Beta pruning with a given maxply - the maximum depth for searching tree. And also, to increase the tendency of cutoffs in Alpha-Beta pruning, at each non-leaf level of the search tree, the search algorithm sorts all successors in the best-first order by calculating the static value of the each node. For the evaluation function, the A.I. engine uses the static weight of each cell, so each disc gets different weight depending on the cell that it occupies. Then, at each turn, the sum of all weights becomes a players score; of course, it dynamically changes since discs may be flipped over by the opponents move at every turn. In fact, for A.I. player, the static-value evaluation function might be more important than any searching algorithm, and it's a key for how A.I. can play better. Although there might be tens of ways to invent an evaluation function, just like every human player has his/her own playing strategy, this program uses a stupid one because I myself is a newbie to Othello.

The natural language interface uses a combination of Linneous parsing approach and Eliza-like production rules - Eliza is the A.I. dialog program developed at MIT by J.Weizenbaum and his companies in 1966. A board game is more likely to have fixed-format command than descriptive commands. Therefore, Linneous parsing approach is considered appropriate for the commands and queries. In addition, Eliza-like production rules are used for the dialog environment.

Source Codes

The program is written in Python and consists of two source files: GameInterface.py, Othello.py, or download zipped file

How to execute the program: First, you need to have Python installed on your system. Download Python for Window, Linux, Mac. If you have Python installed on your system, just double-click on GameInterface.py or run the file under Python IDLE whose shortcut must have been placed in a program group in the start menu of Windows.

Sample Session - see screen shot

Instructions

To execute the program, just double-click on GameInterface.py or run the file under Python IDLE.
Once the program starts, you can freely have conversation with A.I. player.
To start a game, just tell A.I. player something like Let's play a game, I want to start a game, etc.
Once the game starts, you can play the game by saying something like "Place a disc at d, 3, Put a piece at c 2, or more preferably just c 2. Note that the indecies of row and column MUST be separated by a SPACE whether or not it is separated by a comma.
For display options, you can say something like:
Show my move - display the indices of movements that you and A.I player just made
Show the statistics - display the statistics of searching that A.I. performed for its move.
Show the search time - display the time taken for A.I. to search a best-move
Show the maxply - display the maximum depth of searching tree that A.I. look for
Set the maxply to 3 - the lower maxply is set, you may have higher tendency to win over A.I.
To exit the game or program, you may say Bye, Quit, etc.

Note that you don't have to say exactly like the examples shown above. Test yourself whether A.I. player understands what you say.

Limitations and Improvements

Since this program is to demonstrate a dialogable 2 person zero sum game, both ends of the capabilities of game and dialog are quite limited. The A.I. player cannot search with more than the maxply of 10 in reasonable time; but, its smart enough to beat a pretty good human player. Moreover, the natural language interface can interpret only fixed-format patterns, not grammatical patterns with augmented transition network. Definitely, the next move should be on the development of a GUI version of the program using Tkinter module in Python. In addition, the natural language interface deserves infinitely many improvements as we all computer scientists look for. Finally, a variation of Alpha-Beta search algorithm can be implemented so that the A.I. player can search faster with greater maxply to beat better human player or even another A.I player

by Hyung-Joon Kim, CSE 415, University of Washington