- 8×8 Othello/Reversi は、双方が完全にプレイした場合の最終結果が 引き分け であることが計算的に証明され、研究チームの基準では弱い解決状態に到達した
- 可能な棋譜が約 10^58、盤面位置が約 10^28 と推定されるほど探索空間が大きく、既存の解決事例である checkers よりはるかに難しい問題として残っていた
- 今回の結果は、初期位置の ゲーム理論的値 とその値を達成する戦略を求めたものであり、すべての中間位置を計算した強い解決ではない
- 研究チームは Othello ソフトウェアをベースにしたヒューリスティック探索と alpha-beta search を活用し、厳密解に必要な探索規模が以前の予測より小さかったと説明している
- 結果再現のための原データとプログラムが GitHub、Zenodo、figshare で公開されており、純粋戦略ゲームの解決研究における検証可能な事例として活用できる
Othello の計算的解決
- 8×8 盤の Othello は弱く解かれており、初期位置のゲーム理論的値は 引き分け と計算された
- 双方がミスなく最善を尽くしてプレイすれば引き分けになり、今回の研究はこれを計算的に証明した
- Figure 1 には最適な棋譜の一例と最終結果が示されている
- その手順のどの時点であっても逸脱が発生すれば、研究チームのソフトウェアが相手側として引き分けまたは勝利を保証する
- この結果は人間の Othello 専門家たちが予測してきた引き分けと一致しており、研究チームは結果自体は驚くものではないと見ている
解決の範囲とゲーム理論的値
- 完全情報ゲームを解くとは、双方が 完全なプレイ を行ったときの最終結果、すなわち ゲーム理論的値 を決定することを意味する
- 解決されたゲームは通常 3 つのレベルに分けられる
- 超弱解決 (ultra-weakly solved): 初期盤面位置のゲーム理論的値だけを知っている場合
- 弱解決 (weakly solved): 初期位置のゲーム理論的値と、合理的な計算資源の範囲内で双方がその値を達成する戦略を知っている場合
- 強解決 (strongly solved): ゲーム中に発生しうるすべての可能な局面の結果を計算した場合
- 今回の研究は Othello を 弱解決 した事例であり、すべての可能な局面を計算した強解決ではない
- checkers も同じ意味で弱解決されたゲームとして示されている
Othello が長く残っていた理由
- Othello は戦略的な深みを持つ人気ゲームで、19世紀の英国で発明された後、20世紀に現在の形式が日本で広まり、世界中でプレイされている
- 世界選手権は 1977年 から毎年開催されており、世界的な人気を示している
- 探索空間は非常に大きい
- 1 局面あたり平均約 10 手
- 1 ゲーム全体で平均約 58 手
- 可能な棋譜は約 10^58
- 可能な盤面位置は約 10^28
- この規模は、これまでに難問として解かれてきたゲーム、特に checkers よりもはるかに大きいとされる
- 巨大な探索空間のため、Othello はコンピュータ科学における長年の課題として残っていた
探索方法と計算効率
- 研究チームは弱解決を目標に alpha-beta search を使用した
- ゲーム解決アルゴリズムは、目標とゲームの性質によって異なる
- 弱解決には alpha-beta search がよく使われる
- 強解決には retrograde analysis がよく用いられる
- 非常に長い解答シーケンスを持つパズルには df-pn search のような手法が開発されている
- alpha-beta search はゲームグラフを深さ優先で逐次探索するアルゴリズムであるため、単純な並列化だけでは探索効率を大きく高めにくい
- 並列探索にはさまざまな方式が研究されている
- 共有メモリ環境では YBWC と Lazy SMP が一般的な方法である
- 分散メモリ環境では APHID と ABDADA が関連アルゴリズムとして挙げられる
- 分散メモリ環境ではノード間の帯域幅や遅延時間といった条件が大きく異なるため、開発者は環境に合ったアルゴリズムを選択するか、新たに開発する必要がある場合がある
- 最新のコンピュータクラスタを使っても Othello の解決は大きな障壁だったが、最新の Othello ソフトウェアを改良して探索効率を高めたことが突破口になった
他の解決済みゲームと活用可能性
- Othello 以前に難問として解決された最新の事例として checkers が挙げられている
- Connect Four、Qubic、Go-Moku、Nine Men’s Morris、Awari といった非自明なゲームも解決事例として列挙されている
- ゲームの解決難易度は、概してゲーム内の局面や状況の数に大きく左右される
- ゲームを解くことは最終結果を明らかにするだけでなく、そのゲームをベースにした パズル生成 にも活用できる
- 研究チームは再現のための原データとプログラムを GitHub、Zenodo、figshare で提供している
1件のコメント
Hacker News のコメント
「2,958,551 個の局面のうち 2,587 個の局面を選んで結果に関する仮説を立て、この仮説がすべて正しければ初期局面が引き分けであることを証明する」としながら、それ以上の詳しい説明がない
ゲームが完全に解かれたというより、著者が勝ち筋をかなり一生懸命探したが見つからなかった、というふうに聞こえる
「初期局面が引き分けであることを証明できる部分集合を選ぶ方法は多いが、われわれは Algorithm 1 によって小さな部分集合を得た」と書かれている
Algorithm 1 は、「空きマス 50 個のすべての局面の予測スコアを受け取り、その部分集合のすべての局面が解かれ、解が予測と一致すれば、初期局面も結果的に解かれる」部分集合を返す、と説明されている
全体として論文の記述が直感的ではない。著者が正しい可能性はあるが、きちんと腰を据えて論理を追う必要がありそうで、第一印象としては懐疑的
この種の証明は他にもある。たとえば 四色定理も、有限個の構成に還元したうえで手作業で彩色する方式だった
https://github.com/eukaryo/reversi-scripts/blob/main/reversi... のスクリプトは、全体が正しいという前提で完全に指す。リポジトリ内の他のスクリプトは 36 マス空き局面の解を使って計算したデータを用いており、この程度なら一般的なマシンでも可能そうに見える
本質的には、弱解から到達可能な空きマス 37〜64 個のすべての局面を含む 300GB 以下のテーブルを参照し、空きマス 36 個以下の局面は edax の
-solveで解く構造のようだOthello は、基本的な ヒューリスティックだけでどれほど強くなれるかを示すのに適したゲーム
ゲームが進むにつれて絶対に打ってはいけないマスがあり、逆に可能なら必ず打つべきマスもある
こうしたルールを実装するだけでもかなり手ごわい相手になり、人々がごく単純なものにもどれほど素早く「知能」を見いだすかを見るのは興味深い
似たような単純なヒューリスティックを使うアプリと、同じくらい単純だが壊滅的に悪い「最も多く裏返す」戦略のアプリを対戦させたと書いてあった
ヒューリスティックのアルゴリズムが圧勝し、60 対 4 か、それ以上にひどい結果だったと記憶している
空きマスが 19 個になると残りのゲームを完全に解いてしまい、かなり驚かされた
Othello は単三電池 2 本で動く 10 ドルの LCD ゲーム機にも入っていたゲームだ
ゲームに興味があるなら、コンピューター科学者や人工知能研究者の間でも人気のある Othello 世界選手権が、いまイタリア・ローマで開催中
対局は liveothello.com と Youtube @WorldOthello でライブ配信されている
Othello もチェッカーのように、上位陣の対局の大半が引き分けで終わるゲームなのか気になる
すばらしい
15 年ほど前、兄弟とやっていたもっと単純なゲームを解いてみたことがある。盤の両側にそれぞれ約 10 個のくぼみがあり、石を入れるアフリカのゲームだった
アルファベータエンジンを書いたところ、私たちの遊び方に合わせた、とんでもない 必勝戦略を見つけた。その後、突然すべての対局に勝つようになり、兄弟は二度と一緒にやろうとしなくなった。コンピューター科学者対検眼士の典型的な対決だった
年配のアフリカの人たちが Mancala を打つのを見ると学ぶことが多い。非常に素早く打ち、いかさまがゲームの一部になるポーカーのような感じもある
石を十分に速くまけば、器を 1 つ飛ばしたり、石を 1 つ余分に落としたりして得をすることもできる
私はそこまで上手くないし、家族と遊ぶのでいかさまはしない。それでもまったく別のゲームになる。英国の婦人たちがお茶を飲みながらゆっくり Mahjong を打つのと、中国の賭場で金を賭けて打つのとの違いのようなものだ
勝ちすぎても負けすぎても、ゲームを楽しめなくなる
ただ、検眼士という職業がここで何の関係があるのかは分からない
これは本当なのか？ 著者が 1 人で、初めて聞く ディープラーニング・スタートアップ所属という点が少し奇妙に感じる
おそらく査読中なのだろう？
それに Othello は正確にはリーマン予想のようなレベルではない。それだけ研究が少なく、まだ残っていた低い果実があったのかもしれない
Othelloは子どもと一緒に遊ぶのに本当に向いているゲームの一つ
ルールが単純で、覚える価値のあるパターンがあり、大量にひっくり返す楽しさもある。何より、子どもだけでなく大人にとっても同じくらい面白い
6歳の子を圧倒しすぎることなく、単なる運ゲーのようにも感じず、自分も十分楽しめた
https://mancala.fandom.com/wiki/Hus
理論上は運の要素はないが、実際には連鎖反応のせいでそこまで先まで計算できない
ボードは簡単に自作できる
ゲームを試してみたいなら、子どもたちと一緒に作ったものを置いてある: https://jawj.github.io/fliptiles
「AI」プレイヤーはとても弱い
新しいゲームを覚えた
コンピューターが33点、自分は31点だった
Othelloが取るに足らないと思うなら Zebra を試してみるとよい
原作者のウェブサイト: http://radagast.se/othello/
GitHubソース: https://github.com/hoshir/zebra
Othelloで好きな点は、行動と領土の矛盾
ゲームが進む間、自分の手番で手を打つ行為は、ある意味では自分に不利だが、それでも必ず打たなければならない
そのため、盤面が狭くなりすぎて確かな影響力を取り戻す必要が出てくるまでは、占有しながらも小さく内側にとどまる必要がある
関連して、6x6 Reversi を完全にプレイするものもある
https://mame.github.io/6x6-reversi-oracle/
出典: https://twitter.com/mametter/status/1476379841004183556
8x8がまだ解かれていないとは今まで知らなかった