Solving Chess

[drkitten]

If there are multiple possible outcomes, but they are all positive, you're still guaranteed to walk away with more money. If there is any possibility of a negative outcome, no initial stake will guarantee you a positive outcome. If there is a constant outcome, repeated games aren't exactly interesting. What was the larger context that made it interesting to distinguish cases which make repeated games trivial?

There were a number of theorems, IIRC, that involved dividing by the expected variance.

This is difficult to do if the variance is zero.

 

[quarky]

I'm not sure what this game is actually called, but here's a very simple example. Start off with a pile of tokens (I can't remember how many you need exactly, I think it has to be a prime number, and obviously bigger than five). Each turn you can remove 1, 2 or 3 tokens. Whoever takes the last token loses.

Do you think the first player is guaranteed to win if played perfectly? If you do, you'd be wrong. Whoever plays first is guaranteed to lose unless the other player screws up. Even if the best player in the world plays against himself, he will still lose (you know what I mean).

The point is, going first is not necessarily an advantage. With chess, it certainly appears to be an advantage, but there are two problems. Firstly, we haven't proven that it's actually an advantage. It could turn out that there's a perfect play which would mean black always wins. Secondly, even if there is an advantage, that does not guarantee you a win. If may be that black cannot win given perfect play by white, but that perfect play by black can still result in a draw.

This is why I mentioned the fairy chess games. Unfortunately, I don't recall the one that gave advantage to second move, yet it was clear after several tries with an equal player.

Yet, if first move isn't an advantage, always, then we get into fuzzy logic, no?

 

[drkitten]

Yet, if first move isn't an advantage, always, then we get into fuzzy logic, no?

No. We don't even need game theory and "mixed" strategies. See post #79 for an example of a game that can be completely analyzed using arithmetic and traditional logic to show that the second player has a forced win regardless of the first player's moves.

 

[Cuddles]

The game is usually called "Nim" and it comes in approximately as many variants as there are published papers on it. With "normal" Nim, where the person who takes the last token loses, it's a win for the second player if there are 4N +5 (or 1, but that's silly) tokens in the pile at the start of the game.

Basically, whatever move the first player makes (call it X), I remove 4-X tokens. This means that eventually there will be five in the heap at the end. I do the same thing once more, so he has one at the end that he is forced to take.

Turning it around, it is a win for the first player if there is any number other than 4N+1 at the start; the first player just removes enough to make it 4N+1.

With the variation that the player to take the last token wins, the magic number is 4N. It's a second player win if it starts at 4N, a first player win otherwise.

Other variants involve multiple piles and unrestricted number of tokens that can be removed from a single pile, or removal from multiple piles under various restrictions.

Thanks, that's the one. I could have sworn prime numbers were involved somewhere, but it has been several years since I read about it.

 

[quarky]

slight derail;

anyone here play 'othello'?
Such an oddly simple game; so few rules, yet near endless depth of strategy.

 

[Dan O.]

slight derail;

anyone here play 'othello'?
Such an oddly simple game; so few rules, yet near endless depth of strategy.

The maximum depth cannot exceed 60 moves so I wouldn't call it endless. It's been solved for the 6x6 version and the second player always wins with perfect play.

 

[Safe-Keeper]

Black always wins

I always lose.