著者

野下浩平 飯田 崇仁

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.3, pp.708-713, 2002-03-15

---

本論文は,ゲームにおける解手順の定義を一般化し,その応用としてある形の詰将棋問題をすべて数え上げた結果を示す.この問題は,$3?times 3$ の矩形の中に玉のほか金と銀の8枚を配置した「金銀図式」である.これは,詰将棋の専門家によって長年数え上げの対象として研究されてきたが,その完成にはほど遠い状態にあった.ここで提示した方法に基づいて数え上げを実行し,その結果,詰手数の長い問題を含む多くの新しい問題を発見することができた.ここで最も難しい点として,解手順の標準的な定義を用いると,人間(専門家)がほぼ正しいと認める問題が数え上げの中で捨てられることがある.そこで,解手順の定義を一般化して,軽微な不完全さを持つ問題も許すようにする.金銀図式の数え上げは次のように進む.将棋盤で可能な28個の位置における問題図をすべて数え上げる.その中から王手でない図,玉が詰む図を選択し,さらにその中から,別解(余詰)のないという意味で完全な図を求める.最後に,完全でない図の中から,不完全さが軽微な問題で,専門家が正しいと見なすようなものを選ぶ.

著者

三島 健 櫻井 英俊 野下浩平

雑誌

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

巻号頁・発行日

vol.2006, pp.136-142, 2006-11-10

---

ゲームHexは、先手必勝手順の存在が証明されているが、具体的な必勝手順を示すことは長年の研究課題である。本稿では、石の連結性を定義するための新しい概念として、δ連結を提案し、それに基づいて、連結に関与する領域を拡張するための新しい技法δ拡張を導入する。この技法の応用として、従来の技法で記述するには複雑すぎるとされていた8×8盤面の初手63 に対する必勝手順を示す。また、この技法の強力さを示す例として、8×8盤面の初手54 に対する野下の必勝手順(2005)を大幅に簡単化する。同様にして、9×9 盤面に対する必勝手順を示すことができるが、本稿ではその証明木を示す(現在細部のチェック中)。

著者

伊藤琢巳 野下浩平

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.35, no.8, pp.1531-1539, 1994-08-15

参考文献数

8

被引用文献数

18

---

伊藤と野下がそれぞれ独立に開発した詰将棋プログラムItoとT2は17手以下の短篇の問題で人間のエキスパートよりかなり速く解く。ほかのプログラムとは比較にならないほど速い。これまでコンピュータが解けなかった中篇間題や100手を越える長篇問題もかなり解ける。数多くの問題を解いて得た実験データにより両方のプログラムの特徴を明らかにした。T2はしらみつぷし的な縦型探索で、相対的に短い手数の問題に対して正解率が高く、一方Itoは選択的な横型探索で、比較的長い手数の問題も解ける。また余詰を検査するプログラムを作り、実用に使えることを示した。

著者

三島 健 櫻井 英俊 吉元 昭裕 野下浩平

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.49, no.12, pp.4007-4015, 2008-12-15

---

ゲームHexでは,具体的な必勝手順を求めるために,様々な数学的技法が提案されている.8×8や9×9など大きい盤面に対する必勝手順を導くためには,これらの技法に基づいたシステムで人間とコンピュータの共同作業ができるものを実装する必要がある.本稿では,与えられた局面に対してユニオン連結性を判定するプログラムAとBを提示する.プログラムAは局面表を用いたAND-OR探索に基づくものであり,Hex特有の着手選択アルゴリズムにより強化した.プログラムBは,さらに仮想準連結などを組み込んで改良したものである.これらのプログラムは,実行時間と探索節点について評価する.ベンチマーク問題として,Noshitaによる7×7と8×8の必勝手順に現れる約40種類の難しい問題を選んだ.我々の実験結果によると,これらの局面の正しさは,非常に速く検証できた.このことは,我々のプログラムが実用に使えるということを意味する.着手選択(順序付けと先行排除)は,人間の熟練者と同程度に正確であると評価できる.本稿の実験結果をみると,我々のプログラムは,8×8以上の必勝手順の検証・発見のための対話システムを開発する際に最も基本的な道具として使えることが分かる.

