- 著者
- 橋本 剛 長嶋 淳 飯田 弘之
- 雑誌
- ゲームプログラミングワークショップ2002論文集
- 巻号頁・発行日
- vol.2002, no.17, pp.101-108, 2002-11-15
1 0 0 0 将棋の終盤における勝負手探索の応用
- 著者
- 梶原 羊一郎 橋本 剛 飯田 弘之
- 雑誌
- ゲームプログラミングワークショップ2002論文集
- 巻号頁・発行日
- vol.2002, no.17, pp.57-64, 2002-11-15
1 0 0 0 OA しりとりゲームのNP困難性
- 著者
- 田中 哲朗
- 雑誌
- ゲームプログラミングワークショップ2002論文集
- 巻号頁・発行日
- vol.2002, no.17, pp.140-142, 2002-11-15
「しりとりゲーム」はしりとりを完全情報化して定義したゲームである.完全情報ゲームなので,使用可能な文字の種類,使用可能な単語の集合と開始文字を決めれば,勝敗は決定可能である.「しりとりゲーム」の勝敗に関してはグラフとして表現した時に勝敗が同じで辺の少ないグラフに簡約する方法,文字の種類をnとしたとき,n=3までは定数時間で勝敗を決定可能であることが分かっているが,nを増やしていったときに,効率的に勝敗を決定するアルゴリズムがあるかは分かっていなかった.本論文では,しりとりゲームの勝敗の決定問題が文字の種類nに対してNP困難であることを示した.これにより,文字の種類によらずに,しりとりゲームの勝敗を効率的に求めるプログラムを書くのが困難であることが分かる.
1 0 0 0 多人数ゲームの順位を決定するゲーム木探索
- 著者
- 後藤 智章 乾 伸雄 小谷 善行
- 雑誌
- ゲームプログラミングワークショップ2002論文集
- 巻号頁・発行日
- vol.2002, no.17, pp.109-115, 2002-11-15