オセロの解

　この前、数学的にオセロは先手が必勝だという事が、証明されたと言うことを聞いたのですが、それは本当なのでしょうか？
　これは、先手と後手が必ず最前の手を打つという前提なのでしょうが、そんな事が証明かのなのでしょうか？

　お願いします。

No.5 回答者： entree 回答日時： 2006/02/18 13:08

結論から言うと、８ｘ８オセロにおいては、まずドロー (引き分け) と考えて間違いはありません。

最初に双方最善でドローになったとされている手順として見いだされたものは「パブリック・ドロー (PD)」と呼ばれ、今でもメジャーな定石の１つですが、その他にも双方最善でドローになったと思われる手順が数十通り存在するようです。

少なくとも黒勝ち説がないのは以下の根拠によるためと思われます。

白２手目で縦取りでも斜め取りでも以後双方最善でドローとなると思われる手順が複数発見されている状況で、これを黒勝ち説にするためには、縦取り、斜め取りの両方においてこれらの手順を覆す手順が発見されなければならないこと。(現時点での調査状況からは縦取りまたは斜め取りの片方でさえも覆る可能性はかなり低い)

一方、白勝ちを証明するためには白から変化して、かつ黒最善の黒を相手に勝つ必要があります。しかしながら、現時点において、白から考えられる変化のほとんどは研究され尽くしていて、これ以上の白の変化は考えにくいことです。(確定ではありませんので、白勝ちの余地は、わずかながら残されていることになります)

しかも、斜め取りでは、黒５手目で牛定石と飛び出しの両方で双方最善ドローと思われる手順が発見されていたと思うので、斜め取りで白勝ちはまずあり得ないでしょう。

No.4 回答者： jedimaster 回答日時： 2006/01/26 15:42

>質問が「証明できるか」ですから

#2です。この部分の補足ありがとうございました。
おっしゃるとおり、原理的には有限ですので証明可能です。

少し訂正させていただき、ついでに少し詳細について書きます。
まず黒の1手目ですが、打てるのは2箇所でなく4箇所です。しかしどこに打っても対称形で同じことになります。白の2手目は3通りの着手があり、黒3手目までの形は14通り。この後手数が増えると、異手順同形(違う手順でも同じ形)が少しずつ出現するようになりますので、これらを除いて考えると4手目までで60通り、5手目までで338通り・・・となり、10手目までのパターンで数百万通りの変化があります。囲碁や将棋と比較すると、パターンの数は圧倒的に少ないのですが#3の方のおっしゃるとおり、現在のコンピュータでもまだまだ計算しつくせないだけの複雑さがあります。

ただ、計算しつくせないといっても、既に現在最も優秀なソフトウェアは、人間のチャンピオンの能力を上回っています。
これはある局面の評価関数(現在のポジションで黒白どちらがどの程度有利であるかを定量的に評価する手法)が発達したためです。評価関数の作成はこれまたコンピュータの仕事で、完全解析が可能となる30～40個空きに至る手前の段階で、どのような要素をどのような場面でどのような係数を掛けて計算式に入れればどの程度局面の評価値を真の値(完全読みした場合の数値)に近づけることができるかを、試行錯誤的に統計解析して評価関数は作られています。

このような技術により、最強の人間を最強のソフトが教育するという機会がオセロには生まれ、人間の技術向上にソフトが大きく貢献するという状態になりました。人間の技術向上でソフトとの差はここ数年で僅かに縮まったようですが、それでもソフトの方が強いことに変わりはありません。

No.3 回答者： tatsumi01 回答日時： 2006/01/26 11:52

No. 1 のものです。

No. 2 の方の回答では、まだ証明されていない（しかも、引き分けか後手必勝）という話です。質問が「証明できるか」ですから補足します。
オセロは、必ず着手する（パスできない）、相手の駒を裏返すマスにしか打てない、というルールだと思います。
そうすると、第１手で先手は二つしか選択肢がありません。そのどちらかを打ったとして、後手はまた２～３程度の選択肢のどれかを選ぶしかありません。以下同様に、選択肢はありますが、将棋のように同じ手順を無限に繰り返すことはできず、一方向に進行します。
どの選択肢を取るにせよ、マス目は６４ですから、６０回以下の着手で必ず終局し、どちらかの勝ち／引き分けが決ります。つまり、ゲームの進行の場合数は有限です。コンピュータでも数えつくせないでしょうが、理論的には有限ですから必ず全てのゲーム進行の結果は決ります。
ある時点で先手が指したとき、そのあと後手が最善をつくしても先手の勝ちになるなら、その手を先手が選んだ時点で先手必勝です。問題は、開始時点において先手にそんな手があるかどうかで、あるなら先手必勝です。
現時点でそのような手順が示せるかどうかは別として、ゲーム進行は有限ですから必ず数え上げられます。したがって、先手必勝、後手必勝あるいは引き分けのどれであるにせよ、そのことは原理的に証明できます。

No.2 回答者： jedimaster 回答日時： 2006/01/26 05:02

8x8のマス目の盤を使う普通のオセロに関しては、

以前私が回答した時と、状況は変わっていません。
数学的証明は困難で、コンピュータが#１の方のミニマックス法を
改良し最適化したαβ枝刈法で解析を進めているところですが、まだ
結論は出ていません。詳細は参考URLの私の回答を参考にしてください。

ちなみに4x4の盤、6x6の盤はコンピュータが完全解析しており、
いずれも後手(白)の勝ちとなります。

8x8についてはおそらく引き分けか、後手(白)の勝ちというのが、世界
チャンピオン経験者や高段者(オセロにも段位があります)の意見の
大勢を占めています。
今世紀中には結論が出ると思います。

参考URL：http://okwave.jp/kotaeru.php3?q=1390049

No.1 回答者： tatsumi01 回答日時： 2006/01/25 23:51

「最前」は「最善」でしょうね。

オセロは囲碁や将棋と違って繰り返しがありません。
ある局面で打てる手は有限です。有限の手の高々６０回程度の繰り返しですから、一局（局面の進行）の数は有限です。その全てについてミニマックス原理（双方最善手を打つ）で検証すれば、どちらが勝つか（あるいは引き分けか）は決定できます。
ゲームは先手必勝、後手必勝、引き分けのいずれかですが、先手必勝であれば必ず必勝手がみつかります（もちろん、最善をつくしても双方引き分けというケースや、後手必勝というケースはありえます）。
結論として証明は可能です。ただ、証明されたかどうかは知りません。