Scientists have developed a mathematical model that figures out the best strategy to win a popular board game, which could some day help robot mine sweepers navigate strange surroundings to find hidden explosives.
According to Duke University scientists, who developed the new algorithm, both activities are governed by the same principles at the simplest level.
A player, or robot, must move through an unknown space searching for clues.
In the case of CLUE, the board game, players move a pawn around the board and enter rooms seeking information about the killer and murder weapon before moving on to the next room seeking more information.
“In the same way, sensors, like the pawn in CLUE, must take in information about the surroundings to help the robot maneuver around obstacles as it searches for its target,” said Chenghui Cai, from Duke’s Pratt School of Engineering.
“The key to success, both for the CLUE© player and the robots, is to not only take in the new information it discovers, but to use this new information to help guide its next move,” Cai said.
“This learning-adapting process continues until either the player has won the game, or the robot has found the mines,” he added.
Researchers in the field of artificial intelligence research refer to these kinds of situations as “treasure hunt” problems and have developed different mathematical approaches to improve the odds of discovering this buried treasure.
Games are often used to test or to help illustrate such complex problems, the scientists said.
“We found that the new algorithms we developed can be best illustrated through the board game CLUE, which is an excellent example of the treasure hunt problem,” Cai explained.
“We found that players who implemented the strategies based on these algorithms consistently outperformed human players and other computer programs,” he added.
According to Silvia Ferrari, assistant professor of mechanical engineering and materials science at Duke’s Pratt School of Engineering, “In the game of CLUE, you can’t visit all the rooms by the end of the game, so you need to come up with a way to minimize the amount of movement but maximize the ability to reach your targets.”
“When searching for mines, you want the robot to spend as little time as possible on the ground and maximize its information reward function,” he added.