少し遅くなってしまいましたが...！10/28 (土) ～ 10/29 (日) にかけて仙台 IT 文化祭というイベントに参加/登壇してきました。人生初めての仙台、人生初めての東北。新しいところに踏み入れるのは不思議な緊張感があっていいものですね！
ドキドキ・ライブコーディング対決 出張編
いつもは北陸の勉強会で行っていて、若干恒例になりつつある C# 大好き MVP によるドキドキ・ライブコーディング対決 !!。プログラミングを見て/聞いて/一緒に考えて楽しむエンターテイメントとして行っています。今回は出張編と題して、年始に BuriKaigi 2017 in Toyama で行ったのと同じ 4 色オセロ対決 をメインに行いました。お品書きはこんな感じ。
- ライブコーディング対決
- FizzBuzz
- 閏年の判定
- 2017/10 のカレンダー表示
- 4 色オセロ対決
- 各自のアルゴリズム紹介
- 実際に勝負
ライブコーディング対決って言っても、問題が簡単だと思うじゃないですか！でも案外瞬間的には出てこないもので、出題されて 2、3 分で答えを出すのって案外難しいんです。出題される問題を本当に知らないので、本当に毎回テンパります。でもきっとそれが面白く映るんだと思います。実際ほとんどの方が笑ってくださっていましたし、所変えてもポジティブな感想や反響は非常に多かったです。セッションを聞いて、プログラミングを始めるために Visual Studio をインストールした！という方が出たくらい！
4 色オセロのアルゴリズム
さて、今回のメインだった 4 色オセロ対決。前回の対決での僕はと言えば、4 色オセロの強い AI を作ることができず、結果魂を悪魔に売って強いと思われる人の AI を勝手に使うという手法に出ました...w これは正直全然良くないアプローチで、確実に勝てるとは限りませんでした (実際負けた)。
なので今回は考えを大きく改めて、勝ち筋を再現するというアプローチを取ることにしました。これは以下のような発想で作ったものです。
- 自分の手を乱数で決定
- 自分の手はすべて履歴として記録
- 他人のアルゴリズムと事前に 1000 回ほど戦っておく
(このぐらいやると大体数十回は勝つ) - 勝った手筋のうち、最終的に一番自分の石が多く盤面に残っている手筋を選択
- 実際の対決の際には、選択された手筋をそのままトレースして打つ
この手法は、比較的弱いサンプル AI に対して以下のような大勝することもできました。
ただし、これには相手が自分の手に対して必ず同じ答えを返してくるという前提が必要です。もう少し別の言い方をすれば、相手が乱数で決まるアルゴリズムを使ってこないことが条件となります。しかし、これはエンジニア心理としてほとんど発生しないと踏みました。この手のアルゴリズムを考える場合、大抵のエンジニアは自分の手を神に委ねるような真似をしません。「お前がそう打つなら、俺はこう打ってやるぜ」を地で行きます。乱数のないアルゴリズムであれば自分の手に対して毎回同じ答えを返すので、事前に評価された結果と同じ未来が訪れます。あとはランダムに打つ自分のアルゴリズムが試行回数内に勝つことを祈るのみですw
本番では別のところに予期せぬ問題 *1 が発生して上手くいきませんでしたが、イベント終了後に不整合を修正したら僕の AI が勝ちました！
我々が勝手に考えたルールの 4 色オセロなので、定石なんてものはありません。また、総当たりに近い計算をしてしまうと (計算量が多くなってしまうために) 現実的な時間で結果を出せなくなってしまいます。そういったところに対して、勝率と実装コストのバランス両方を考慮したアルゴリズムを考えられたと思います。
セッション資料
関連記事
東北関連の与太話
ずいぶんと話を戻せば、僕がプログラミング関連の勉強を頑張るようになったのは東北大震災が大きなキッカケのひとつでした。当時の僕は Windows のデスクトップアプリしか作ることができず、Web/クラウドの知識も一切なかったので、エンジニアであるにも関わらずプログラムを使った即効性のある支援が一切できませんでした。それがとっても悔しくって Web/クラウド関連に触れるようになりました。それから数年経って東北の地に行って、何もできなかったあの頃を懐かしいなぁと思うのと同時に、もうちょっと頑張らなきゃなって少しヤル気が出ました。
