An educational research challenge based on a game of cards inspired Florida Southern’s Dr. Christian Roberson to apply for a summer 2018 collaboration grant with student Katarina Sperduto.
Their resulting work in the areas of artificial intelligence (AI), algorithms, and machine learning led to the submission of a scholarly paper and an invitation for the student/faculty duo to present their findings at a major AI conference in Honolulu, Hawaii.
What’s the deal? It’s deceptively simple. A variation on the card game Solitaire, called Birds of a Feather, was at the heart of their research. Played with just 16 randomly selected playing cards, laid out in a four-by-four grid, the game was specially created to afford computer science researchers with a new, untested area of study.
Dr. Roberson, assistant professor of Computer Science and the department’s chair, collaborated on the Birds of a Feather research challenge with Katarina, who will graduate in May 2019 with a double major in Mathematics and Computer Science. The focus of their work involved the development of an AI player that could effectively determine the solvability of any configuration of cards.
“The objective is to reduce the 16 cards to a single pile of cards,” Dr. Roberson explained, by moving the cards individually to cover similar suits or ranks. According to the rules of the game, cards may only be stacked within a shared row or column. “As you reduce the number of cards, you lose places where the cards can be moved. So we developed code to identify states that are unsolvable.”
The pair developed a computer program that played through a large number of simulated games, keeping track of each possible move to determine whether or not a game could be solved, and to identify a possible sequence of winning moves. They found that by simulating 400 games and tracking each possible move, the AI player was able to win roughly 95 percent of the time. Boosting the number of simulated games to 4,000 increased the player’s effectiveness, improving its win rate to 99.8 percent.
Dr. Roberson and Katarina submitted their research paper, “A Monte-Carlo Tree Search Player for Birds of a Feather Solitaire,” to the Ninth Symposium on Educational Advances in Artificial Intelligence (EAAI-19). It was accepted for presentation at the Honolulu conference in late January 2019, where Katarina gave a 13-minute presentation of their findings. The duo also received the Best Paper Award (Runner-Up) in the research challenge track.
“I thought the entire experience was amazing!” Katarina said. “It was great to get involved in undergrad research, which helped with my programming, problem-solving, and professional paper-writing skills, and attending and presenting at the conference helped with my presentation skills, as well.”