抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2500000, indirect: 750000)
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.