雑記
- 起動時オプション
- GeneralReversi.exeを起動するときに「Ctrlキーを押しながら」にすると、
（コマンドラインでは「GeneralReversi.exe log」と入力すると、）
「ボード」タブではなく、「ログ」タブが、表示された状態で起動します。
通常起動するとボードが表示されることにより、リバーシ／オセロをしていることが
周囲の人に認識される可能性がありますが、このオプションを利用することにより、
その可能性を排除できます。
作者はこれを利用して会社のハイスペックマシンでボードサイズ6の解法を行いました＾＾；
詳しくは「解法」で！
- GeneralReversi.exeを起動するときに「Shiftキーを押しながら」にすると、
（コマンドラインでは「GeneralReversi.exe ffo」と入力すると、）
コンソールでFFOを実行します。
FFOは#40（20手読み）から#48（25手読み）までの9種類で、
作者の環境で全部完了するまでには30分程度かかります。
ソルバープレイヤーで20手以上の深い読みを設定するときの目安にしてください。
- GeneralReversi.exeを起動するときに「Ctrlキーを押しながら」にすると、
- 同じプレイヤー同士の対局
コンピューターの同じプレイヤー同士の対局を、違う設定で行うことは仕様上できません。
例えば、深さ5のアルファベータプレイヤーと深さ10のアルファベータプレイヤーの対局を行うことはできません。
ただ、同じ設定であれば行うことはできますし、
どうしてもという場合には、GeneralReversiを2つ起動して、人間が仲介することによって行うことはできます。
- 待った
コンピューターと対局していて「待った」をしたいときは履歴機能を利用してください。
具体的には、直近の手のみの「待った」であれば今のフェーズから2を引いたフェーズに設定してください。
通常のボードゲームソフトでは「最初へ戻る」、「戻る」、「進む」、「最後へ進む」、
の機能が備わっていることが多いですが、
GeneralReversiでは履歴機能によって任意のフェーズにジャンプすることができるようにしています。
これは、例えばボードサイズが100の場合は終局フェーズは最低でも9996であり、
ここからフェーズ5000に戻したいといった場合に、1つ1つ戻していたのでは大変だからです。
また、相手の手番に戻して、相手プレイヤーの設定を変えたり、プレイヤー自体を変えるといったことも可能です。
- マスの位置
通常のボードサイズ8のリバーシ／オセロでは左上を基準にして、
左右方向にアルファベットのAからHで、
上下方向に数字の1から8で、
マスの位置を表現します。
しかし、任意のボードサイズでマスの位置を表現するためには
アルファベットでは役不足です。
そこで、左右方向に関しても数字で表現します。
また、数字の最初は1ではなく0とします。
さらに、二つの数字を列挙する順番を上下方向→左右方向とします。
つまり、行列表現です。
いくつか例を示します。
- D3：(2, 3)
- C4：(3, 2)
- F5：(4, 5)
- E6：(5, 4)
- D3：(2, 3)
- 棋譜
ゲームを途中で中断して後で再開する場合や、
ゲームの終了後に後で振り返る場合などには、
棋譜の出力と入力を行います。
棋譜を出力したら、コピーしてテキストファイルを作成します。
（付属のFFO#40Moves.txtは棋譜のテキストファイルです。）
再開時や振り返り時にはそのテキストファイルを開き、
コピーして棋譜の入力を行います。
棋譜のフォーマットは人間にもわかりやすいものとなっています。
最初の一行にボードサイズと初期配置を記述し、以降の行では、
左側に先手である黒の着手を、右側に後手である白の着手を、記述します。
- ウィンドウサイズ
起動時のウィンドウサイズは1200×900に設定しています。
ウィンドウサイズのリサイズは可能ですが、このサイズ以上でのご使用を推奨します。
解像度が低いディスプレイではそれに合わせたウィンドウサイズで起動しますが、
設定項目の表示が乱れる場合があります。
- 数あるリバーシ／オセロソフトの中でのGeneralReversiの特徴
世の中には無数のリバーシ／オセロソフトが存在します。
それらの多くは「強さ」に主眼を置いています。
しかしGeneralReversiは「一般化」に主眼を置いています。
「強さ」に主眼を置いたソフトの多くは「棋譜からの学習」を行います。
ここで「棋譜」は人間同士の対局のものや、人間対コンピューターの対局のもの、
コンピューター対コンピューターの対局のもの、など様々ですが、
共通して言えることは「棋譜という歴史的資産を利用して強くなる」ということです。
では歴史がないゲームについてはどうしたらいいでしょうか。
例えば「ボードサイズ8の平行型」や「ボードサイズ10」などです。
これらについては棋譜という歴史的資産がないため、学習を行うことができません。
自己対局により学習を行うことも可能なのですが、
無限のゲームの種類を想定しているので、敬遠せざるを得ません。
「一般化」に主眼を置いていると言っても人間が戦ってそれなりに手応えのある
コンピュータープレイヤーを作る必要があります。
そこで作者がとったアプローチは一般化リバーシに適用できるアルゴリズムの「選択」と「構築」です。
具体的に「選択」というのは「モンテカルロ木探索」のことを表しています。
アルファベータ法や反復深化法は基本的な手法として知れ渡っていましたが、
モンテカルロ木探索をリバーシ／オセロに適用したという例は見たことがありません。
モンテカルロ木探索は評価関数が不要という性質に加えて、
イテレーションを十分に大きくすれば最善の着手を行うことができるということが証明されています[1]。
（石差が最大の着手は行えないが、勝率が最大の着手は行える。つまり、必勝ゲームに対しては必ず勝てる。）
実際に、ボードサイズ4の場合は白必勝のゲームなのですが、
白プレイヤーとしてモンテカルロ木探索プレイヤーを選択し（イテレーションは10000）、
黒プレイヤーとしてソルバープレイヤーを選択しても（ランダム性はオン）、
モンテカルロ木探索プレイヤーは必ずソルバープレイヤーに勝つことができます。
しかし、モンテカルロ木探索は理論は非常に美しいのですが、速さの面で実用性に難がありました。
具体的には、ボードサイズ8の場合はそれほどリバーシ／オセロが強くない作者であっても勝ててしまいます＾＾；
そこで「構築」の話ですが、一般化リバーシ用にオリジナルの評価関数「Stable」を構築しました。
重み付きの確定石の数の差とムーバブルを考慮した評価値を返します。
この評価関数を利用したアルファベータや反復深化には作者は勝てなくなりました＾＾；
めでたし、めでたし？
- ゲームの解法
2007年にチェッカーが解かれたという論文がScienceに掲載され話題になりました[3]。
詳しくは読んでないですが、要約によると1989年から回し続けていたようですから、
20年近くかけてようやく解くことができたみたいです。
さて、リバーシ／オセロに関してはどうかというと、2014年現在では解かれていません。
ボードサイズ8の解法は難しいかもしれないが、ボードサイズ6なら簡単に解法できそう・・・、
そんなふうに考えていた時期が俺にもありました＾＾；
単純なアルファベータ法をプログラムし、まずはボードサイズ4の解法にチャレンジ。
これは比較的すぐに解くことが出来ました。
次はボードサイズ6の解法にチャレンジ。
しかし、いっこうに解ける気配がありません。
調べてみると1993年に交差型は2週間、平行型は5週間かけて解かれているということがわかりました[4]。
それから20年以上経ってコンピューターの性能もアップしているわけだし、すぐに解けないものでしょうか。
さらに調べてみると英語版Wikipediaの「Computer Othello」のページにて、
「ボードサイズ6のオセロは単純なミニマックス法で100時間以内に解ける」という記述を発見[5]。
なぜアルファベータ法よりも効率が悪いミニマックス法を使ってるんだ？という疑問は残りつつも、
ミニマックス法で100時間ならアルファベータ法にすればもっと速くなる、と確信する。
そしてGeneralReversiの開発において高速性を重要視するようになる。
アプローチとしては、ボードサイズ8の速さをFFO#40をベンチマークとして改善し、
結果として任意のボードサイズの速さが改善する、という方法をとりました。
開発初期ではFFO#40に1800秒かかっていましたが、最終的に7.3秒になりましたので、
250倍高速化できた、ということになります。
プログラミングの一般論としての高速化も勉強になりましたし[6]、
リバーシ／オセロプログラミング特有の先人の知恵なども勉強になりました[7]。
最終的にボードサイズ6は一日かからずに解くことができるようになりました。
めでたし、めでたし？
- 開発の経緯
- Mathematicaの動的インタラクティブ機能で一般化したリバーシを作って、
デモンストレーションサイトに投稿しようと思い立つ。
- 一般化リバーシのゲーム機能とアルファベータ法をMathematicaで実装する。
- アルファベータ法でボードサイズ6の解法を試みるも失敗。
- モンテカルロ木探索というアルゴリズムの存在を知り実装する。
- アルファベータ法（＋評価関数）もモンテカルロ木探索も弱かったが（作者が勝てる）、
特に改善もせず投稿し採択される[8]。
- 約2年が経過。
- C#を勉強しようと思い立つ。
- 一通りC#を勉強し終えた後[9]、実践的な勉強として一般化リバーシを作成しようと思い立つ。
- Mathematicaではなし得なかった「速さ」と「強さ」の実現を図る。
- 作者が自作のプログラムに負ける（嬉しくもあり悲しくもある。娘を嫁にやる気分？）。
- ボードサイズ6を一日かからずに解くことができるようになる。
- 初版リリース。
- Mathematicaの動的インタラクティブ機能で一般化したリバーシを作って、
- 各プレイヤーの速さと強さ
- 「Random」
説明不要だと思いますが、着手可能位置の中からランダムに着手しているだけです。
速さは一瞬で、このためプログレスバーでの進捗表示も行いません。
強さは最弱で、初心者であっても負けることはまずないでしょう。
作者による強さの評価：「最弱」
- 「Monte-Carlo」
初めて論文[1]を読んだときは非常にワクワクしたのを覚えています。
評価関数が不要という性質に加えて、
イテレーションを十分に大きくすれば最善の着手を行うことができる、
なんて素敵なアルゴリズムだ、と。
しかし、実際に実装してみるとそれほど強くはありませんでした。
イテレーションを大きくすれば強くなるのは事実なのですが、
現実的に待てる時間というのは限られています。
ボードサイズ8に関して言えば、イテレーション10000まではストレスなく対局できますが、
作者よりも弱いです。
少し待ち時間がかかるのを我慢してイテレーション100000とも対局してみましたが、
やはり作者よりも弱いです。
作者による強さの評価：「弱」
- 「Alpha-Beta」と「Iterative-Deepening」
アルファベータと反復深化は置換とMTD(f)の別で計4種類ありますが、
深さが一緒なら強さも一緒になります。
強さが一緒なら速い方がいいに決まっています。
作者が速さを評価したところ、速い方から順に以下のようになりました。
- Alpha-Beta MTDf
- Alpha-Beta Transposition
- Iterative-Deepening MTDf
- Iterative-Deepening Transposition
ただ、「Alpha-Beta MTDf」はプログレスバーでの進捗表示が割合を表示しているのではなく、
「思考中ですよ！」ということを表すために床屋さんの看板のようにグルグル回ります。
そして思考が終わると突然止まります。
なので、遅くても進捗表示が割合で表示される方がいい、という場合は他のプレイヤーを選択してください。
ただ、「Alpha-Beta MTDf」は「ログ」タブを表示すれば「思考中ですよ！」以上の情報を得ることができます。
強さについては、作者は深さ10（評価関数はStable）には勝てません。
速さについては、深さ10の場合であってもストレスなく対局することができます。
参考までに、作者が速さを評価した際の深さ10の場合の最速設定を載せておきます。
- プレイヤー：Alpha-Beta MTDf
- 深さ ：10
- 順序閾値 ：3
- 置換閾値 ：3
- Alpha-Beta MTDf
- 「Solver」
ソルバープレイヤーはコンピューターの計算能力をフル活用したプレイヤーです。
ボードサイズ8のリバーシ／オセロでは全64マスのうち初期配置の4マスを除いた
60マスに両者が着手を行うことになります。
この60マスのうち、最初の20手を「序盤」、中間の20手を「中盤」、最後の20手を「終盤」、
と呼びますが、ソルバープレイヤーでは終盤を完全に読み切ることができます。
なので、対局相手は序盤・中盤で有利な状態にしておき、なおかつ終盤ではミスを最小限に抑える必要があります。
強さについては、ベースプレイヤーにもよりますが、ベースプレイヤーが上記の設定であれば、
人間は勝てないのではないでしょうか。
速さについては、深さ20の場合であってもストレスなく対局することができます。
参考までに、作者が速さを評価した際の深さ20の場合の最速設定を載せておきます。
- プレイヤー ：Solver MTDf
- 深さ ：20
- 順序閾値 ：6
- 置換閾値 ：9
- ベースプレイヤー：上記の「Alpha-Beta MTDf」の最速設定
たまに勝てる程度でした。
作者による強さの評価：「最強」
- プレイヤー ：Solver MTDf
- 「Random」
- マルチプラットフォーム
「Visual Studio」で開発したプログラムはWindowsでしか動かないと思っていませんか？
実はそんなことないんです。
開発言語であるC#は標準化団体によって標準化されており、誰でも処理系を作ることは可能なんです。
ただ、Windowsの開発元であるMicrosoftが例えばLinux向けの処理系を作成することはありませんでした。
その状況を打開したのがLinuxにおけるデスクトップ環境GNOMEの開発者として知られるイカザでした。
彼は「Mono」という.NET互換の環境を実現するオープンソースソフトウェアを開発しました[10]。
作者はGeneralReversiの開発において、当初Windowsのみをターゲットとしていました。
ですが、Monoの存在は知っており、モノは試しということでLinuxにMonoをインストールし、
GeneralReversiを実行してみました。
すると、なんといきなり動いたではありませんか！
細かいところで挙動が違うということはありましたが、大した問題ではありません。
大した問題ではありませんが、将来の修正を期待して、Monoプロジェクトに対してバグ報告をしておきました。
- CheckBox with button appearance can not align text in Linux (Windows can) [11]
- TextBox with tab text can not show correctly in Linux (Windows can) [12]
バージョン1.2.0.0より、Mono環境（Linux, Mac, etc.）に対応しました。 - CheckBox with button appearance can not align text in Linux (Windows can) [11]
- オープンソース
GeneralReversiはバージョン1.2.0.0より前はソースコードを公開していませんでしたが、
バージョン1.2.0.0のリリースに際してGitHubに公開リポジトリを作成しました。
ライセンスはGPLv3または全後方とします。
神様！仏様！ストールマン様！に感謝！
少し脱線しますが、作者が好きなイカザの言葉を紹介します。
「Cでプログラミングするには人生は短すぎる（Life is too short to code in C.）」
つまり、「C#を使え！」ってことです。
しかし、当の本人イカザは処理系を作っているわけですからCから離れることはできません。
つまり、自分が犠牲になって人生を短くすることによって、今後の人類の人生を長くしてくれているのです！
神様！仏様！イカザ様！に感謝！
