In mid-August, Gettysburg College alumnus Marcin Malec ’13 earned a bronze medal at the Computer Olympiad in Yokohama, Japan. The Olympiad, hosted by the International Computer Games Association, pitted Marcin against five other skilled competitors in The Game of the Amazons (commonly referred to as “Amazons”), considered by many aficionados to be one of the best and deepest abstract strategy games.
Amazons was invented in 1988 by Walter Zamkauskas of Argentina. Michael Keller wrote the first computer program to play Amazons in 1994 (in Fortran with a text interface; a later version was written in Visual Basic). Each player has four Amazons, with queen-like movement reminiscent of Chess and probabilistic area control reminiscent of Go. In play, an Amazon moves any number of vacant squares in a straight line, and after it moves it must fire an arrow in the same manner. The square where the arrow lands is then marked to indicate it is blocked; no amazon or arrow may move into or through a blocked square. The player last able to make a move wins. Perfect play is currently computationally intractable, leaving considerable room for research advances in quality of artificial intelligence (AI) play.
Malec was introduced to Amazons through a course taught by Computer Science Prof. Todd Neller during the spring semester of 2012. The course, CS 391—Selected Topics: Game Artificial Intelligence, was taught so as to bypass many conventional topics and beat a direct path to the current state of research in game artificial intelligence. (A number of the readings had been presented at a conference in the Netherlands the prior fall, but would not be published until the summer after the course.) In the fifth homework assignment, Neller challenged students to create computer Amazons players using an algorithm called UCT, a type of Monte Carlo Tree Search (MCTS) that uses some randomization of simulated play in order to sample and gradually explore promising lines of play in the game tree of all possible plays. Students created Amazons players to battle Neller’s basic sparring bot, a “vanilla” UCT Amazons bot.
Although each student was ultimately conquered by Neller’s player, Malec was driven to see what improvements he might achieve in his own play to defeat his professor in a rematch. Neller shared general research ideas with Malec concerning the introduction of adaptive search behaviors for MCTS, that is, software that could learn to adaptively change its search parameters in reaction to different game conditions. This knowledge, combined with Malec’s adroit and determined application, led to a victory in round two, and ultimately inspired him to become the first student to exercise a new research capstone option for computer science majors. His research, which included reviewing the work of others and investigating enhancements to his player’s adaptive behavior, resulted in artificial intelligence that consistently performed at a high level in simulations. He tuned his AI such that it had strong performance against all available players. Later he added parallelization to allow several computers to work together at the same time to share the evaluation of possible lines of play.
Malec was therefore ready to compete at the Computer Olympiad in Yokohama. There were six total Amazons contestants, three of whom had long experience and success in Computer Olympiad competitions, and three of whom (including Malec) were introducing new players. Given that Marcin was introducing a new entry amidst three competition veterans, two of which have dominated the event throughout its 12 years, and given that Amazon pieces in the game make potentially distant shots across the board, Neller and Malec decided on a pun for naming his AI competition entry: “Long Shot”.
During play, human operators communicated their AI player’s moves to each other verbally, entered each move manually, and tracked player time with chess clocks, allowing 30 minutes of time per player for each game. (Human operators are not allowed to alter their AI player moves or provide any game play expertise to their programs during competition. Decision-making must be entirely autonomous.) Competition was round robin and allowed each contestant to play as both 1st and 2nd player against each other contestant.
The games took place over three days. On the first day, Malec went undefeated in all four games against newcomers and in one game against a veteran player. On the second day, he won his second game against the veteran player, and was then defeated by both veteran players that have taken the gold and silver medals for the past four competitions. In final standings, Malec was awarded the bronze medal, a very respectable first performance at the Computer Olympiad.
In the course of the competition, Malec observed potential improvements to his player, and expressed a hope of improved performance at a future Computer Olympiad. He has been working on such improvements amidst his graduate work on Case Based Reasoning under Prof. David Leake at the University of Indiana at Bloomington.
While in Japan, Malec and Neller also presented at the 8th International Conference on Computer and Games. The pair presented a peer reviewed paper, Optimal, Approximately Optimal, and Fair Play of the Fowl Play Card Game, they collaborated on with Prof. Clifton Presser and Forrest Jacobs ’12. In the future, the paper will be published in the conference proceedings.
Currently, Malec is pursuing his Master’s at Indiana University at Bloomington and plans to enter a Ph.D. program in computer science.
--By Cynthia Helfrich, from source material by Michael Baker and Dr. Todd Neller