Loading article…
『ゲーム、パズル、計算』は、ロバート・ハーンとエリック・デメインが執筆し、2009年にAK Peters社から出版された、ゲームの複雑性に関する書籍です。ハーンの博士論文を改訂したもので、デメインが指導しました。 [ 1 ] [ 2 ]アメリカ数学協会の基本図書館リスト委員会は、学部生向けの数学図書館への収蔵を推奨しています。 [ 3 ]
ゲーム、パズル、計算は、 2人用および多人数用の組み合わせゲームで論理パズルを解いたり、最適な決定を下したりする際の計算複雑性理論に関するものです。純粋に数学的な目的で考案されたものではなく、現実世界でプレイされているゲームやパズルに焦点を当てています。[ 2 ]この分野では、数独、ラッシュアワー、リバーシ、チェス（任意の大きな盤面を持つ一般化された形式）などのパズルやゲームは、計算が困難であることが一般的です。数独はNP完全、ラッシュアワーとリバーシはPSPACE完全、チェスはEXPTIME完全です。本書は、このような新しい結果を証明するだけでなく、非決定性制約論理、つまり完全性証明に以前使用されていたより古典的な問題よりもゲームプレイによく似た抽象的な組み合わせ問題を使用して、そのような結果を証明するための統一的なフレームワークを提供することを目指しています。[ 1 ] [ 3 ]
本書は 3 つのパートに分かれています。最初のパートは制約論理に関するもので、[ 3 ] [ 4 ]これは、各頂点が十分な総重みを持つ入力エッジを持つように、無向グラフのエッジに方向を割り当てるものです。 [ 1 ] [ 3 ]本書の 2 番目のパートでは、制約論理をさまざまな現実世界のゲームやパズルの難しさの新しい証明に適用し、[ 3 ] [ 4 ] 各ケースで、制約論理インスタンスの頂点とエッジがゲームの動きとピースによってエンコードできることを示します。これらの難しさの証明の中には、以前に知られていた証明を簡略化したものがあり、そのうち 10 個は新しいもので、特定のマルチプレイヤー ゲームでの最適なプレイが決定不能問題になる可能性があるという発見も含まれています。[ 1 ]本書の 3 番目のパートでは、ゲーム複雑性に関する既知の難しさの結果の概要を提供し、[ 3 ] [ 4 ] 1979 年の書籍Computers and Intractabilityからのゲーム複雑性に関する完全な問題のはるかに短いリストを更新しています。付録では、この分野に馴染みのない読者のために、本研究で必要となる計算複雑性理論の手法について概説している。[ 3 ]
本書は主にこの分野の研究者向けの研究モノグラフおよび参考書であるが、評者のオスウィン・アイヒホルツァーは、ゲームの数学とその複雑性に関心のあるすべての人に本書をより広く推薦している。[ 2 ]リリャナ・バビンコストワは、 『ゲーム、パズル、計算』は楽しく読めるものであり、「ゲームと計算理論の間に橋を架ける」という目的に成功していると述べている。 [ 4 ]
レオン・ハークレロードはやや批判的で、本書はところどころ冗長に感じられると述べている[ 3 ]。ジョセフ・オルークは、現実世界のゲームにたどり着く前に抽象的な数学が何ページにもわたって続く構成のため、最初から最後まで通して読むのに適していないと不満を述べている[ 1 ]。しかし、ハークレロードとオルークは共に、本書はよく作られており、示唆に富む内容であるという点では一致している[ 1 ] [ 3 ] 。