チェッカーの解法

昨日日経新聞に出てた.
J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen. "Checkers Is Solved " -- Science
最善手を打ち続けると両者引き分け. 1989年から回し続けてたらしい.
概要を読むと引き分けと書いてあるが, これAIの論文じゃないか? 本当に引き分けなのだろうか. Science読むか (面倒臭い).

Chinook - World Man-Machine Checkers Championに実装されている.
Publicationsの項から2005年のを流し読みした. このときはある開始状態からの探索を全て行ったらしい. 2007年に全ての定石を調べた終わったということか.

一般化チェッカーと一般化オセロの複雑さについて言及しているのがあったのでメモ.

7. Anonymous says:
It's unfair to say Kasparov lost: (1) all in all he won the game in two matches (2) he underperformed in the last match and (3) Deep Blue refused to give its analysis lines... But no doubt computers will win sooner or later. The engine Rybka seems unbeatable at the moment...
Is othello next? Are both (generalised) othello and checkers PSPACE-complete?
8. Aaron Sterling says:
Don't know about Othello, but here's a paper that claims generalized checkers is *EXPTIME* complete. At stake is whether the game is such that possible legal moves can generate a game tree that is exponential in the size of the board (which is the "input length").
J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing, 13 (2): 252–267.
9. Numan says:
Othello is also PSPACE complete.
S. Iwata and T. Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theor. Comp. Sci. (123): 329–340.