Wednesday, January 20, 2010

Is there such a game...

My lack of knowledge of all the material in CGT often comes out when I try to talk about a general aspect. Luckily, there are enough people reading this that they let me know about it and correct me! Sweet!

Other times, this happens when I'm trying to prove something and realize I'm just not familiar with enough games out there. This morning, I was considering a game and hoping I could show it was PSPACE-complete. Then I realized that the method of play was dissimilar from any other games I knew anything about.

I have mentioned before that I think those reductions that transcend locality or number of players are excellent. Now I'm curious about involving the number of pieces.

What is known about games where each player has only one "piece" or one "location" at each game state? Through the course of the game, the two pieces may traverse the board. Are there any proven-hard games out there with a property like this?

Many games could be considered to have only one "location" per move, such as with Kayles. In that example, though, the location of your last move does not restrict the location of your next move; you can still make the next move wherever you like. This is not true if you're playing Amazons and each player has only one Queen; your options for movement are restricted by the current position of that Queen.

No comments:

Post a Comment