Sean Doyle takes the `Knight's Tour'
At first it sounds like an amusing and pointless parlor game: what sequence of moves will permit a knight to visit each of the 64 squares on a chessboard only once?
Chess, of course, never strays far from mathematics, as Sean Doyle, a master’s student in computer science (CS) at Rice University, demonstrates in his work with the Knight’s Tour problem.
“The Knight’s Tour will help us improve the approximate model counter that was developed, in part, here at Rice. This will improve our progress on efficiently counting the solutions to satisfiability problems,” said Doyle, who graduated with a B.A. in C.S. in 2016. Doyle was awarded a Graduate Research Fellowship by the CS department, and with it he is spending a fifth year at Rice, further investigating satisfiability problems.
“The research I’m going to be working on over the next year for my master’s is on parallelizing an approximate counter developed earlier by [fourth-year Ph.D. student] Kuldeep Meel,” Doyle said. “That will be in the works over the next year.”
Doyle works closely with Moshe Y. Vardi, the Karen Ostrum George Distinguished Service Professor in Computational Engineering, one of the researchers pioneering the field of approximate model counting—that is, computing the number of models for a given propositional formula.
“The idea is to approximate the number of solutions to a given problem,” Doyle said. To understand the complexity, consider that on an eight-square-by-eight-square chessboard there are approximately 4×1051 possible move sequences that satisfy the Knight’s Tour problem. “You can see why an approximate solution is important. Otherwise, you’re overwhelmed with solutions. Precision isn’t always important. We want a good ballpark figure.”
In his junior year at Rice, Doyle joined a small team of students working on the Knight’s Tour problem—“unsolved since the 10th century,” he notes. “This had the effect of improving the approximate model counter used by our team, so we could tackle the problem of counting satisfactory assignments within a given tolerance. It gave us the confidence to mitigate the complexity of finding an exact answer.”
Though rarified and highly theoretical, such research has important applications in artificial intelligence and probabilistic inference. Doyle said the tour counter developed by his team ran into issues and could not return a timely answer because the problem itself is so large. “This acted as a phenomenal example for why we want to parallelize the counter to work more efficiently,” said Doyle.
Running the problem in parallel returns “probabilistically accurate results in a fraction of the time for an exact result,” Doyle said. “Anywhere that counting problems can grow, like artificial intelligence or probabilistic inference, you may find use for an approximate result returned in a much shorter time.”
Doyle credits his mentor with encouraging him to continue his research. “Moshe’s been a great asset in my ongoing attempts to really get into the ideas of research,” he said. “He’s the one who convinced me to apply for the research fellowship, and I will be thanking him for that for years to come.”
Doyle remains uncertain whether he will go on to seek a Ph.D. Once convinced he wanted to go into teaching, now he also considers going directly into industry. “Wanting to go into teaching would definitely put me in the minority at Rice, but I like the idea of doing research and at the same time teaching students. They go together naturally. I know, because I’ve had some outstanding teachers, here at Rice and elsewhere,” Doyle said.