ゲームとパズルの計算量

Ｇａｍｅｓ，ｐｕｚｚｌｅｓ，ａｎｄ　ｃｏｍｐｕｔａｔｉｏｎ．

近代科学社
ロバート・Ａ．ハーン　エリック・Ｄ．ドメイン　上原隆平　

• 価格: 4,950円（本体4,500円＋税）
• 発行年月: 2011年08月
• 判型: Ａ５
• ISBN: 9784764903920

内容情報

[BOOKデータベースより]

著者たちは、ゲームやパズルの難しさの背後に隠された、数学的な理論を示している。ゲームやパズルの面白さの理由は、こうした理論によって説明できるのかもしれない。それだけではなく、彼らはゲームやパズルが強力な計算モデルを提供してくれることも示した。これはオートマトンや回路といった通常のモデルとは大きく異なっていて、計算というものについて考えるための新しい方法を与えてくれる。本書の第１部では、ゲームとパズルと計算を結び付けるために著者たちが開発した「制約論理」と呼ばれる単純で、かつ強力なフレームワークを解説する。次に、このフレームワークを人間が実際に楽しんでいるゲームやパズルのいくつかに適用し、それぞれの場合に、そのゲームが同じカテゴリーの別のゲームと計算量的に同程度に難しいことを示す。

１　一般のゲーム（制約論理の定式化；制約論理ゲーム；０人ゲーム（シミュレーション）；１人ゲーム（パズル）；２人ゲーム；集団ゲーム；第１部のまとめ）
２　実際のゲーム（１人ゲーム（パズル）；２人ゲーム；第２部のまとめ；おわりに）
付録（ゲームとその計算量のまとめ；計算量理論；決定性制約論理の具体的な活性化の列；制約論理のクイックリファレンス）