权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Searching algorithms with transposition tables and their applications

转置表搜索算法及其应用

基本信息

批准号：
15500021
负责人：
NOSHITA Kohei
金额：
$ 1.47万
依托单位：
The University of Electro- Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15500021/
关键词：
searching algorithm transposition table game hex 必勝法並列選択局面表技法計算量

项目摘要

This research is concerned with searching algorithms with transposition table techniques. We design and analyze new efficient algorithms and data structures, and apply them to several computing problems. Those problems investigated in this research are construction of winning strategies in the game of Hex, automatic generation of combinatorial puzzles, and gathering of images from the internet. The main result of this research is that we formulated a new notion named union-connection for constructing a winning strategy for Hex. Based on this notion, we developed a new technique combined with transposition tables, which enabled us to construct a simple winning strategy for 8x8 Hex. This solved one of the long-standing open problems in the research of games listed by van den Herik in 2002. We extended this notion as well as the searching techniques, and obtained more advanced results, which were published at the GPW workshop in 2006. As other applications, we designed and implemented algorithms for systematic searching of Number Place puzzles with the minimum number of clues, and algorithms for automatic generation of helpmate problems of Tsumeshogi. Those algorithms consist of Dancing Links by D.E. Knuth (2000) and Random Reduction Method by the author (1996) combined with transposition table techniques. We also implemented a system for gathering images from the internet by parallel distributed computation on a PC cluster.

本研究系探讨利用转置表技术之搜寻演算法。我们设计和分析了新的高效算法和数据结构，并将其应用于几个计算问题。本研究所探讨的问题包括：六角棋的获胜策略建构、组合谜题的自动产生、以及网际网路上的图像搜集。本研究的主要结果是，我们制定了一个新的概念命名为联合连接，以构建一个获胜的策略，为十六进制。基于这个概念，我们开发了一种新的技术，结合换位表，使我们能够构建一个简单的8x8十六进制获胜策略。这解决了货车登赫里克在2002年列出的游戏研究中长期存在的开放性问题之一。我们扩展了这一概念以及搜索技术，并获得了更先进的结果，这些结果在2006年的GPW研讨会上发表。作为其他应用程序，我们设计和实现的算法，系统搜索的数字的地方难题的最小数量的线索，和算法自动生成的助手问题的Tsumeshogi。这些算法包括D.E.的Dancing Links。Knuth（2000）和作者（1996）提出的随机约简方法结合转置表技术。我们还实现了一个系统从互联网上收集图像的并行分布式计算上的PC集群。