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

Game informatics: Search of And-Or tree and Computational Complexity of games and puzzles

游戏信息学：与或树的搜索以及游戏和谜题的计算复杂性

基本信息

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

项目摘要

This research is concerned with Game Informatics. The themes are (1) computer search of And-Or trees, and (2) computational complexity of games and puzzles.Search of And-Or tree (game-tree) by computers generally use evaluation function. We define our game-tree model, and compare numbers of configurations to be searched by depth-first search at the designated depth of our game-tree under various evaluation functions. Our result shows that the number of configurations when an evaluation function is applied, which is as close as the perfect evaluation function with probability p (0<p<1), is polynomial time larger than that of configurations when the perfect evaluation function is applied.We obtained computational complexities of some games and puzzles, and the results have been published as papers, or presented in international conferences.

本研究涉及游戏信息学。（2）博弈和谜题的计算复杂性。计算机对与或树（博弈树）的搜索一般使用评价函数。我们定义我们的游戏树模型，并比较的配置数量进行搜索的深度优先搜索在指定的深度，我们的游戏树下的各种评价功能。结果表明，当采用概率为p（0<p<1）的最佳评价函数时，系统的配置数比采用最佳评价函数时的配置数多出多项式倍，得到了一些游戏和谜题的计算复杂度，相关结果已发表在论文或国际会议上.

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Helly numbers of polyominoes

多骨牌的 Helly 数

DOI：
10.1007/s00373-012-1203-x
发表时间：
2013
期刊：
Graphs and Combinatorics
影响因子：
0.7
作者：
Jean Cardinal;Hiro Ito;Matias Korman;and Stefan Langerman
通讯作者：
and Stefan Langerman

上書きハッシュ表の性質

覆盖哈希表的属性

DOI：
发表时间：
2013
期刊：
影响因子：
0
作者：
山口陽平;岩田茂樹
通讯作者：
岩田茂樹

Constant-time algorithms for sparsity matroids

稀疏拟阵的恒定时间算法

DOI：
发表时间：
2012
期刊：
Proc. of The 39th International Colloquium on Automata, Language and Programming (ICALP 2012) (1), LNCS
影响因子：
0
作者：
Hiro Ito Shin-ichi Tanigawa;Yuichi Yoshida
通讯作者：
Yuichi Yoshida

On computational complexity of graph inference from counting

论计数图推理的计算复杂度

DOI：
10.1007/s11047-012-9349-2
发表时间：
2013
期刊：
Natural Computing
影响因子：
2.1
作者：
Szilard Zsolt Fazekas;Hiro Ito;Yasushi Okuno;Shinnosuke Seki;and Kei Taneishi
通讯作者：
and Kei Taneishi

Constant-time approximation algorithms for the optimum branching problem on sparse graphs

稀疏图上最优分支问题的常数时间近似算法