Friday, December 25, 2020

[ribbtdwo] why are some Nim variants easy?

positions in the game of Nim (normal play) can be evaluated quickly.  there is no need for minimax tree search.  surprisingly, misere play of Nim also requires very little computation for perfect play.  this is surprising because often the misere form of a game requires totally different analysis, often more complicated.

restricting moves to removing at most k coins from a heap seems to change the game completely because a good move in the unrestricted game can become no longer permitted, but this variation too, for both normal and misere play, can be computed quickly, in a way similar to unrestricted Nim.

under what conditions does a Nim variant have an easy-to-compute strategy?  define "easy-to-compute" in terms of computational complexity.  is there something deeper going on that allows games to have an easy-to-compute strategies?  not all variations of Nim have easy-to-compute strategies: Domineering, Cram, and Chomp could be viewed as Nim variants permitting removing coins from several heaps simultaneously.

No comments :