Bakalářská práce se zabývá aplikací teorie grafů na stolní hry a puzzle. Také mapuje téma stolních her s cílem popsat hru s pomocí teorie grafů, vytvoření grafového modelu hry a zodpovězení otázky, zda je teorie grafů efektivním nástrojem pro nalezení výherní, nebo alespoň efektivní strategie. Hry vybrané pro tuto bakalářskou práci jsou Carcassone a Sedm Draků. Bakalářská práce také bude obsahovat specifikování částí teorie grafů, které budou použity k dosažení jejích cílů.
Anotace v angličtině
The thesis is dealing with an application of graph theory on board games and puzzles. It also maps the board game theme with goals of describing the game with graph theory, creating graph model of the game and answering the question, if the graph theory is an effective tool for finding of winning, or at least effective strategy. The games selected for the thesis are Carcassone and the Seven Dragons. The thesis will also contain specification of the parts of graph theory, which will be used to reach goals of the thesis.
Klíčová slova
Teorie Grafů, Efektivní strategie, Stolní hry, Carcassone, Sedm Draků
Bakalářská práce se zabývá aplikací teorie grafů na stolní hry a puzzle. Také mapuje téma stolních her s cílem popsat hru s pomocí teorie grafů, vytvoření grafového modelu hry a zodpovězení otázky, zda je teorie grafů efektivním nástrojem pro nalezení výherní, nebo alespoň efektivní strategie. Hry vybrané pro tuto bakalářskou práci jsou Carcassone a Sedm Draků. Bakalářská práce také bude obsahovat specifikování částí teorie grafů, které budou použity k dosažení jejích cílů.
Anotace v angličtině
The thesis is dealing with an application of graph theory on board games and puzzles. It also maps the board game theme with goals of describing the game with graph theory, creating graph model of the game and answering the question, if the graph theory is an effective tool for finding of winning, or at least effective strategy. The games selected for the thesis are Carcassone and the Seven Dragons. The thesis will also contain specification of the parts of graph theory, which will be used to reach goals of the thesis.
Klíčová slova
Teorie Grafů, Efektivní strategie, Stolní hry, Carcassone, Sedm Draků
Hlavním cílem práce je zodpovědět otázku "Které hry (a hlavolamy) a které partie teorie grafů je
možné spolu provázat?", přičemž sledována budou tři základní hlediska výběru her:
a) hry, kde v pozadí (v herním mechanismu) je teorie grafů
b) hry, ke kterým lze vytvořit grafový model
c) hry, kde nám teorie grafů umožňuje najít výherní (nebo efektivní) strategii
Osnova:
1) provést rešeršní činnost vzhledem ke známým oblastem hlavolamů a stolních her, ve kterých se teorie grafů již využívá (sudoku, šachové hlavolamy, "Loydova patnáctka", bludiště a další);
2) zmapovat oblast stolních her s cíli:
popsat danou hru jazykem teorie grafů,
vytvořit grafový model dané hry,
zodpovědět otázku, zda je teorie grafů vhodným nástrojem pro nalezení výherní (nebo alespoň efektivní) herní strategie.
Jako základ lze volit hry: Carcassone, mlýn (Nine men's moris) včetně jeho modifikací, Sedm
draků;
3) specifikovat vybrané partie teorie grafů, které se uplatní při plnění jednotlivých cílů, do ucelené
formy;
4) demonstrovat pro každou kategorii her zapojení teorie grafů;
5) popsat oblasti, kterými se může ubírat další výzkum;
Zásady pro vypracování
Hlavním cílem práce je zodpovědět otázku "Které hry (a hlavolamy) a které partie teorie grafů je
možné spolu provázat?", přičemž sledována budou tři základní hlediska výběru her:
a) hry, kde v pozadí (v herním mechanismu) je teorie grafů
b) hry, ke kterým lze vytvořit grafový model
c) hry, kde nám teorie grafů umožňuje najít výherní (nebo efektivní) strategii
Osnova:
1) provést rešeršní činnost vzhledem ke známým oblastem hlavolamů a stolních her, ve kterých se teorie grafů již využívá (sudoku, šachové hlavolamy, "Loydova patnáctka", bludiště a další);
2) zmapovat oblast stolních her s cíli:
popsat danou hru jazykem teorie grafů,
vytvořit grafový model dané hry,
zodpovědět otázku, zda je teorie grafů vhodným nástrojem pro nalezení výherní (nebo alespoň efektivní) herní strategie.
Jako základ lze volit hry: Carcassone, mlýn (Nine men's moris) včetně jeho modifikací, Sedm
draků;
3) specifikovat vybrané partie teorie grafů, které se uplatní při plnění jednotlivých cílů, do ucelené
formy;
4) demonstrovat pro každou kategorii her zapojení teorie grafů;
5) popsat oblasti, kterými se může ubírat další výzkum;
Seznam doporučené literatury
Bockholt, M., & Zweig, K. A. (2015). Why Is This So Hard? Insights from the State Space of a Simple Board Game. In S. Göbel, M. Ma, J. B. Hauge, M. F. Oliveira, J. Wiemeyer, & V. Wendel (Eds.), Serious Games First Joint International Conference, JCSG 2015, Huddersfield, UK, June 34, 2015, Proceedings. Cham Heidelberg New York Dordrecht London: Springer International Publishing Switzerland.
Bockholt, M. (nd). A Network Analytic Approach for Exploring The Complexity of Rush.
Dostupné z: http://gtna.informatik.unikl.de/gruppe/bockholt/PDFs/ Bockholt_Summary.pdf
Felgenhauer, B., & Jarvis, F. (2005). Enumerating possible Sudoku grids. Dostupné z: http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf
Gymrek, M. (2009). Board Game Topics: Analysis Using Graph Theory. Dostupné z: http://web.mit.edu/mgymrek/Public/boardgames.pdf
Vejmola, S. (1986). Konec záhady hlavolamů. Praha: SPN.
Seznam doporučené literatury
Bockholt, M., & Zweig, K. A. (2015). Why Is This So Hard? Insights from the State Space of a Simple Board Game. In S. Göbel, M. Ma, J. B. Hauge, M. F. Oliveira, J. Wiemeyer, & V. Wendel (Eds.), Serious Games First Joint International Conference, JCSG 2015, Huddersfield, UK, June 34, 2015, Proceedings. Cham Heidelberg New York Dordrecht London: Springer International Publishing Switzerland.
Bockholt, M. (nd). A Network Analytic Approach for Exploring The Complexity of Rush.
Dostupné z: http://gtna.informatik.unikl.de/gruppe/bockholt/PDFs/ Bockholt_Summary.pdf
Felgenhauer, B., & Jarvis, F. (2005). Enumerating possible Sudoku grids. Dostupné z: http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf
Gymrek, M. (2009). Board Game Topics: Analysis Using Graph Theory. Dostupné z: http://web.mit.edu/mgymrek/Public/boardgames.pdf
Vejmola, S. (1986). Konec záhady hlavolamů. Praha: SPN.