著者

長島 紀子 中山 泰一 野下浩平

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.39, no.6, pp.1581-1586, 1998-06-15

---

ゲーム木を探索する場合,異なる枝に同一局面が発生することが頻繁に起きる.この探索の重複を避けるため,局面表(ハッシュ表)に局面を登録し,計算結果を再利用するという手法がよく用いられる.ゲーム木の並列探索するときにも,上記のハッシュ表をプロセッサ間で共有できれば,異なるプロセッサ上で計算した結果が利用でき,計算時間の短縮が期待できる.本研究では,まず,分散メモリ型並列計算機(NEC Cenju?3)上に分散共有ハッシュ機構を設計・実現した.続いて,具体的なゲーム木探索問題としてオセロゲームの先手必勝後手必勝の決定問題を取り上げ,分散共有ハッシュ機構の評価実験を行った.実験の結果,たとえば7×5盤のオセロゲームでは,分散共有ハッシュ機構の導入により約30%計算時間が短縮されることが示された.

著者

林山 剛久 柳井 啓司 野下浩平

雑誌

情報処理学会研究報告コンピュータビジョンとイメージメディア(CVIM)

巻号頁・発行日

vol.2002, no.34(2002-CVIM-133), pp.161-168, 2002-05-09

---

テレビ放送からの自動情報抽出の研究の一例として、本研究では、囲碁対局テレビ番組から画像認識によって自動的に対局棋譜を生成するシステムを提案する。システムは、囲碁対局番組の画面画像を取り込み、画面中の囲碁盤の位置を検出し、置石(囲碁盤上に置かれている石)を検出して、囲碁対局の棋譜の自動生成を行う。対局中の画面画像を認識する際には、対局画面とそれ以外の対局には直接無関係な画面の識別や、囲碁盤上に現れる指し手の手や頭などの置石以外の物体の除去などの、囲碁対局テレビ番組の特有の問題点に対する対処を行う。我々は、実装したシステムを用いて、実際の11対局分の囲碁対局番組に対して実験を行い、96%の適合率と83%の再現率を得た。

著者

林山 剛久 柳井 啓司 野下浩平

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告コンピュータビジョンとイメージメディア(CVIM) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.34, pp.161-168, 2002-05-09

被引用文献数

4

---

テレビ放送からの自動情報抽出の研究の一例として、本研究では、囲碁対局テレビ番組から画像認識によって自動的に対局棋譜を生成するシステムを提案する。システムは、囲碁対局番組の画面画像を取り込み、画面中の囲碁盤の位置を検出し、置石(囲碁盤上に置かれている石)を検出して、囲碁対局の棋譜の自動生成を行う。対局中の画面画像を認識する際には、対局画面とそれ以外の対局には直接無関係な画面の識別や、囲碁盤上に現れる指し手の手や頭などの置石以外の物体の除去などの、囲碁対局テレビ番組の特有の問題点に対する対処を行う。我々は、実装したシステムを用いて、実際の11対局分の囲碁対局番組に対して実験を行い、96%の適合率と83%の再現率を得た。In this paper, we present an image-recognition system for generating Go-kifu (i.e., Go-records) automatically from games played by human professionals on a TV program. The system takes screen images of a TV program every several seconds, determines the position of the Go-board, and detects Go-stones played on the board. The system deals with several problems encountered on the TV program. It has to remove several types of noise like players' heads or hands, and discriminate a scene of the game from other various scenes like conversations by commentators. We have implemented the system, and performed experiments for eleven games on the TV program, whose results show high performance of the system. In particular, the precision and recall rate are 96% and 83%, respectively.