著者

山本 一成 竹内 聖悟 金子 知適 田中 哲朗

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.42-48, 2010-11-12

---

本稿では,将棋においてMagicBitboardを適用する手法を提案する.Bitboardはチェスなどの二人ゲームのゲーム木探索で盤面を表現するのに適した手法であり,チェスや将棋の強いプログラムで広く使われている.MagicBitboardは従来のBitboardの手法に比べ,よりシンプルなデータ構造を管理するだけで利きを算出することが可能となる近年開発された手法である.MagicBitboardはチェスの盤面が一つの64ビット整数で表現できることに依存した手法であり,盤面のマス目の数が81マスの将棋で,MagicBitboardを使う方法は知られていなかった.しかし我々は初めて,複数の整数で表現された盤面においてMagicBitboardを使って利きを算出する手法を発明し,Bonanzaを使った実験で我々の手法の効果を示した.

著者

草野 一彦 成澤 和志 篠原 歩

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.108-113, 2010-11-12

---

立体ピクロスとは任天堂が2009年に発売した同名のゲームに収録されているパズルである.問題として立方体のブロックが積み重なった直方体が与えられ,ブロックに描かれたヒントに従って不要なブロックを削り,隠されたカタチを取り出すのが目的である.本稿では,3SATからの帰着により,立体ピクロスの解の存在判定がNP完全であることを示す.また,立体ピクロスの高さを1に制限し,普通数字・丸数字・四角数字を区別しない場合には,解の存在判定が多項式時間で行えることを示す.

著者

石関 匠 松浦 昭洋

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.101-107, 2010-11-12

---

「量子三目並べ」は2002年に物理学者AllanGoffらによって提案された,量子力学の概念を利用した二人完全情報零和ゲームである1).本稿では,直線状の三目を先に完成させれば勝ちとする古典的な三目並べの勝利基準(完勝と呼ぶ)と,両者同時に三目完成させたとき,完成した三目の着手番号の最大値が小さい方を勝ちとする勝利基準(辛勝と呼ぶ)の下で量子三目並べの必勝法の解析を行い,本ゲームが完勝の基準の下では引き分けであり,辛勝の基準の下では先手必勝で勝利に必要な手数が9手であることを示す.さらに,探索の高速化とある自然な改訂ルールの下での必勝法についても述べる.

著者

森田 悠樹 橋本 剛 小林 康幸

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.36-41, 2010-11-12

---

コンピュータゲームプレイヤの研究ではゲームの解明も盛んに行われており,近年ではチェッカーが解かれて大きな話題となった.次のターゲットはオセロが有力である.証明数系の探索がオセロにも有効で特にWPNSが良い結果を出すことが報告されている.本稿では単純な2種類のαβ探索とWPNSの比較実験を行った.パブリックドローと呼ばれる定石から作った残り19から25石の難解な局面を使っている.その結果,ソートを行わないαβ探索の性能はかなり落ちるものの子ノードの数でソートしたαβ探索はWPNSと同等の性能を出すことが示された.またWPNSの探索における弱証明数計算の占める割合のデータを示した.それによりオセロ完全探索に向けた今後のより難解な局面の探索でWPNSなど証明数系探索が主役になりにくいことが予想された.また新たに分枝数を閾値とするαβ法を提案し実験を行った.

著者

浦 晃 横山 大作 近山 隆

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.134-141, 2010-11-12

---

従来の並列ゲーム木探索手法の多くは、プロセッサが数十という環境を想定しているため、計算量を抑制することに配慮するあまり並列度が低下し、多数のプロセッサを有効利用できない。本稿では、数百以上のプロセッサからなる環境において大きな速度向上を実現するために、必要なタスクの実行を妨げないようにスケジューリングしつつ、必要性が明らかでないタスクも投機実行することを提案する。提案手法を実装して評価したところ、タスクの粒度と優先度の設定が適切であれば、大きな速度向上が得られることがわかった。また、逐次探索プログラムとの対戦でも提案手法の優位性を示すことができた。

著者

瀧澤 武信

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.55-58, 2010-11-12

---

世界コンピュータ将棋選手権は,第8回は,上位予選,下位予選と決勝,第9回以降は1次予選,2次予選,決勝という形で行われている.第11回は,決勝に10チームが参加して行われたが,通常は決勝に8チームが参加して行われている.ここでは,決勝8チーム制が定着した2002年から2010年までの決勝における先手の勝率,初手から6手目までの流れ,戦形別成績について分析する.