Tato práce z oblasti Teorie her je zaměřena na hry typu Mancala, konkrétně v západním světě nejrozšířenější variantu - Kalahu. Hlavním cílem této práce je navrhnout a vytvořit aplikaci, která implementuje optimální strategii vedoucí k vítězství v této hře. Na základě analýzy pravidel Kalahy byly navrženy nové strategie s cílem zajistit hráči vítězství v každé herní partii. Tyto strategie byly implementovány v rámci nově vytvořené aplikace pro hraní hry Kalahy a byly vyhodnoceny jejich výkonnosti. Při analýze bylo zjištěno, že výsledek velkou měrou ovlivňuje pozice začínajícího hráče, který může od počátku volit výhodné tahy. Experimenty ukázaly, že lidský hráč v pozici druhého hráče proti některým implementovaným strategiím nedokázal ani jednou vyhrát. Naopak v případě, že začínal, vždy nalezl takovou posloupnost tahů, aby dokázal vyhrát. Obecně lze konstatovat, že navržené strategie mohou konkurovat lidským hráčům.
Annotation in English
This thesis belonging under the umbrella of the Game Theory is focused on games of the Mancala type - namely its most widespread variant in the western world, the Kalah game. The principal goal of this work is to design and create an application implementing a strategy leading to victory in this particular game. Based on the analysis of Kalah rules, we designed a novel winning strategies. This strategies were then implemented within a new Kalah game application and their performance were experimentally evaluated. Our analysis shows that the player who has the initial move usually has a decisive advantage as they can choose the most favorable moves from the very beginning. The experimental evaluation shows that when playing as the second player, the human competitor could not defeat some of the designed strategies at all. On the other hand, with the first move advantage, the human player always found a sequence of moves leading to victory. We conclude that the implemented strategies are able to thoroughly challenge human players.
Tato práce z oblasti Teorie her je zaměřena na hry typu Mancala, konkrétně v západním světě nejrozšířenější variantu - Kalahu. Hlavním cílem této práce je navrhnout a vytvořit aplikaci, která implementuje optimální strategii vedoucí k vítězství v této hře. Na základě analýzy pravidel Kalahy byly navrženy nové strategie s cílem zajistit hráči vítězství v každé herní partii. Tyto strategie byly implementovány v rámci nově vytvořené aplikace pro hraní hry Kalahy a byly vyhodnoceny jejich výkonnosti. Při analýze bylo zjištěno, že výsledek velkou měrou ovlivňuje pozice začínajícího hráče, který může od počátku volit výhodné tahy. Experimenty ukázaly, že lidský hráč v pozici druhého hráče proti některým implementovaným strategiím nedokázal ani jednou vyhrát. Naopak v případě, že začínal, vždy nalezl takovou posloupnost tahů, aby dokázal vyhrát. Obecně lze konstatovat, že navržené strategie mohou konkurovat lidským hráčům.
Annotation in English
This thesis belonging under the umbrella of the Game Theory is focused on games of the Mancala type - namely its most widespread variant in the western world, the Kalah game. The principal goal of this work is to design and create an application implementing a strategy leading to victory in this particular game. Based on the analysis of Kalah rules, we designed a novel winning strategies. This strategies were then implemented within a new Kalah game application and their performance were experimentally evaluated. Our analysis shows that the player who has the initial move usually has a decisive advantage as they can choose the most favorable moves from the very beginning. The experimental evaluation shows that when playing as the second player, the human competitor could not defeat some of the designed strategies at all. On the other hand, with the first move advantage, the human player always found a sequence of moves leading to victory. We conclude that the implemented strategies are able to thoroughly challenge human players.
Popište deskovou hru Mancala a její varianty.
Zpracujte rešerši o existujících desktopových a mobilních aplikacích této hry.
Popište optimální strategie hry Mancala.
Vyberte a popište softwarové nástroje pro vytvoření vlastní aplikace.
Vytvořte aplikaci pro hru Mancala implementující popsané optimální strategie umožňující hrát člověku proti stroji.
Ověřte funkcionalitu a efektivitu vytvořené aplikace.
Research Plan
Popište deskovou hru Mancala a její varianty.
Zpracujte rešerši o existujících desktopových a mobilních aplikacích této hry.
Popište optimální strategie hry Mancala.
Vyberte a popište softwarové nástroje pro vytvoření vlastní aplikace.
Vytvořte aplikaci pro hru Mancala implementující popsané optimální strategie umožňující hrát člověku proti stroji.
Ověřte funkcionalitu a efektivitu vytvořené aplikace.
Recommended resources
BROWN, Seth. How to Win at Mancala? Basic Strategy. The Spruce Crafts \matsymb{lbrack}on-line\matsymb{rbrack}. 27. 9. 2018 \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z: https://www.thesprucecrafts.com/how-to-win-at-mancala-basic-strategy-411832.
Mancala. In: Wikipedia: the free encyclopedia \matsymb{lbrack}online\matsymb{rbrack}. San Francisco (CA): Wikimedia Foundation, 2001-, 30. 9. 2018 \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z: https://en.wikipedia.org/wiki/Mancala.
MAŇAS, Miroslav. Teorie her a optimální rozhodování. Praha: SNTL, 1974.
HYKŠOVÁ, Magdalena. Teorie her a optimální rozhodování. Praha, 2009. Odborná publikace. ČVUT. \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z WWW: http://euler.fd.cvut.cz/predmety/teorie_her/hry.pdf.
HRUBÝ, Martin. Doprovodné texty ke kurzu Teorie her \matsymb{lbrack}online\matsymb{rbrack}. Brno, 2010. \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z: http://www.fit.vutbr.cz/ hrubym/THE/sk-2-nekoo.pdf. Brno University of Technology.
Recommended resources
BROWN, Seth. How to Win at Mancala? Basic Strategy. The Spruce Crafts \matsymb{lbrack}on-line\matsymb{rbrack}. 27. 9. 2018 \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z: https://www.thesprucecrafts.com/how-to-win-at-mancala-basic-strategy-411832.
Mancala. In: Wikipedia: the free encyclopedia \matsymb{lbrack}online\matsymb{rbrack}. San Francisco (CA): Wikimedia Foundation, 2001-, 30. 9. 2018 \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z: https://en.wikipedia.org/wiki/Mancala.
MAŇAS, Miroslav. Teorie her a optimální rozhodování. Praha: SNTL, 1974.
HYKŠOVÁ, Magdalena. Teorie her a optimální rozhodování. Praha, 2009. Odborná publikace. ČVUT. \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z WWW: http://euler.fd.cvut.cz/predmety/teorie_her/hry.pdf.
HRUBÝ, Martin. Doprovodné texty ke kurzu Teorie her \matsymb{lbrack}online\matsymb{rbrack}. Brno, 2010. \matsymb{lbrack}cit. 2018-10-02\matsymb{rbrack}. Dostupné z: http://www.fit.vutbr.cz/ hrubym/THE/sk-2-nekoo.pdf. Brno University of Technology.
