Algorithmic Analyses of Card-Discarding Type Games

2021年8月15日 08:35

邦訳：手札消費型ゲームに対するアルゴリズム論的解析

木谷裕紀

（名古屋大学未来社会創造機構　特任助教）

------------------ keyword ------------------
理論計算機科学
アルゴリズム論
勝者判定
----------------------------------------------

【背景】ゲームの勝者判定は現実的に解ける計算時間でないものがほとんど
【問題】手札消費型ゲーム（ババ抜き，七並べなど）を対象
【貢献】勝者判定の計算量を解析．ゲームの高速解法を提案

　将棋やチェス，囲碁といったゲームは組合せゲーム（二人零和有限確定完全情報ゲーム）に分類されます．これらのゲームに対する自然な興味の1つが「（最善を尽くした場合の）ゲームの勝敗」です．本研究では，手札消費型ゲームと呼ばれるゲーム群に対して，「ゲームの勝敗」やその具体的な手順を計算するにはどのような計算を人間ないし，コンピュータが行う必要があるのかということを考えています．

　実をいうと，すべての（有限な）組合せゲームに対して，この計算方法は知られています．しかしながら上述のゲームを含む多くの組合せゲームに対して，実際のゲームの勝敗を計算すること（以下では必勝判定）が未解決です．一見このギャップは不思議に見えますが，それはどのゲームにも使える方法が必ずしも現実的に行うことができる効率が良い方法ではないことに起因します．たとえば，必勝判定できるがそのためには数億年以上の年月や数億台のスーパーコンピュータが必要である場合などは現実的に必勝判定ができるとは言えません．このように必勝判定は，その計算手順が存在するか否かだけではなく，その計算にかかる時間や計算に必要な計算領域がどの程度であるか考慮されている必要があります．この研究の一環として現在までに種々のゲームに対して，その必勝判定を行う「効率の良い」計算手順を求める研究やそのような効率の良い計算手順が存在しないことの証拠を示す研究が行われています．本研究ではこれらの研究をゲームに対するアルゴリズム論的解析と呼びます．

　本研究では「手札消費型ゲーム」に対象を絞って，その必勝判定のアルゴリズム論的解析を行いました．ここで，手札消費型ゲームとはあらかじめ配られた手札を条件にしたがって出していき，最初にすべての手札を出しきったプレイヤが勝ちというゲームのことを指します．たとえばUNOなどはこれに該当します．最後に簡単に本研究の成果の一部を下記で紹介します．

　まず，「大貧民」を簡易化したゲーム「単貧民」やそれをより実際の大貧民に近づけた「8切り単貧民」を2人で行った場合について，その勝者がどちらであるかという判定は現実的な計算時間で実行可能であることを示しました．また，手札公開で行う「ババ抜き」を提案し，その勝者判定について考えました．結果として，3人以下で行う場合の必勝判定を示したほか，4人で行う場合，とても興味深いことに，不完全情報下では嫌厭される札を積極的に引いたほうが良い状況が存在することを示しました．最後に七並べを題材に2人で行った場合に必勝判定を線形時間という高速な時間で行うことができる計算手順を示しました．さらに，七並べ本来のローカルルールなどを踏まえたグラフモデル下の七並べを提案し，その必勝判定が一定の条件下で計算困難であることを示しました．

（2021年5月31日）
（2021年8月15日note公開）

ーーーーーーーーーーーーーーーーーー
　取得年月日：2021年3月
　学位種別：博士（情報学）
　大学：名古屋大学
ーーーーーーーーーーーーーーーーーー

推薦文：（アルゴリズム研究会）
人工知能（AI）の性能評価に「娯楽ゲーム」が用いられることは多々あるが，ゲームそのものを対象とした研究はあまり行われていない．一方本論文ではいくつかの娯楽ゲームを対象とし，さまざまな解析を行うことで，ゲームのどの部分がコンピュータにとって難しいのかを明らかにしており，大きな将来性を持つ研究として推薦する．　

木谷裕紀（正会員）

研究生活：修士課程から博士課程へ進学する際，大学を変えたこともあり，やや戸惑うこともありましたが，有意義な3年間を過ごすことができたように思います．この研究は大学内や学外での多くのコメントを受けてブラッシュアップされました．指導教員の小野廣隆教授をはじめとするすべてのこの研究に携わってくださった方々へこの場を借りてお礼を申し上げます．