Date of Award

3-4-2014

Document Type

Thesis

Degree Name

Master of Science in Cyber Operations

Department

Department of Electrical and Computer Engineering

First Advisor

Robert J. McTasney, PhD.

Abstract

Games provide fertile research domains for algorithmic research. Often, game research helps solve real-world problems through the testing and refinement of search algorithms in game domains. Other times, game research finds limits for certain algorithms. For example, the game of Go proved intractable for the Min-Max with Alpha-Beta pruning algorithm leading to the popularity of Monte-Carlo based search algorithms. Although effective in Go, and game domains once ruled by Alpha-Beta such as Lines of Action, Monte-Carlo methods appear to have limits too as they fall short in tactical domains such as Hex and Chess. In a continuation of this type of research, two new games, Crossings and Epaminondas, are presented, analyzed and used to test two Monte-Carlo based algorithms: Upper Confidence Bounds applied to Trees (UCT) and Heuristic Guided UCT (HUCT). Results indicate that heuristic knowledge can positively affect UCT's performance in the lower complexity domain of Crossings. However, both agents perform worse in the higher complexity domain of Epaminondas. This identifies Epaminondas as another domain that poses difficulties for Monte Carlo agents.

AFIT Designator

AFIT-ENG-14-M-44

DTIC Accession Number

ADA599685

Download

Share

COinS