Dr. Sean McCulloch (Department of Mathematics and Computer Science)

Much work has been done in the past on designing Artificial Intelligence (AI) programs to play “classic” board games, such as Chess, Checkers, Othello, and Go. Many of these games have programs that are sufficiently advanced that they beat the best human players (see, for example, Refs. [1-3]). In the last ten to twenty years, however, there has been a rise in “abstract” or “European-style” board games. These differ from the board games many of us have played as children (such as Monopoly or Life) in several areas: (1) the games are typically short, many finishing in 90 minutes or less; (2) the games usually emphasize player interaction in some way (components such as bidding, competing for scarce resources, or trading/negotiation are commonly seen); and (3) the games often are based around hidden information, so that nobody can know the whole state of the game. These factors, especially the last two, make designing an AI for these games a challenge, and so much less has been done analyzing these games, and what has been done has much room for improvement (some examples include Refs. [4, 5], while other game companies have been developing AI programs for sale, usually as mobile apps). I have personally been working on a game-theoretic agent to play the game Football Strategy [6].

In the last REU funding cycle, the students have designed a program for a game called Battle Line [7] that can be viewed as two players playing three-card poker against each other on a field of nine columns. Each column represents a different “hand”, and each turn a player chooses a card to play on any of the nine columns. The game involves aspects of automated theorem proving (if you can prove that your hand is unbeatable, even if the opponent has yet to play a complete hand, you win the hand) and probability (computing the odds that a player will make a winning hand given the cards played and yet to be seen). My plan is to look at some different games that have different underlying structures, and approach them in a similar manner—design an agent that applies existing theoretical knowledge from an area to the structure of the game. The games I’m currently considering include Empire Builder [8], Modern Art [9], and Scotland Yard [10].

References

[1] M. Campbell, A.J. Hoane Jr., F. Hsu, Artificial Intelligence 134, 57 (2002).

[2] J. Schaffer, J. Culberson, N. Treleoar, B. Knight, P. Lu, D. Szafron, Artificial Intelligence 53, 273 (1992).

[3] M. Buro, Artificial Intelligence 134, 85 (2002).

[4] C. Heyden, Master’s Thesis, 2009. [http://www.personnel.unimaas.nl/uiterwijk/Theses/MSc/Heyden_thesis.pdf].