Storong Othello Player by OCaml

OCaml のインストール

• Ubuntu の場合

  $ sudo apt install ocaml

• Mac の場合

  $ brew install ocaml

その他の場合は 公式ページ を見てください．

GUI で対戦をみたり，人間と対戦することもできますが，is-othello を参考にしてください．

使い方

• 準備

$ git clone https://github.com/hashi0203/Strong-Othello-Player.git
$ cd Strong-Othello-Player
$ make

• 審判サーバを準備

  $ ./reversi-serv -p 30000 -t 60 -r 10

  主なオプション

  • -p: ポート番号 (デフォルト: 3000)
  • -t: 各プレイヤの合計持ち時間 (デフォルト: 600秒)
  • -r: ラウンドの回数 (偶数のみ，デフォルト: 4回)
  • -help: ヘルプを表示

  先手後手を入れ替えて -r で指定した回数だけ勝負

• プレイヤを準備

  ランダムで手を打つプレイヤを用意

  $ ./reversi-random -H "localhost" -p 30000 -n COM

  主なオプション

  • -H: ホスト名 (審判サーバを立てたホスト名を指定，デフォルト: local host)
  • -p: ポート番号 (審判サーバを立てたポート番号を指定，デフォルト: 3000)
  • -n: プレイヤの名前 (デフォルト: Anon.)
  • -help: ヘルプを表示

  同様に自作のプレイヤも準備

  $ ./reversi-me -H "localhost" -p 30000 -n ME

  2人のプレイヤを用意したらゲームが開始する．

  タイムアップになると Fatal error: exception End_of_file が表示されて終了する．

戦略

• 前半，中盤，後半，終盤に分けて評価関数を作る
• αβ法で4から6手先読みする (後半まで)
• αβ法で13から17手先読みし，最善手を打ち続ければ自分が勝てるように置く (なければ後半の評価関数で4手先読みする)
• 開放度が低い石を返すと評価が高く，低い石を返されると評価が低い (前半)
• 角が取れていれば評価を高く，自分がとっていない角の周囲の3マスに自分の石を置いていれば評価を低くする (前半から後半)
• 自分の石が壁 (枠を除いて外側の空マスに面している石) を作っていると評価が低い (中盤)
• 確定石 (角のように相手がどう打っても返すことのできない石) が多いと評価が高い (中盤以降)
• 石と枠に囲まれた空きマスを打てば点数が高い (中盤以降)

工夫と議論

• αβ法の時は毎回評価関数を使って着手可能手をソートしてから探索を行うことで，枝刈りを増やして深くまで探索できる
• 終盤では勝率が高い手を選ぶのではなく，勝ち盤面を1，負け盤面を-1とする2つの値のみで評価するようにしたため，早い段階で枝刈りができる
  • 例えば相手の最善手が-1とわかった瞬間に残りの探索をやめる
  • 絶対に勝てる手がない場合は後半と同様の評価関数で4手先読みして一番いいものを選ぶ
• 着手可能手の個数などによって探索時間が大きく変わってしまうことがあるので，残り時間や着手可能手の個数を見て，探索の深さを適宜変更する
• 序盤の定石などを入れることで探索時間をさらに短縮できたかもしれないが，実装していない
• byte-code ではなく native-code を生成するようにコンパイル方法を変えることで，探索速度が速くなる
  • make clean して make し直すなどした場合に明らかに探索速度が速くなったりすることもあるが原因は不明
• 確定石の判断については 100% ではない
  • 確定石と判断するものは確実に確定石だが，確定石なのに確定石と判断されないものがある
  • 終盤は完全読みをするため，内部の確定石を正確に評価する必要性は低く，枠に近い確定石だけを正しく判断できるようにしたから
• 序盤は石を取らず，真ん中に置くようにしているが，それがうまくいくときは勝てて，うまくいかないときは勝てない