Searching algorithms with transposition tables and their applications

本文研究了基于置换表技术的搜索算法。我们设计和分析了新的高效算法和数据结构，并将它们应用于几个计算问题。本研究调查的问题是在Hex游戏中获胜策略的构建，组合谜题的自动生成，以及从互联网上收集图像。这项研究的主要结果是，我们提出了一个名为联合连接的新概念，用于为海克斯构建获胜策略。基于这一理念，我们开发了一种与换位表相结合的新技术，这使我们能够构建一个简单的8x8十六进制获胜策略。这解决了van den Herik在2002年列出的游戏研究中一个长期存在的开放性问题。我们扩展了这个概念以及搜索技术，并获得了更先进的结果，这些结果发表在2006年的GPW研讨会上。在其他应用中，我们设计并实现了基于最小线索数的数位谜题的系统搜索算法和Tsumeshogi帮伴问题的自动生成算法。这些算法由D.E. Knuth（2000）的Dancing Links和作者（1996）的Random Reduction Method结合转置表技术组成。我们还在PC集群上实现了一个通过并行分布式计算从互联网上收集图像的系统。

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.