Skip to main content
MathOverflow

Return to Answer

deleted 9 characters in body
Source Link
Steven Landsburg
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153

It's easy to prove that either White has a winning strategy, Black has a winning strategy, or each player can force a draw. It's not terribly hard to prove to put an upper bound on the number of moves in a winning strategy (roughly the number of positions in the game --- the argument being that if a winning strategy required more moves than there are positions, then some position would be reached twice, meaning that the winning player could have taken a short cut and skipped the intervening moves). So it is a finite (and hence decidable) problem to determine which of the three possibilities holds.

It's easy to prove that either White has a winning strategy, Black has a winning strategy, or each player can force a draw. It's not terribly hard to prove to put an upper bound on the number of moves in a winning strategy (roughly the number of positions in the game --- the argument being that if a winning strategy required more moves than there are positions, then some position would be reached twice, meaning that the winning player could have taken a short cut and skipped the intervening moves). So it is a finite (and hence decidable) problem to determine which of the three possibilities holds.

It's easy to prove that either White has a winning strategy, Black has a winning strategy, or each player can force a draw. It's not terribly hard to put an upper bound on the number of moves in a winning strategy (roughly the number of positions in the game --- the argument being that if a winning strategy required more moves than there are positions, then some position would be reached twice, meaning that the winning player could have taken a short cut and skipped the intervening moves). So it is a finite (and hence decidable) problem to determine which of the three possibilities holds.

Source Link
Steven Landsburg
Steven Landsburg
  • 23k
  • 5
  • 95
  • 153

It's easy to prove that either White has a winning strategy, Black has a winning strategy, or each player can force a draw. It's not terribly hard to prove to put an upper bound on the number of moves in a winning strategy (roughly the number of positions in the game --- the argument being that if a winning strategy required more moves than there are positions, then some position would be reached twice, meaning that the winning player could have taken a short cut and skipped the intervening moves). So it is a finite (and hence decidable) problem to determine which of the three possibilities holds.