End States: Hardness without Randomness

My last post was about trying to show some games were (NP) hard to play even near the end. I have a few motivations for thinking this way, and some tie more into the basis of combinatorial games than others.

In the post I mentioned the game Cave Troll, which is a cool fantasy-setting board game. Each player controls a cohort of adventurers and monsters which meander around a cave, sometimes avoiding each other and sometimes ganging up on characters of other players. Every so often (determined randomly) the board is "scored" and players gain points based on the value of each room they have more adventurers in than those of other players.

The randomness comes from card drawing. Each player has their own small deck of cards and when they draw the last card, the game ends after after the card is played. Some cards are marked and after enough of them are played, the board is scored. Other than this, there are no sources of randomness in the game. Players can only take actions on their own turns. Thus if a player has only one card left in their deck, they know what that card is and can determine whether any sequence of actions on their turn will win the game. (Actions include moving characters one space or using their abilities, as well as drawing and playing one card. A player is limited to a certain number of actions per turn.) Without the randomness, this situation acts a lot more as a combinatorial game.

Thus, if the current player has only one card in their deck, we can ask the question: "Do you have a winning strategy this turn?" The hope is that this is NP-hard. (It would explain why my last turns always take too long!)

There is another reason to investigate end states instead of general states: I cannot think of another way to approach other analysis! Our game Dictator (sorry, no link yet!) is like this. This game simulates investigation of a set of ballots, until a dictator is found (or IIA is violated) as per Arrow's Theorem. Instead of trying to show hardness at any turn, I hope to show that it is hard to come up with a proof enabling you to win that turn.

In any case, there are a variety of games where the last few turns are meaningless, but some others where everything can change in the last few decisions! Which actual properties make these games different?