狠狠撸

狠狠撸Share a Scribd company logo

Euler Getter

?
?
Takehiko Yasuda
Takehiko Yasuda

This document introduces Euler Getter (EG), a topological game invented by Takehiko Yasuda. EG is played on a projective plane board with 10 cells. Two players take turns coloring cells red or blue until the board is filled. The player with the larger Euler characteristic of their colored area wins. The first player has a winning strategy if the number of cells is even. The document discusses tactics, implementations, problems with EG, and proposes a variant called Stringy Euler Getter played on a torus board.

1 of 46
Download to read offline
Introduction to Euler Getter Takehiko Yasuda (Osaka Univ.) Mathematical Software and Free Documents XV
What is EG (Euler Getter) ? a game introduced by Y. (2010) Other games with Features the feature topological Hex, Minor, Shapley (connection) territory Go, Reversi (Othello)
Hex the ?rst topological game invented by Piet Hein and reinvented by John Nash (1940s)
Hex variants ? Milnor (or Y) ? Shapley (or Projective Plane, Projex) ? many others
EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1
EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1 ?real projective plane like Shapley
EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1 ?real projective plane like Shapley ?each vertex three edges.
EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1 ?real projective plane like Shapley ?each vertex three edges.
EG Rules
EG Rules ? Two players: Red and Blue
EG Rules ? Two players: Red and Blue ? Take turns coloring a cell red or blue, until all cells are colored.
EG Rules ? Two players: Red and Blue ? Take turns coloring a cell red or blue, until all cells are colored. ? The winner is the one whose area has larger Euler characteristic.
Euler characteristic A : area consisting of cells on a EG board ??e(A) Z : its Euler characteristic
Euler characteristic A : area consisting of cells on a EG board ??e(A) Z : its Euler characteristic e(A) := #{vertices} - #{edges} + #{cells}
Euler characteristic A : area consisting of cells on a EG board ??e(A) Z : its Euler characteristic e(A) := #{vertices} - #{edges} + #{cells} = #{connected components} - #{loops} ← human-friendly
Example e(A) = #{connected components} - #{loops} Q: What are the Euler characteristics of RED and BLUE?
Example e(A) = #{connected components} - #{loops}
Euler characteristic as a measure Inclusion-exclusion principle: e(X Y) = e(X) + e(Y) - e(X Y) The idea came from the motivic integration.
Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1
Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw!
Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts
Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts ?P? is closed and unorientable.
Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts ?P? is closed and unorientable. ? Red Blue = disjoint loops
Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts ?P? is closed and unorientable. ? Red Blue = disjoint loops ? e(loop) = 0
Winning Strategy Theorem (Schnell) If #{cells} is even, then the ?rst player has a winning strategy.
Winning Strategy Theorem (Schnell) If #{cells} is even, then the ?rst player has a winning strategy. Proof Strategy-stealing argument
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ...
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point)
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point)
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch)
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch) ? 凝り (lump)
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch) ? 凝り (lump) ? 安息地 (haven)
Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch) ? 凝り (lump) ? 安息地 (haven) ? 渋田止め (Shibuta block)
Implementations In chronological order, ? Euler Getter 1 (Y., Haskell) ? Web Euler Getter (motemen, Perl+JavaScript) ? E2G2 (Hashimoto, Maxima, AI) ? Euler Getter 2 (Y., Python, AI) ? Euler Getter 2 wrapper (Numata, Python, AI)
Implementations In chronological order, ? Euler Getter 1 (Y., Haskell) ? Web Euler Getter (motemen, Perl+JavaScript) ? E2G2 (Hashimoto, Maxima, AI) ? Euler Getter 2 (Y., Python, AI) ? Euler Getter 2 wrapper (Numata, Python, AI) The Monte-Carlo method works well. (Or humans are still too weak.)
Problems
Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.)
Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.) ? Is the reversed rule better?
Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.) ? Is the reversed rule better? ? Di?cult to explain rules to the general public
Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.) ? Is the reversed rule better? ? Di?cult to explain rules to the general public ? No iOS or Android implementation
S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide
S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane
S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane ? each cell has an assigned score (randomly at the beginning)
S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane ? each cell has an assigned score (randomly at the beginning) ? compete on: Euler char. + the sum of scores (+ Komi)
S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane ? each cell has an assigned score (randomly at the beginning) ? compete on: Euler char. + the sum of scores (+ Komi) Algebro-geometric interpretation torus + scores = log elliptic curve Euler char. + scores = stringy Euler number
References ? Euler Getter Wiki: http://www14.atwiki.jp/euler_getter/ ? My homepage: http://takehikoyasuda.jimdo.com/

More Related Content

