Title page for ETD etd-04202011-170529

Type of Document

Master's Thesis

Author

Cherry, Kevin Anthony

Author's Email Address

kcherr1@tigers.lsu.edu

URN

etd-04202011-170529

Title

An Intelligent Othello Player Combining Machine Learning and Game Specific Heuristics

Degree

Master of Science in Systems Science (M.S.S.S.)

Department

Computer Science

Advisory Committee

Advisor Name	Title
Chen, Jianhua	Committee Chair
Baumgartner, Gerald	Committee Member
Kooima, Robert	Committee Member

Keywords

genetic algorithm
heuristics
Othello
computer game playing
expected min
influence map
minimax
neural network

Date of Defense

2011-03-04

Availability

unrestricted

Abstract

Artificial intelligence applications in board games have been around as early as the 1950's, and computer programs have been developed for games including Checkers, Chess, and Go with varying results. Although general game-tree search algorithms have been designed to work on games meeting certain requirements (e.g. zero-sum, two-player, perfect or imperfect information, etc.), the best results, however, come from combining these with specific knowledge of game strategies.
In this MS thesis, we present an intelligent Othello game player that combines game-specific heuristics with machine learning techniques in move selection. Five game specific heuristics, namely corner detection, killer move detection, blocking, blacklisting, and pattern recognition have been proposed. Some of these heuristics can be generalized to fit other games by removing the Othello specific components and replacing them with specific knowledge of the target game. For machine learning techniques, the normal Minimax algorithm along with a custom variation is used as a base. Genetic algorithms and neural networks are applied to learn the static evaluation function. The five game specific techniques (or a subset of) are to be executed first and if no move is found, Minimax game tree search is performed. All techniques and several subsets of them have been tested against three deterministic agents, one non-deterministic agent, and three human players of varying skill levels. The results show that the combined Othello player performs better in general. We present the study results on the basis of four main metrics: performance (percentage of games won), speed, predictability of opponent, and usage situation.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	Thesis.pdf	1.23 Mb	00:05:42	00:02:56	00:02:34	00:01:17	00:00:06