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) 
 
 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

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.