Euler Getter

  • 1. Introduction to Euler Getter Takehiko Yasuda (Osaka Univ.) Mathematical Software and Free Documents XV
  • 2. What is EG (Euler Getter) ? a game introduced by Y. (2010) Other games with Features the feature topological Hex, Minor, Shapley (connection) territory Go, Reversi (Othello)
  • 3. Hex the ?rst topological game invented by Piet Hein and reinvented by John Nash (1940s)
  • 4. Hex variants ? Milnor (or Y) ? Shapley (or Projective Plane, Projex) ? many others
  • 5. EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1
  • 6. EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1 ?real projective plane like Shapley
  • 7. EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1 ?real projective plane like Shapley ?each vertex three edges.
  • 8. EG Board 1 2 3 4 6 7 8 5 5 9 10 6 4 3 2 1 ?real projective plane like Shapley ?each vertex three edges.
  • 10. EG Rules ? Two players: Red and Blue
  • 11. EG Rules ? Two players: Red and Blue ? Take turns coloring a cell red or blue, until all cells are colored.
  • 12. EG Rules ? Two players: Red and Blue ? Take turns coloring a cell red or blue, until all cells are colored. ? The winner is the one whose area has larger Euler characteristic.
  • 13. Euler characteristic A : area consisting of cells on a EG board ??e(A) Z : its Euler characteristic
  • 14. Euler characteristic A : area consisting of cells on a EG board ??e(A) Z : its Euler characteristic e(A) := #{vertices} - #{edges} + #{cells}
  • 15. Euler characteristic A : area consisting of cells on a EG board ??e(A) Z : its Euler characteristic e(A) := #{vertices} - #{edges} + #{cells} = #{connected components} - #{loops} ← human-friendly
  • 16. Example e(A) = #{connected components} - #{loops} Q: What are the Euler characteristics of RED and BLUE?
  • 17. Example e(A) = #{connected components} - #{loops}
  • 18. Euler characteristic as a measure Inclusion-exclusion principle: e(X Y) = e(X) + e(Y) - e(X Y) The idea came from the motivic integration.
  • 19. Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1
  • 20. Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw!
  • 21. Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts
  • 22. Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts ?P? is closed and unorientable.
  • 23. Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts ?P? is closed and unorientable. ? Red Blue = disjoint loops
  • 24. Euler characteristic as a measure In EG, if the board is ?lled, e(Red) + e(Blue) = e(P?) = 1 e(Red) e(Blue); No Draw! Key Facts ?P? is closed and unorientable. ? Red Blue = disjoint loops ? e(loop) = 0
  • 25. Winning Strategy Theorem (Schnell) If #{cells} is even, then the ?rst player has a winning strategy.
  • 26. Winning Strategy Theorem (Schnell) If #{cells} is even, then the ?rst player has a winning strategy. Proof Strategy-stealing argument
  • 27. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ...
  • 28. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point)
  • 29. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point)
  • 30. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch)
  • 31. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch) ? 凝り (lump)
  • 32. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch) ? 凝り (lump) ? 安息地 (haven)
  • 33. Tactics and terminology Miura, Sannai, Shibuta, Tiba, ... ? 鋭点 (acute point) ? 鈍点 (blunt point) ? 竦み (?inch) ? 凝り (lump) ? 安息地 (haven) ? 渋田止め (Shibuta block)
  • 34. Implementations In chronological order, ? Euler Getter 1 (Y., Haskell) ? Web Euler Getter (motemen, Perl+JavaScript) ? E2G2 (Hashimoto, Maxima, AI) ? Euler Getter 2 (Y., Python, AI) ? Euler Getter 2 wrapper (Numata, Python, AI)
  • 35. Implementations In chronological order, ? Euler Getter 1 (Y., Haskell) ? Web Euler Getter (motemen, Perl+JavaScript) ? E2G2 (Hashimoto, Maxima, AI) ? Euler Getter 2 (Y., Python, AI) ? Euler Getter 2 wrapper (Numata, Python, AI) The Monte-Carlo method works well. (Or humans are still too weak.)
  • 37. Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.)
  • 38. Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.) ? Is the reversed rule better?
  • 39. Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.) ? Is the reversed rule better? ? Di?cult to explain rules to the general public
  • 40. Problems ? What are the best shape and size as an EG board? (Special cells like the acute point are not desirable.) ? Is the reversed rule better? ? Di?cult to explain rules to the general public ? No iOS or Android implementation
  • 41. S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide
  • 42. S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane
  • 43. S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane ? each cell has an assigned score (randomly at the beginning)
  • 44. S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane ? each cell has an assigned score (randomly at the beginning) ? compete on: Euler char. + the sum of scores (+ Komi)
  • 45. S.E.G. (Stringy Euler Getter) a possible variant of EG which might address issues in the last slide ? on a torus instead of the projective plane ? each cell has an assigned score (randomly at the beginning) ? compete on: Euler char. + the sum of scores (+ Komi) Algebro-geometric interpretation torus + scores = log elliptic curve Euler char. + scores = stringy Euler number
  • 46. References ? Euler Getter Wiki: http://www14.atwiki.jp/euler_getter/ ? My homepage: http://takehikoyasuda.jimdo.com/

Editor's Notes

  1. \n
  2. \n
  3. \n
  4. \n
  5. \n
  6. \n
  7. \n
  8. \n
  9. \n
  10. \n
  11. \n
  12. \n
  13. \n
  14. \n
  15. \n
  16. \n
  17. \n
  18. \n
  19. \n
  20. \n
  21. \n
  22. \n
  23. \n
  24. \n
  25. \n
  26. \n
  27. \n
  28. \n
  29. \n
  30. \n
  31. \n
  32. \n
  33. \n
  34. \n
  35. \n
  36. \n