Application of game-tree searching algorithms to parallel selection

博弈树搜索算法在并行选择中的应用

• 批准号: 12680337
• 负责人: NOSHITA Kohei
• 金额: $ 1.22万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12680337/
• 关键词: selection algorithm; parallel selection; game; searching algorithm; parallel comparison; complexity; 並列比較; 分散共有ハッシュ法; 比較回数

This research is concerned with the computational complexity of parallel selection problems, with specific interests in applying game-tree searching algorithms to obtain new results. Let U(n, t) be the minimum number of parallel comparisons required to select the t largest of n elements in the worst case on the parallel disjoint comparison model. Similarly, V(n, t) and W(n, t) are defined to be the minimum number to select the t-th largest element and the sorted t largest elements, respectively. We derive a new upper bound of U(n, t) for t 【greater than or equal】 4. This is proved by theoretical analysis, along with computational results obtained by our searching algorithms. Among other new techniques, a distributed shared-hashing method is designed and implemented on a parallel PC cluster. We also derive several upper, lower and optimal formulas of U(n, t) for some particular values of t. We show several relations between U, V and W, and make a table of the values of U, V and W for n 【less than or equal】 16. In this table, several nontrivial optimal values are determined. In the proof, our searching programs are also used. Finally, we show some results in other problems than selection by applying our searching algorithms.

本研究关注并行选择问题的计算复杂性，特别关注应用博弈树搜索算法来获得新的结果。设U（n, t）为在并行不相交比较模型的最坏情况下，从n个元素中选择最大的t个元素所需的最少并行比较次数。同样，定义V（n, t）和W（n, t）分别为选择第t大元素和排序后第t大元素的最小个数。我们导出了t大于等于4时U（n, t）的一个新的上界。理论分析证明了这一点，并通过我们的搜索算法得到了计算结果。在其他新技术中，设计了一种分布式共享哈希方法，并在并行PC集群上实现。对于某些特定的t值，我们也推导出了U（n, t）的几个上、下和最优公式。我们给出了U、V和W之间的几个关系，并制作了n <小于或等于16时U、V和W的值表。在该表中，确定了几个非平凡的最优值。在证明中，也使用了我们的搜索程序。最后，我们展示了应用我们的搜索算法在其他问题上的一些结果。

项目成果

野下 浩平: "ある選択問題の並列比較回数について"情報処理学会論文誌. 43・6. 1949-1955 (2002)

Kohei Noshita：“关于多项选择问题的并行比较数”，日本信息处理学会汇刊 43・6（2002 年）。

N.Sato, M.Shindo, K.Noshita & Y.Nakayama: "Some experiments on the distributed shared-hashing method for searching game-trees in parallel"Transactions of IPSJ. 42. 1198-1206 (2001)

N.佐藤、M.Shindo、K.Noshita

K.Noshita & N.Sato: "On the parallel rounds of a certain selection problem"Transactions of IPSJ. 43. 1949-1955 (2002)

野下

野下 浩平: "ゲームの解手順の一般化とある詰将棋の数え上げ"情報処理学会論文誌. 43・3. 708-713 (2002)

Kohei Noshita：“游戏解决程序的概括和特定Tsume Shogi的计数”日本信息处理学会交易43・3（2002）。

星由雄, 野下浩平, 柳井啓司: "反復深化探索に基づく協力詰将棋の解法"情報処理学会論文誌. 43. 11-19 (2002)

Yoshio Hoshi、Kohei Noshita、Keiji Yanai：“基于迭代深化搜索的协作 Tsume 将棋解决方法” 日本信息处理学会杂志 43. 11-19 (2002)。