オセロの「必ず勝つ方法」のプログラム開発は技術的に可能？

質問

小学生の頃、私と友人達との間で○× （マルバツ）というゲームがはやっていました。
この○×というゲームは、「絶対負けない方法」というのが存在し、その方法は
小学生でも理解できる非常に簡単なものでした。

そこで疑問に思ったのですが、もしパターンを徹底的に追求すれば、○×よりも
もっとルールが複雑なオセロでも「必ず負けない方法」を開発することって
出来るのではないでしょうか？

チェスのプロに勝ってしまうコンピュータなんてのが出てきて話題になったのは
かなり昔になってしまいましたが、ルールがチェスよりも単純なオセロなら、
プロに勝つどころか「絶対に負けない」というアルゴリズムを開発する事は
可能な気がしてしまいます。

現在のコンピュータ開発は、オセロ対戦プログラムについてはどこまで進んでいるので
しょうか？
コンピュータのオセロってどれくらい強いんでしょうか？
今後の開発具合によっては「オセロで絶対に負けないコンピュータ」は現れると
思いますか？

回答No.4

Tacosan · ベストアンサー

「オセロで必ず負けない方法」というのは, あくまで「技術的」には可能です. ただし, 非現実的な時間とメモリを要求しますが.
なお, いろいろなゲームに対するプログラムの強さですが, およそ次のようになっていると思います (全て「最強のプログラム」を比較しています):
・オセロ: 最強の人間であっても歯がたたない
・チェス: 最強の人間ならいい勝負
・将棋: 最強の人間は苦労するだろうけど有利
・囲碁: 最強の人間なら余裕で勝てる
まず, オセロやチェスに関していうと, 「エンドゲーム (終盤) ではコンピュータは無敵」と言っていいです. オセロでは石を置く場所が少なくなるため, またチェスでは動かせる駒が少なくなるため, どちらも可能な着手の数が少なくなります. そのため十分に読むことができるようになり, (コンピュータが理論上間違えないこととあわせて) 「無敵」という状況になります. 今だと, オセロのコンピュータプログラムは「40手目 (つまり残りが 20マス以下) では読み切れる」くらいになっていると思います. 従って人間が勝つためにはそこまでに「余裕で勝っている」くらいまで局面をリードしないと, 「絶対に間違えないコンピュータ」に追い詰められることになります.
ついでにいえば, 囲碁の場合黒番 (= 先手) に 6目半のコミがある (つまり, 黒番には 6.5目分のハンディがある) わけですが, これがないと「黒番が負けることはありえない」ルールになっています. つまり, コミがない場合には白番 (後手) の必勝法は存在しないことが一瞬で証明できます.

お礼

回答ありがとうございます。興味深いご回答でした。

回答No.3

php504

ミニオセロ（6×6）なら1994年にイギリスのファインシュタインという人が後手必勝であるということを証明したらしいです。
ちなみに先手が最善を尽くした時は、先手16対後手20で後手の4目勝ちになるとか。

お礼

なるほど。将来的には正規のオセロでも必勝法が見つかるかもしれませんね。

回答No.2

notnot

＞オセロは二人零和有限確定完全情報ゲームに分類されるゲームなので
までは良いのですが、先手必勝か後手必勝か引き分けかはまだわかっていません。
○×も二人零和有限確定完全情報ゲームの引き分けのケースですね。

アルゴリズムの問題と言うよりは、場面の数が多すぎて現在のスーパーコンピュータでも非常に時間がかかって無理と言うことです。

CETI@HOME 等のように、全世界のボランティアのPCを繋いで計算すれば出来るかも。

回答No.1

syatsoul

オセロは二人零和有限確定完全情報ゲームに分類されるゲームなので必勝法があります。
実際には完全な先読みを人間が行う事は困難であるため、ゲームとして成立しています。
その完全な先読みができるアルゴリズムが完成すれば必勝できます

参考URL：

http://ja.wikipedia.org/wiki/二人零和有限確定完全情報ゲーム