University:
Boston University
Course:
CAS MA 411 | Advanced Calculus
Academic year:

2021
Views:

271

Pages:

32
Author:

Emery Goodwin

Combinatorial Game Theory Let’s Play a Game Rules of the Game: On your turn, you can take any number of coins provided they all come from the same heap The person who takes the last coin from all the heaps, wins. i.e. there are no coins left Outline 1 What is a Game? 2 Games which are numbers Winning Strategies Simplicity Rule 3 Game of Nim Nim Addition 4 Conclusion What is a Game? 8 rules for Combinatorial Games: 1 Two players, Left and Right 2 Finite many positions, including a starting position 3 Clearly defined rules for players to move from the current position to its options 4 Left and Right alternate in turns 5 Complete information 6 No chance moves 7 In the normal play convention the player unable to move loses 8 There exists an ending condition, i.e. game ends when either player is unable to move Which Games are numbers? Which Games are numbers? G = {a, b, c, ...|d, e, f , ...} Where G is the current position of the game and is determined by the options of the Left and Right players. Which Games are numbers? G = {a, b, c, ...|d, e, f , ...} Where G is the current position of the game and is determined by the options of the Left and Right players. G is a number when a, b, c, ... ≤ d, e, f , ... Winning Strategies If G > 0, there is a winning strategy for Left. If G < 0, there is a winning strategy for Right. If G = 0, there is a winning strategy for the second player. G ||0, there is a winning strategy for the first player. Common Games 0 = {|} which is the ending condition n + 1 = {n|} which is a Left player win −n + 1 = {| − n} which is a Right player win ∗ = {0|0} which is a first player win Simplifying Games To simplify a game, we eliminate dominated options Simplifying Games To simplify a game, we eliminate dominated options If Left has options {-3, 12 , 7}, options −3 and 1 2 would be dominated by 7. If Right had options {-6, -2, 0}, options 0 and 2 would be dominated by −6. Simplicity Rule Definition If all the options for both players of some game G are numbers, and every Left option is less than or equal to every Right option, then G itself is a number, namely the simplest number greater than every Left option and less than every Right option. G= 2p 2p + 2 p p+1 2p + 1 = { n+1 | n+1 } = { n | n } n+1 2 2 2 2 2 Simplicity Rule Definition If all the options for both players of some game G are numbers, and every Left option is less than or equal to every Right option, then G itself is a number, namely the simplest number greater than every Left option and less than every Right option. G= 2p 2p + 2 p p+1 2p + 1 = { n+1 | n+1 } = { n | n } n+1 2 2 2 2 2 A whole number is simpler than 2a . a a 2 is simpler than 4 and so on. The smallest number that satisfies the above is the simplest number. Examples If G = {2|3} Examples If G = {2|3}, then G = 25 . Examples If G = {2|3}, then G = 25 . If G = {−2|2} Examples If G = {2|3}, then G = 25 . If G = {−2|2}, then G = −1. Examples If G = {2|3}, then G = 25 . If G = {−2|2}, then G = −1. If G = { 54 |2} Examples If G = {2|3}, then G = 25 . If G = {−2|2}, then G = −1. If G = { 54 |2}, then G = 32 . Game of Nim Nim is an impartial game. i.e. At every position, both players have the same legal moves. Game of Nim Nim is an impartial game. i.e. At every position, both players have the same legal moves. A nimber, i.e. ?1, ?2, ?3..., represents the number of objects available to the players at every position of the game. Game of Nim Nim is an impartial game. i.e. At every position, both players have the same legal moves. A nimber, i.e. ?1, ?2, ?3..., represents the number of objects available to the players at every position of the game. E.g. The game we played was: G = {?1, ?2, ?3, ?4, ?5, ?6| ? 1, ?2, ?3, ?4, ?5, ?6} Game of Nim Nim is an impartial game. i.e. At every position, both players have the same legal moves. A nimber, i.e. ?1, ?2, ?3..., represents the number of objects available to the players at every position of the game. E.g. The game we played was: G = {?1, ?2, ?3, ?4, ?5, ?6| ? 1, ?2, ?3, ?4, ?5, ?6} Nimbers are their own negatives. i.e. ?1 + ?2 + ?3 = 0 is the same as ?1 + ?3 = ?2 3-Heap Game Facts: A single non-empty heap is fuzzy. Two equal-sized heaps is a zero game. Two unequal-sized heaps is fuzzy. 3-Heap Game Facts: A single non-empty heap is fuzzy. Two equal-sized heaps is a zero game. Two unequal-sized heaps is fuzzy. How to lose in a 3-heap game: Equalize two heaps Empty a heap Nim Addition Table Nim Addition ?10 + ?6 = 12 Nim Addition ?10 + ?6 = 12 Break each nimber into distinct parts whose sizes are powers of 2, beginning with the largest size. Nim Addition ?10 + ?6 = 12 Break each nimber into distinct parts whose sizes are powers of 2, beginning with the largest size. ?10 + ?6 = ?8 + ?2 + ?4 + ?2 Nim Addition ?10 + ?6 = 12 Break each nimber into distinct parts whose sizes are powers of 2, beginning with the largest size. ?10 + ?6 = ?8 + ?2 + ?4 + ?2 ?10 + ?6 = ?8 + ?4 = 12 Conclusion A game is a number if: all the options for both players are numbers every Left option is less than or equal to every Right option G will be the simplest number greater than every Left option and less than every Right option. Conclusion A game is a number if: all the options for both players are numbers every Left option is less than or equal to every Right option G will be the simplest number greater than every Left option and less than every Right option. In the game of Nim: Nimbers are their own negatives In a 3-heap game, the player who equalizes two heaps or empties a heap loses To add nimbers, break each nimber into distinct parts whose sizes are powers of 2 and use arithmetic addition

Combinatorial Game Theory

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock