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?

Tricky Last Moves and Schedule Change

There are two parts to this post. The first is actual content, but the second is some metaposting about the schedule. The short version is that I am switching to a Tuesday-Friday schedule instead of MWF. I am simply too busy to keep up with posting on my three busiest days of the week, so I will instead post twice per week.

Often, the end of a game is not when the difficult decisions arrive. There are certainly some sneaky final chess positions (I used to see them in the paper) but often either the last moves are a bit obvious or Chessmaster has already forfeited the game to you. (I'm not a good chess player... perhaps I'm completely wrong about this!)

Assume it's your turn and it's the last turn of a game. If that game is Amazons, it doesn't seem hard to determine if you've won. Similarly for Mancala. Each potential move is simple enough that you can try them all and see what the outcome is. In some games, however, there may be a large number of different potential final moves. What do you do in this case?

I picked up the game Cave Troll over the winter break and found myself taking way too long on the last turn of the game. The scores were close, and I had to figure out how to spend my four "actions" on my final turn to maximize the gold I would collect. Worse still, depending on which actions I might use, the game might not even end that turn!

Although I might have had a reasonable number of options for one action, say x, now I have a similar number of options for each of my four actions: meaning about x^4 in total. If we generalize this game, the number of actions might be one of the generalized variables, making it x^n options. Oof!

Which games are hard to make last-turn plays on? Are there lots of good examples of this?