Transverse wave: an impartial color-propagation game inspired by social influence and quantum NIM. (English) Zbl 1492.91064
The authors study Transverse wave, a colorful, impartial combinatorial game played on a two-dimensional grid. They show several connections of this game with other well-studied combinatorial games. The game is played on a grid with green or purple cells, two players then take turns selecting a column of this colorful grid. A column is feasible for the grid if it contains at least one green cell. The selection of a column transforms the grid into another colorful grid of the same size by recoloring the column chosen and every row with a purple cell at the chosen column with purple. In the normal-play convention, the player without a feasible move loses the game.
Reviewer: Manjil Pratim Saikia (Cardiff)
MSC:
| 91A46 | Combinatorial games |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 91A81 | Quantum games |
| 81P40 | Quantum coherence, entanglement, quantum correlations |
Keywords:
combinatorial gamesReferences:
| [1] | M. H. Albert, R. J. Nowakowski, and D. Wolfe, Lessons in Play: An Introduction to Combi-natorial Game Theory, A. K. Peters, Wellesley, Massachusetts, 2007. · Zbl 1184.91001 |
| [2] | G. Beaulieu, K. G. Burke, andÉ. Duchêne, Impartial coloring games, Theoret. Comput. Sci. 485 (2013), 49-60. · Zbl 1297.05160 |
| [3] | E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for your Mathematical Plays, volume 1, A. K. Peters, Wellesley, Massachsetts, 2001. · Zbl 1005.00004 |
| [4] | C. L. Bouton, Nim, a game with a complete mathematical theory, Annals of Mathematics 3(1/4) (1901), 35-39. · JFM 32.0225.02 |
| [5] | K. Burke, M. Ferland, and S.-H. Teng, Quantum combinatorial games: structures and com-putational complexity, CoRR abs/2011.03704, 2020. |
| [6] | K. W. Burke and O. George, A PSPACE-complete graph nim, Games of No Chance 5 (2019), 259-270. |
| [7] | K. W. Burke and S.-H. Teng, Atropos: a PSPACE-complete sperner triangle game, Internet Mathematics 5(4) (2008), 477-492. · Zbl 1194.91025 |
| [8] | K. W. Burke, Science for Fun: New Impartial Board Games, PhD thesis, USA, 2009. |
| [9] | W. Chen, S.-H. Teng, and H. Zhang, A graph-theoretical basis of stochastic-cascading net-work influence: characterizations of influence-based centrality, Theor. Comput. Sci. 824-825 (2020), 92-111. · Zbl 1437.91342 |
| [10] | P. Dorbec and M. Mhalla, Toward quantum combinatorial games, arXiv preprint arXiv:1701.02193, 2017. · Zbl 1486.91020 |
| [11] | D. Eppstein, Computational complexity of games and puzzles, 2006, http://www.ics.uci.edu/∼eppstein/cgt/hard.html. |
| [12] | S. Even and R. E. Tarjan, A combinatorial problem which is complete in polynomial space, J. ACM 23(4) (1976), 710-719. · Zbl 0355.68041 |
| [13] | A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n x n chess requires time exponential in n, J. Comb. Theory, Ser. A 31(2) (1981), 199-214. · Zbl 0467.90100 |
| [14] | A. S. Fraenkel, E. R. Scheinerman, and D. Ullman, Undirected edge geography, Theor. Comput. Sci. 112(2) (1993), 371-381. · Zbl 0801.90147 |
| [15] | M. Fukuyama, A nim game played on graphs, Theor. Comput. Sci. 1-3(304) (2003), 387-399. · Zbl 1041.91018 |
| [16] | D. Gale, A curious nim-type game, American Mathematical Monthly 81 (1974), 876-879. · Zbl 0295.90045 |
| [17] | D. Gale, The game of hex and the Brouwer fixed-point theorem, American Mathematical Monthly 10 (1979), 818-827. · Zbl 0448.90097 |
| [18] | A. Goff, Quantum tic-tac-toe: a teaching metaphor for superposition in quantum mechanics, American Journal of Physics 74(11) (2006), 962-973. |
| [19] | P. M. Grundy, Mathematics and games, Eureka 2 (1939), 198-211. |
| [20] | D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through a social network, In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03 (2003), 137-146. |
| [21] | D. Lichtenstein and M. Sipser, Go is polynomial-space hard, J. ACM 27(2) (1980), 393-401. · Zbl 0434.68028 |
| [22] | J. F. Nash, Some Games and Machines for Playing Them, RAND Corporation, Santa Monica, CA 1952. |
| [23] | S. Reisch, Hex ist PSPACE-vollständig, Acta Inf. 15 (1981), 167-191. · Zbl 0431.90103 |
| [24] | M. Richardson and P. Domingos, Mining knowledge-sharing sites for viral marketing, In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’02 (2002), 61-70. |
| [25] | T. J. Schaefer, On the complexity of some two-person perfect-information games, Journal of Computer and System Sciences 16(2) (1978), 185-225. · Zbl 0383.90112 |
| [26] | R. P. Sprague,Über mathematische kampfspiele, Tôhoku Mathematical Journal 41 (1935-36), 438-444. · JFM 62.1070.03 |
| [27] | G. Stockman, Presentation: The game of nim on graphs: nimg, 2004, Available at http: //www.aladdin.cs.cmu.edu/reu/mini_probes/papers/final_stockman.ppt. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
