2013年に表題のテーマでパワポを作っていたのですが公開することができないので、当時のパワポをベースに新たに記事を起こします。
合理的な意思決定を実現する上で役に立つ学問分野の紹介です。
【ゲーム情報学の意義】
ゲーム情報学とは、情報学の知識をゲームに適用することでゲームの解を得ようとする学問分野である。
現実とは異なり、ゲーム内では、意思決定を行う上で必要な情報が明確に定義されている。
そのため、意思決定に関する研究を行いやすい環境であり、ゲームの解を得るための方法を模索することで現実の意思決定にも応用可能な知見が得られると考えられている。
【囚人のジレンマの解】
ゲーム情報学の学会では、遺伝的アルゴリズムを使用して囚人のジレンマを解く試みが行われた。
囚人のジレンマとはゲーム理論における代表的な問いの一つである。
２人のプレイヤーがお互いに「協調」と「裏切り」の２つの選択肢を持ち、「裏切り」を選ぶことで相手がどちらの選択肢を選んだとしても「協調」を選んだ時よりも高い利得が得られるが、お互いに「裏切り」を選んだ場合はお互いに「協調」を選んだ場合よりも利得が少なくなる、というゲームである。
例としては、以下のような利得表となるゲームである。
このゲームを解くために使用された遺伝的アルゴリズムとは、１つの戦略を持つ複数のプレイヤーが何度も試行を繰り返す中で、高い利得を得られた戦略については次の試行でより多くのプレイヤーが使用するようにし、そうではない戦略は次の試行でより少ないプレイヤーが使用するようにする、というアルゴリズムである。
このアルゴリズムでは、最終的に多くのプレイヤーが採用した戦略が優れた戦略である、と判断する。
下記のグラフは遺伝的アルゴリズムの結果を示したものであり、横軸が試行回数（世代）であり、ある試行回数の時点で縦方向の長さが長ければ長いほどその試行回数の時点で多くのプレイヤーが使用する戦略であるということを指している。
「x00x」は「相手が裏切った時は自分も裏切りで返すが、それ以外の場合は協調する」という戦略であるが、試行回数が進めば進むほどこの戦略が優勢となることがわかる。
一方的に搾取されるのは避けるが、なるべくお互いに協調しお互いに高い利得を得られるようにする、という戦略が最終的には合理的になることが遺伝的アルゴリズムにより示されたのである。
【コンピュータ将棋のアルゴリズム】
コンピュータ将棋はプロ棋士を上回る実力を身に付けたとして注目を浴びている。
コンピュータ将棋にはゲーム木を高速で解くアルゴリズムが搭載されており、人間に対しては特に終盤の詰めの場面で優位性を見せる。
ゲーム木とは下記のようなものであり、交互進行ゲーム（交互に意思決定を行うゲーム）で用いられるゲーム理論の表記方法である。
下記のゲーム木では、○が自分の選択肢、□が相手の選択肢、数字が自分の利得としている。
自分は利得がなるべく高くなるように、相手は利得がなるべく少なくなるように選択肢を選ぶ。
相手はcとdならc(利得3)、eとfならe(利得2)を選択するため、自分はaを選択すれば利得3、bを選択すれば利得2となる。
そのため、自分は利得aを選択するのが最適となる。
将棋のように複雑なゲーム木が描かれるゲームでは、不要な探索を打ち切るためのアルゴリズムを搭載し、少ない時間でより適切な解を得ることが重要となる。
「前向き枝刈り」「ウィンドウ検索」「証明数検索」等のアルゴリズムが存在するが、ここでは最も基本的な「αβ法」について紹介する。
例えば、下記のゲーム木で、左から順番に探索を行うことを考える。
cを選んだ場合は利得は6となる。ではdを選んだ場合はどうなるか。
まず、d→jと選んだ場合の利得を考える。この場合は利得は6となる。
この時点で、相手にとってdがcよりも優れた選択肢ではないことが明らかになるため、相手がcを選択することが確定する。
よって、dについてd→kやd→lを探索する必要は無くなる(βカット)。
次に、c,d,eについて探索を終えた場面を考える。
自分がaを選んだ場合、相手はcを選び、利得は6となる。
自分がbを選んだ場合、相手がeを選ぶと、利得は5となる。
fの利得がeの利得未満の場合は相手はそれを選び利得は4未満となり、fの利得がeの利得以上の場合は相手はeを選択し利得は5となる。
よって、自分がbを選んだ場合、利得が5以下になることが確定し、bを選択することが合理的ではないことがわかるため、bについてb→fを探索する必要は無くなる(αカット)。
このように、αβ法を用いることで、少ない探索数で解を得ることが可能となる。
なお、データを予めソートすることで、αβ法でカットできる探索量を増やすことができる。
下記のように、将棋に比べて囲碁は選択肢の数が桁違いに多い。
そのため、ゲーム木を効率良く探索するアルゴリズムでは、プロ棋士に迫る実力を得ることができなかった。
そこで使われるようになったのが、モンテカルロシミュレーションである。
モンテカルロシミュレーションとは、乱数を用いて疑似的に試行を重ね、アルゴリズムを解かずとも解に近い結果を得る手法である。
モンテカルロシミュレーションは、下記の考慮を行うことで効果が増す。
- シミュレートでは、可能な限り現実的な手を打つ（完全にランダムに打つのは避ける）
- 有望な手や試行回数が少ない手を多く選ぶ（最終的に選ぶ可能性の高い手を多くシミュレートしたい）
モンテカルロシミュレーションを行い、高い利得を得られる選択肢を学習し、改良したモンテカルロシミュレーションを行い…を繰り返すことで、現在ではコンピュータ囲碁はプロ棋士を上回る実力となっている。
なお、モンテカルロシミュレーションは物理学・経済学等で広く用いられている手法であり、簡易なものであればExcelでも実施可能である。
【多数のプレイヤーが協調するゲームでの知見】
多数のプレイヤーが協調するゲームとして、サッカー（RoboCup Soccer シミュレーションリーグ）や、災害対応を想定したレスキュー（RoboCup Rescue シミュレーションリーグ）等が存在する。
これらのゲームからは、下記のような知見を得られている。
- 問題を解決するための情報を持つ者が指示を出すと良い。
- かけ声を使用することで、最小限の通信量で協調動作できた。（かけ声…短いメッセージ。詳細な数値・座標を使わない。）
- ボディーランゲージでも意思の疎通は可能である。ただし、表現の衝突や認識のタイミングのずれで正しく意図が伝わらないことがある。
- 一貫した行動目標を定める大域的な行動判断と、詳細な情報を持つ者による個別の柔軟な行動判断を組み合わせることが重要である。
【不完全情報ゲームでの知見】
不完全情報ゲームとは、自分が持つ情報を相手から隠すことができるゲームのことを指す。
例えば、トランプを用いたゲーム（ブリッジ）では、「相手がこちらの情報を推測しようとしている場面で、相手の推測を誤らせるように情報を公開することで、相手のミスを誘発することが可能である」という知見を得られている。
