Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Gry, mechanizmy i sieci społ.


Game of Hex - Solving 10x10 board

Seminarium Gry, Mechanizmy i Sieci Społeczne

Prelegent: Jakub Pawlewicz

2015-10-29 12:15

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.