Game of Hex - Solving 10x10 board

Prelegent(ci)

Jakub Pawlewicz

Afiliacja

Instytut Informatyki, Wydział MIM UW

Termin

29 października 2015 12:15

Pokój

p. 3320

Seminarium

Seminarium „Gry, mechanizmy i sieci społeczne”

---

Hex is a famous board game with very simple rules invented by Piet Hein in 1942 and independently by John Nash in 1948. Since finding a winning strategy is PSPACE-complete it is unlikely that we will find it. However, for this game many theories were developed. On the last decade, research made by University of Alberta games group produced a computer program which was able to solve board sizes up to 9x9 (with swap rule) and 10x10. Also very strong program was developed. In this talk main ideas will be presented: virtual connections and inferior cell analysis. Computing virtual connections is an automated way of solving smaller subgames and composing them into larger subgames. Inferior cell analysis allows to prune many moves from consideration for game tree search algorithms.

---