読者です 読者をやめる 読者になる 読者になる

interprism's blog

インタープリズム株式会社の開発者ブログです。

第2回 プログラミングコンテスト

プログラミング JavaScript Java

以前社内で開催されたプログラミングコンテストの第二回目が行われた。
今回も社員誰もが参加できるようにJavaを用いたもので行われた。
今回の課題は以下のようなものである。


オセロゲームのAIロジックを実装し、他の人のAIと戦って誰が一位になるかを競います。
相手と戦って勝つことが重要となります。  

  • 盤面は8x8
  • 置ける場所がない場合はスキップ扱い
  • 両者とも置ける場所がない場合はその時点でゲーム終了し、置かれている石の数で勝敗
  • 勝者は勝ち点3
  • 敗者は勝ち点0(減点なし)
  • 引き分けは両者に勝ち点1
  • 全AIの組み合わせで対戦する
  • 同じ相手とは先攻と後攻の2回戦う

具体的にはOthelloAIインタフェースの以下の3つのメソッドを実装することになる。

  • initメソッド
    各ゲーム開始時に一度だけ呼ばれる初期化処理。
    「自分の石(色)」が通知されます。
    黒が先行で白が後攻です。
  • getNameメソッド
    AIの名前です。ランキングに載るのでかっこいいのをつけましょう。
  • nextメソッド
    現在の盤の情報が渡されるので、その情報などを使って、次にどの位置に石を置くのかの情報を返してください。
    これがほぼAIのロジックになります。

G藤氏がJavaScriptベースの3Dライブラリを用いたオセロ対戦Webアプリケーションを作ってくれた。
Tomcat上で動作し、OthelloAIインタフェースを実装したJavaファイルをアップロードすることで、既にアップロードされたAIと対戦し、その様子を3Dで再生してくれるものだ。
自分の作った子(オセロAI)が戦っている様子を見れるのはなんとも感慨深いものであった。

約1カ月間のAIたちの死闘の末、最終的な結果はこうなった。

順位 結果
1 PhoenixAI(N部氏)
2 ディープラーニン君 4才(A藤氏)
3 ビットもんたかなり完全体10.100号(社長A木氏)
4 αβ03(Y越氏)
5 Future02(U本氏)
6 AI覚えてますか(S根氏)
7 いちか(K林氏)
8 ぜったいまけるこ1号の正反対のこ(I本氏)
9 切り込み隊長(M木氏)
10 GentleHirano(H野氏)
11 いっぱいとるこ(G藤氏)

I本氏はぜったいまけるこというあえて負けるAIを作成し、そのアルゴリズムを逆転させたAIを作ってきてくれた。
絶対負けるには自分が返す石の数を少なくし、解放度を下げるということのようだ。
その反対ということは石をいっぱい取って、解放度を上げるということになる。
他にもいっぱい取る子といった面白いAIも登場した。 いっぱい取るようにAIを作れば強くなると思いがちであるが、実際には弱くなるというのは自分もまた痛感したことだ。
最初は少なく取るようにして後で一気に逆転する方が勝てると言っていた方も居た。

U本氏はオセロが実際に強く、置く場所に対し経験から得た評価関数を与えてAIを作ってきてくれた。
実際にどういった打ち方をすれば良いのか分かるということは、AIの調整の上で一つのアドバンテージになるだろう。

Y越氏のAIはmin-Max法を用いたものからαβ法を用いたAIへ進化していった。min-Max法やαβ法はゲーム木探索で一般的によく用いられている手法だ。

このオセロボードは、評価を行うごとにcloneを呼んでインスタンスを再生成しなければならないため、3手や4手先までシミュレートすると非常に時間が掛ってしまう問題があった。
この問題に最も対応したのは社長A木氏とA藤氏のビットボードであっただろう。

社長A木氏はモンテカルロシミュレーションを長時間掛けて行い、学習していってデータを読み込むことも考えていてのコードだったようだ。
ビット演算を行い高速に処理を行っていた。

A藤氏もビットボードを用いていたが、より評価関数部分に力を入れていた印象を受けた。
さらに、A藤氏のビットボードは20手先まで数秒で考えることの出来る驚愕のAIであった。
ここまで先を読めるように作れるのは不可能を可能にするレベルに凄いことだと感じた。
ビットボードだとlongに格納できるためインスタンスへのアクセスが減らせるし、生成コスト、ビット演算のコストも低いことで高速化できたようだ。

N部氏は定石をBase64形式風に定石を登録しておき、それに一致した場合はその通りに打つという機能を備えてきていた。
ビットボードよりパフォーマンスは落ちるが配列を用いた自作ボードに履歴機能を実装することでインスタンスを再生成せずに戻して次を考えることで対処していた。

どのように盤面を評価することも重要であったと感じている。
完全読みと必勝読み、開放度、確定石、辺、星など勝つための評価の仕方は多様にある。

辺の評価に特に力を入れた16手読みであったN部氏のAIは20手先読みのA藤氏のAIに勝っていたので評価関数で勝敗が大きく変わるのではないかと感じている。
個人的に上位組を戦わせてみて分かったことであるが、N部氏の中盤読み手数を1つ下げるとA藤氏が勝利した。評価関数で多少アドバンテージがあっても読みが浅いと、相手がより早く必勝読みや完全読みに切り替わることになり、そこでの読みが甘いことで勝敗に影響すると予想される。
相手の読みが分かっていればそこで読みを増やして対抗できるようになるのではないかとも感じたがそこは色々試してみて明らかにしたい所だ。

オセロAIは実際に戦わせてみないと分からないため評価の重みづけが難しい。
以前の自分のAIに勝てるように作ったつもりが他には負けてしまうこともよくある。
そういった、トライアンドエラーの繰り返しも今回の課題で面白かった部分だ。
社長A木氏のようにモンテカルロ的にパラメーターを定めていくというのも面白そうであり、機会があったら自分のAIと実際の人間で対戦させて学習させていくのもありかもしれない。

コンテストは競い合ってお互い高め合うのも楽しいし、新しい発見も多いので次の機会にも参加していきたい。

PAGE TOP