| Meno: | Rastislav
|
|---|
| Priezvisko: | Lenhardt
|
|---|
| Názov: | Composite mathematical games
|
|---|
| Vedúci: | Doc. RNDr. Rastislav Kráµovič, PhD.
|
|---|
| Rok: | 2007
|
|---|
| Kµúčové slová: | Dots and Boxes, composite games, w-numbers
|
|---|
| Abstrakt: | Decomposition of mathematical games to smaller parts is essential because of the
large number of possible positions. We have studied the degenerated variation of the famous Dots and Boxes game where the winner is a player who first creates the first box. This variation is strongly related to the original game and can often help us to find a strategy for the original game. We have found and proved which player has a winning strategy if we start from the initial empty board. For arbitrary positions we found out that the game is being decomposed to the smaller subgames where the winner is a player who wins the first of these subgames.
We have introduced w-function that assigns w-numbers to the positions of subgames and by combining these values we can find the w-number and thus who has a winning strategy in the composite games of this type. These results allow us to find solutions to these games much faster. If n is the size of the subgames and k number of subgames then the complexity is only O(kn) in comparison to O(n^k) obtained by the standard algorithm. We used this general concept to solve the degenerated Dots and Boxes game. However, it can be used in any other games decomposing this way. We have also succeeded to find the way how to play this combination of games with the misére play rule.
The first part contains known ways of adding impartial games with proofs and many examples to help orient in this area. We have also created a combinatorial game API to support and improve conditions in researching the combinatorial games. Almost all these games including the degenerated Dots and Boxes game and algorithms for composite games are implemented in this API.
|
|---|