棋譜データベースに基づく将棋対局システムの開発

基于将棋记录数据库的将棋游戏系统的开发

• 批准号: 10143216
• 负责人: 石坂 裕毅
• 金额: $ 1.73万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (A)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10143216/
• 关键词: 将棋; 棋譜検索; データベース; ゲーム

本年度は,過去の対局データをそこに出現する局面により検索するためのシステムを構築した.データベースの検索に関する研究は,従来から盛んに行われているが,本研究では2つの検索手法について検討を行なった.1つ目の手法は,文字列パターン照合による検索である.この手法は,データベースとしてテキストファイルだけを保持しておけばよく,テキストエディタなどで簡単に追加や編集を行うことができるという利点がある.ただし,1棋譜当たり120局面生成される局面データを単純なテキストで表現すると,局面データベースが極めて大きなものになり,その分検索コストが増加するという欠点もある.そこで我々は,高速な複数文字列パターン照合機能を有するテキストデータベース管理システムSIGMAを用いた検索実験を行ない,テキストファイルによる局面データベース構築の可能性について検討を行なった.SIGMAでは,テキストファイルを1回走査するだけで複数のパターンの出現を検出することができる.さらに複数のキーワードからなる論理式を質問として与えることでより柔軟な検索を行うことができる.2つ目の手法は,転置ファイル法と呼ばれる手法である.検索が非常に速いことで知られており,大規模データベースにおける検索手法としてよく用いられているが,一般に,データベースの維持管理に対する手間と時間のコストが高いという難点がある.また,局面による棋譜検索では,駒を索引とした局面データの検索と局面を索引とした棋譜データの検索という2段階の検索が必要となるため,転置ファイルの管理はより繁雑になる.上に示した2つの手法の比較を行うために,1500対局,約17万局面分のデータベースを作成し検索速度の計測を行なった結果,盤上に40駒すべてを配置した局面検索を行った場合の検索時間は,SIGMAの場合で3.79秒,転置ファイルを用いた場合は0.16秒であった.また,盤上に一部の駒だけ配置した部分一致による局面検索においても,SIGMAによる検索時間は転置ファイルを用いた場合の検索時間の概ね数十倍程度のものであった.データベース管理の容易さと検索の柔軟さを考慮すれば,文字列パターン照合による検索が局面検索において十分有効であることが確認できた.

今年，我们已经建立了一个系统，可以根据其中出现的方面搜索过去的游戏数据。过去对数据库搜索的研究在过去已经广泛进行，但是在这项研究中，我们研究了两种搜索方法。第一个方法是通过字符串模式匹配进行搜索。该方法的优点是只能将文本文件作为数据库保存，并且可以使用文本编辑器轻松添加和编辑。但是，游戏记录的120个阶段以简单的文本表示。这是一个缺点，即数据库变得极大，因此搜索成本增加。因此，我们使用Sigma进行了搜索实验，Sigma是一个具有高速多弦模式匹配函数的文本数据库管理系统，并检查了使用文本文件构建阶段数据库的可能性。使用Sigma，可以通过简单地扫描文本文件来检测多种模式的发生。此外，通过给出由多个关键字作为问题组成的逻辑表达式，可以执行更灵活的搜索。第二种方法称为转置文件方法。它以其非常快速的搜索而闻名，并且通常在大规模数据库中用作搜索方法，但通常它的缺点是，维护数据库的时间很耗时且耗时。此外，在使用各个方面搜索游戏记录时，有必要搜索两个阶段：使用索引作为索引搜索功能数据并使用方面作为索引搜索游戏记录，这使得管理重定向文件更加复杂。为了比较上面显示的两种方法，我们共有1,500场比赛和大约170,000个事件。当我们创建一个数据库并测量搜索速度时，我们发现，当我们执行板上所有40个零件的相位搜索时，Sigma的搜索时间为3.79秒，而转置文件的搜索时间为0.16秒。此外，当我们使用部分匹配进行阶段搜索时，仅在板上的几个部分，使用Sigma的搜索时间大约是使用转置文件的搜索时间的几十倍。考虑到数据库管理的易度性和搜索的灵活性，可以证实使用字符串模式匹配的搜索在空间搜索中足够有效。

项目成果

Takeshi Shinohara: "Approximate Retrieval of High-Dimensional Data by Spatial Indexing" Discovery Science,Lecture Notes in Artificial Intelligence. 1532. 141-149 (1998)

Takeshi Shinohara：“通过空间索引近似检索高维数据”Discovery Science，人工智能讲义。

石坂裕毅: "棋譜データベースに基づく将棋対局システムの開発" 「発見科学」研究成果報告書. 252-255 (1999)

Hiroki Ishizaka：“基于游戏记录数据库的将棋游戏系统的开发”《Discovery Science》研究成果报告252-255（1999）。