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

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

[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
  (石を取ることは考慮しない)

それぞれひとつの手順を評価するのに要する時間を同じであるとすると，同じ 5 手を読む場合，囲碁の方が，

  5962870725840 / 914941440 = 6517 倍

の時間を必要とします．

これは単純化されたモデルによる計算ですが，1 手の自由度の差が，読む手数が増える程，指数関数的に，処理時間の差となって現れることを，雰囲気的につかんでいただけるのではないかと思います．

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

[halo (12510)]

おお、丁寧な説明ありがとうございます。

囲碁というのは探索範囲の広さもさることながら、
「この辺はまだ決着ついてないけど、あっち行こか」とか、
「まだ微妙なとこあるけど、決まったよね」みたいな
対戦者同士の無言のやりとりが感じられるゲームで、
その辺をプログラム化することは難しかろうなと思います。

各手の評価をするアルゴリズムを作って総あたり式でという
今のアプローチだと、まだしばらくの間、強い弱いの問題とは
別の意味で相手にならないというのが私の印象です。

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

[suntear (11933)]

> 囲碁というのは探索範囲の広さもさることながら、
> 「この辺はまだ決着ついてないけど、あっち行こか」とか、
> 「まだ微妙なとこあるけど、決まったよね」みたいな
> 対戦者同士の無言のやりとりが感じられるゲームで、
> その辺をプログラム化することは難しかろうなと思います。

そうですよね．石が詰まって来た場面での死活は読みの部分がありますけど，それは局面が進んで，手順が限定されて来たときの話です．手が広い場面では到底読みきれるものではありませんので感性で打つことになります．

> 各手の評価をするアルゴリズムを作って総あたり式でという
> 今のアプローチだと、まだしばらくの間、強い弱いの問題とは
> 別の意味で相手にならないというのが私の印象です。

良く知らないのですが，量子コンピュータが実用化されると P != NP であると思われる問題に強いという話です．
結構期待しているのですが．

〔オフトピ〕必殺の

[Newtosh (12572)]

整地での勝負(!)ってのもありますしね。

#コンピュータ相手じゃムリ。「手談」ももっとムリ

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

[arkas (10211)]

些細な事だけど、Othelloはそんなに手が無いから読むの簡単だよ(例えば初手は置ける場所は8通り、でも対称形を削れば実質1通り)

# 最近趣味でOthelloのアルゴリズム書いてるのでID

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

[suntear (11933)]

> 例えば初手は置ける場所は8通り、でも対称形を削れば実質1通り

ご指摘ありがとうざいます．ぼけておりました．

オセロだと 1 月ぐらいの常識的な時間で，すべての手順の解析ができそうですね．

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

[tix (7637)]

オセロだと 1 月ぐらいの常識的な時間で，すべての手順の解析ができそうですね．

ああ、そうそう、オセロは先手必勝です。証明はここには狭くて書けませんが :)

冗談はさておき、1ヶ月で解析できるなら、誰か既にやって、結果が報告されていると思いますよ。

6×6 の盤でのオセロは後手必勝 [nott.ac.uk]だそうです。

--
鵜呑みにしてみる？

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]。

--
鵜呑みにしてみる？