Wang tiles are interesting in that they can simulate Turing machines. My question is whether anyone has studied their game theoretic properties?

In particular, we could imagine a game in which you have a plane with some Wang tiles on it, and players take turns placing tiles adjacent to tiles already on the board. The last player to place a tile wins. This is only one example of how to gamify Wang tiles, of course.

Is there any research into the games based on Wang tiles?

  • 1
    $\begingroup$ I am not aware of any research into this interesting question. Perhaps the 1-dimensional version has been studied, since it is similar to the popular word game "Ghost". You might ask Chaim Goodman-Strauss. $\endgroup$ – David Cohen Jun 8 '17 at 13:43

Perhaps the key search phrase is "domino-tiling games." This 1986 paper seems to be a source, subsequently cited ~100 times.

Chlebus, Bogdan S. "Domino-tiling games." Journal of Computer and System Sciences 32.3 (1986): 374-392. Journal link.

Abstract. Games in which players build domino tilings are considered. The computational complexity of problems of existence of winning strategies is investigated. These problems are shown to be complete in the respective complexity classes, e.g., SQUARE TILING GAME is complete in PSPACE, HIGH TILING GAME is complete in 2EXPTIME and has a doubly exponential time lower bound. As an application, new simple hardness proofs for certain propositional logics are obtained.

Among the later papers: Grädel, Erich. "Domino games and complexity." SIAM Journal on Computing 19.5 (1990): 787-804. Journal link.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.