Developers.IO 2017セッション「今からはじめるボードゲーム解析」で話しました #cmdevio2017

Developers-IO-2017-400x400

クラスメソッドが運営するIT系技術ブログDevelopers.IOのカンファレンスイベントDevelopers.IO 2017にて、セッション「今からはじめるボードゲーム解析」を発表しました。そのレポートです。

本発表は「組合せゲーム理論入門 -勝利の方程式-」の内容をベースに、組み合わせゲームがどのようなものかや、局面の帰結類をゲーム木を用いて導出する方法などについて話しました。内容について興味を持たれた方は、こちらの書籍をご参考いただければより詳細な内容を知ることができると思います。比較的読みやすい文章で書かれているため、初学者の方にもオススメです。

発表スライド

組み合わせゲームについて

2人の対局者が交互に手を打ち、どちらかの対局者が規則 に従った手を打つことが出来なくなるまで続くゲームのことを、組み合わせゲームと呼びます。

このゲームの特徴として、

  • 完全情報 : ゲームの局面(状態)が全て公開されている
  • 確定 : (サイコロなど)偶然に左右される要素がない
  • 有限 : 有限の手数によって必ずゲームが終了する

があります。

二人零和有限確定完全情報ゲームと近いゲームの性質を持っており、組み合わせゲームの理論を応用することも可能です。

組み合わせゲームの基本定理と帰結類

ある組み合わせゲームが与えられ、Aが先手とした場合、お互いが最善手を打ち続けた場合には、必ず

  • Aが必ず勝つ
  • Bが必ず勝つ

のいずれかとなります。

このことから、それぞれの対局者が最善手を打ち続けた場合、ある局面においてどちらが勝つかのパターンは、以下の4つとなります。この4つのパターンを帰結類と呼びます。

帰結類 名称 定義
N ファジー 先手番(Next)が必ず勝つ
P 後手番(Previous)が必ず勝つ
L どちらが先手番でも、左(Left)が必ず勝つ
R どちらが先手番でも、右(Right)が必ず勝つ

ゲーム木と帰結類

ある局面について、お互いの対局者の選択肢とそこから生まれる局面をゲーム木として描くことができます。このゲーム木を終局まで伸ばしていくと、ある局面から起こりうるあらゆる局面を洗い出すことができます。これに対して、それぞれの局面の帰結類を終局から帰納的に求めることで、大元の局面の帰結類を求めることができます。

局面の直和

複数の小さな局面を組み合わせた局面を、それぞれの小さな局面の直和と呼びます。

局面の直和に対して帰結類を求める場合、各直和成分から定性的に求められる場合と、局面の値と呼ばれるものを考慮する必要がある場合があります。

本発表では局面の値について詳細は触れず、局面の直和が帰結類にどう影響を与えるかを簡単に紹介しました。

感想

AWSやIT技術とは全く関係がない発表でしたが、思いの外多くの方にご参加いただけました。

ITエンジニアとして日々勉強していくことも重要ですが、勉強とは今の自分の環境の外側を知り、より自由になるためのものでもあるとも考えています。その意味で、今回は少し普段と離れた内容の発表を試してみました。

拙い発表でしたが、みなさまの興味を少しでも刺激することができれば、登壇者として幸いです。

AWS Cloud Roadshow 2017 福岡