21st of October - Alessandro Zocca (VU Amsterdam)
Title: Ready, SET, go: Improving card game strategies with hypergraphs and a little help from AI
Abstract: Interested in combinatorics, finite geometry, or optimization under uncertainty? The card game SET has all three and connects them in unexpected ways!
Deal twelve cards in SET, keep removing SETs and drawing new cards: can you clear the entire deck? Playing at random, you succeed in about one game in a hundred. In his bachelor's thesis, Maciek Sidor (a former BSc math student here at the VU) recast the problem in terms of hypergraph matchings on a finite geometry. In simulations, his best strategy clears the table in about 46% of games, more than double the best previously known strategy. How well an optimal strategy can do, without knowing the future deal order, remains unknown.
His strategies motivated my follow-up research into better algorithms and yielded a surprising result: maximizing the number of surviving partitions into SETs does not always maximize the chance of clearing the table! Alongside the mathematics, I will briefly show how I used AI tools to extend the C++ simulator, interpret extensive experiments, develop and check mathematical arguments, and prepare the very slides you will be watching. The talk covers both the results and the process. No familiarity with the game SET is assumed.