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

分散的並列計算によるゲーム木の高速探索法

基于分布式并行计算的博弈树高速搜索方法

基本信息

批准号：
06680314
负责人：
野下浩平
金额：
$ 0.58万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-06680314/
关键词：
ゲームアルゴリズム並列計算分散システム詰将棋

项目摘要

本研究の目的は,多数のワークステーションによる分散的な並列計算システムの上で,長時間かかる非常に深いゲーム木を高速探索するためのアルゴリズムを開発することである.まず,ゲーム木の並列探索のための基本操作の組を定義して,それを分散システムの上で実現した.また,この基本操作の基本性能を実験的に評価した.使用したワークステーションの台数は最大で64である.次に,この分散システムの上で,ゲーム木の並列探索のためのマスターとスレーブからなる並列計算モデルを設定した.ゲーム木の事例研究として,詰将棋を解く問題を取り上げ,特に,遂次型アルゴリズムでは長時間かかったり,あるいはすべての問題を完全には解けないというような難しい問題群を選んだ.ここで開発した並列アルゴリズムによって,これまでの遂次型アルゴリズムで非常に長い時間のかかる問題を短い時間で解けることを示した.さらに,これまで解けなかった問題をはじめて解くことができた.特に,深さ優先にもとづく遂次型アルゴリズムで,これまで最も優れた性能をもつものと比較して,問題を解く時間が台数以上の倍率で短くできるような実例を示した.このように分散的並列アルゴリズムによって,ゲーム木の探索を著しく高速化できることを実証したのは本研究の主たる成果である.そのほか,多数のワークステーションが共有できる大域的ハッシュ表の設計と実現を行い.その基本性能を評価した.これはゲーム木の分散的並列探索における新しい研究課題を提起するものである.

The purpose of this study is to develop a distributed parallel computing system for a long time and a very deep and high speed exploration. The basic operations of the system are defined and implemented in a decentralized manner. The basic operation and basic performance of the system are evaluated. The maximum number of users is 64. Next, the distribution system is on top of the system, and the system is parallel to the system. A case study of a chess game is carried out, and the problem of solving the chess game is selected. In particular, the problem of solving the chess game for a long time is selected. This is a very long time problem and a short time solution. The problem is that we have to solve it. In particular, priority is given to the number of times the problem can be solved, and the number of times the problem can be solved is shown in an example. The research of the paper is aimed at speeding up the exploration and realization of the main achievements of the paper. The design and implementation of a wide range of design and implementation of the design. Basic performance evaluation. This is a new research topic that needs to be explored in a decentralized way.