Algorithmic Approach for Combinatorial Game Theory
Algorithmic Approach for Combinatorial Game Theory
复制标题
组合博弈论的算法方法
DOI：
10.11509/isciesci.65.10_415
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
小野 廣隆
中科院分区：
文献类型：
--
作者：
木谷 裕紀;小野 廣隆
本稿では組合せゲームに対するアルゴリズム論的アプローチに関して解説する. 一般にゲーム対戦における自然な興味は 「どのプレイヤが勝つか?」 であるが, この問いはややあいまいである. それはゲームをプレイするプレイヤの習熟度や時の運をはじめとしたさまざまな要素が考えられるためである. 一般のゲームにおいては有利, 不利を論じる程度はできても断定的な答えを出すことはできない. そのようなあいまい性を排除するため, これを 「組合せゲーム」,「お互いが最善手を着手」 という二つの限定を行うことにすると,「どのプレイヤが勝つか?」 はどのゲームにも答えがあるものとなる. しかしながら当然, 答えがあることとその答えが具体的にわかることは等価ではない. その答えにたどり着くためにどのような計算を人間ないし, コンピュータが行う必要があるのか考える学問体系が (組合せゲームにおける) アルゴリズム論的アプローチである. ニムを例に説明する. ニムは各プレイヤが自分の手番にいくつかの山から一つの山を選んで石を取り除き, 最後に石を取り除いたプレイヤが勝利するゲームである. このゲームは代表的な (有限の) 組合せゲームであり, 組合せゲームであるがゆえに, ツェルメロの定理が適用できる [16]. ツェルメロの定理は 「有限の組合せゲームは先手必勝または後手必勝または引き分けである」 という定理である. このツェルメロの定理が示すように組合せゲームはゲームの帰結, つまりどちらのプレイヤが必勝か判定可能であるゲーム群である. ツェルメロの定理は, ゲームの状態遷移を木上で表したゲーム木を用いた議論により証明することができるが, その議論をさらに進めると必勝判定自体ができることになる. 必勝判定アルゴリズム設計の観点からみると, ニムの場合, 任意の石山の数に対していずれのプレイヤが勝つかを判定する仕組みがアルゴリズムであり, 本特集でもいくつかの記事で触れられているように排他的論理和を計算することによる判定アルゴリズムが存在する. ほかのゲームではどうだろうか. いわゆる〇× ゲーム (三目