「コンピュータに負けない新ゲーム」記事へのコメント

勝てない時にはルールを変える

[suntear (11933)]

件のチェス対戦でのカスパロフ氏の敗北は，むしろこの手のゲームでは特殊なケースだと思いますので，人間のアドバンテージを確保する目的で新しいルールを公案する必要はないのではないでしょうか．将棋，囲碁になるとコンピュータは人間の専門棋士に遠く及ばないのが現状です．

将棋は随分と強くなっており，アマ初段の私などでは簡単に勝てないソフトが市販されています．

囲碁はまだまだ弱く，例えば GNU Go [gnu.org]などは，今年の 7 月にカナダのエドモントンで開催された The second annual 21st Century Cup Computer G [intelligentgo.org]

Re:勝てない時にはルールを変える

[halo (12510)]

オセロとバックギャモンはもうコンピュータの方が強いようですね。

で、軍人将棋はどうなってるんでしょう?

Re:勝てない時にはルールを変える

[suntear (11933)]

> オセロとバックギャモンはもうコンピュータの方が強いようですね。

囲碁や将棋よりも手が狭いということです．

この手の問題は，おそらく P != NP な問題で，現在広く使われているコンピュータでは brute-force アルゴリズムで解くしかありません．したがって 1 手の自由度が狭いゲーム程，コンピュータが有利になります．

オセロのゲーム開始から 5 手のすべての手順の数は，

  64 * 63 * 62 * 61 * 60 = 914941440

囲碁のゲーム開始から 5 手のすべての手順の数は，

  361 * 360 * 359 * 358 * 357 = 5962870725840
  (石を取ることは考慮しない)

Re:勝てない時にはルールを変える

[nasb (3002)]

> この手の問題は，おそらく P != NP な問題で，

「NP完全問題」か「NP困難問題」のどちらかを書きたかったのでしょうか？

Re:勝てない時にはルールを変える

[suntear (11933)]

>「NP完全問題」か「NP困難問題」のどちらかを書きたかったのでしょうか？

完全なアルゴリズムを見いだすのは困難 (もちろんゲームの内容によります) であるという観点から，一般的に多項式時間で解けない類の問題ではないかという予想です．NP 完全な問題に帰結するかどうかということは検討していません．

ゲームが終了するまでの手順を読むという前堤であれば，ある手順における勝ち負けは明らかなので NP 完全のように思えますが，囲碁や将棋で考えると複雑すぎて，予想の域を出ませんね．

Re:勝てない時にはルールを変える

[nasb (3002)]

単に、「P != NP」という言葉の使い方が変ではないですか？という指摘です。

Re:勝てない時にはルールを変える

[tix (7637)]

ご存じかもしれませんが、オセロの盤のサイズを8×8と固定しない場合、与えられた局面の必勝手を求める問題は NP 問題ですらない（つまり、 NP 完全問題より難しい）と予想されています。正確には、 PSPACE 完全であることが証明されています。

参考: Computational complexity of games and puzzles [uci.edu]。

--
鵜呑みにしてみる？