Research Unit for Computers and Games
Japan Advanced Institute of Science and Technology




PUBLICATIONS LIST SINCE April, 2005
Technical Reports

No. 215 Games and Arts

By H. Iida.

The lecture overviews three stages of games: playing, solving and appreciating. A ggameh is played as competitive sports. Some games can be solved. Then such a game becomes a gpuzzleh. In the stage of a puzzle the initial position is important as well as the terminal position which appears on the principal variation. People observe a master-piece puzzle as an art. Such a puzzle has harmony between the art of diversity and art of necessity, as a well refined game has a good balance between skill part and chance part. When emphasizing the art of games, the state transition (i.e., move) would be no longer discrete and unnecessary to have the beginning and the ending, i.e., endless.  Such games would be popular in the future, which is greater than TV games in the sense that people feel nature.

unknown pgs (2006) Symposium on Game Informatics, Keynote lecture, FIT2006, September 5, Fukuoka

More...

No. 214 Forward Game and Backward Game

By H. Kita and H. Iida.

This paper proposes a notion of so-called forward and backward game, and its properties are examined. In a forward game, search is to be performed from the initial position of a given game to a terminal position, while it is from a terminal position to an initial position in a backward game. The aim of the forward game is to determine the principal variation, which shows the game-theoretical value. In the backward game a reasonable initial is to be determined. In this study we have chosen the domain of small size of reversi as an experimental testbed to analyze the forward and backward games. We discuss several aspects of these games such as search space and the initial position.

6 pgs (2006) Game Informatics GI-15, Information Processing Society of Japan, March 7, Tokyo

More...

No. 213 Four-Person Reversi Yonin

By M. Fujii, H. Kita, T. Murata, J. Hashimoto and H. Iida.

This paper discusses four-person reversi called Yonin. Reversi is a game also called othello that is played by two players on an 8x8 board using 64 pieces of two-colour (Black and White) disks.   Yonin is an extension of the two-person reversi to four-person reversi that can be played by four players. Point in the extension is the restriction of the possible moves and the judge for the winner. The design concept of Yonin is quite simple and may be applicable to other domains.   In this study, we outline the design concept and consider the characteristics of the game Yonin. 

8 pgs (2006) Game Informatics GI-15, Information Processing Society of Japan, March 7, Tokyo

More...

No. 212 The Use of Killer Heuristics in Computer Shogi

By J. Hashimoto and T. Hashimoto.

This paper concerns the effective use of killer (move) heuristics in the domain of computer shogi. There are several different kinds of killer heuristics that are implemented for computer shogi. Little is known about the effectiveness of such killer heuristics. In this study, we define so-called ''effective ratio'' as an indicator for the assessment. The results of experiments performed with three killer heuristics give an interesting insight: the ratio of the passbest is proportional to the temperature of the phase, premovebest is effective around leaf nodes, and brotherbest keeps constant effectiveness in any condition.

8 pgs (2006) Game Informatics GI-15, Information Processing Society of Japan, March 7, Tokyo

More...

No. 211 Alternative Use of Two Transposition Tables for Game-Tree Search

By J. Nagashima, T. Hashimoto and H. Iida.

This paper concerns the use of transposition tables in game-tree search. The use of transposition tables enables a computer to efficiently search a game tree. Such a transposition table is used only during the current search in the conventional game-tree search. This paper proposes a method that uses alternatively two different transposition tables. One is for a game-tree search in the present position, while another one is for the search in the position where the player is to move next. This idea was implemented on computer shogi TACOS to evaluate. The results of the experiments performed show that the proposed method improves the search efficiency as well as the playing strength.

7 pgs (2006) Game Informatics GI-15, Information Processing Society of Japan, March 7, Tokyo

More...

No. 210 Defense against One-Ply-Mate Threat in Shogi and Its Implication to Endgame

By M. Sano, T. Hashimoto and H. Iida.

It is important to perform good defense against threatmate, but it is not always easy to find such a move. To prevent from the threatmate, the conventional idea is to generate potentially defensive moves while focusing on the squares around the King. However, this idea does not always enable a computer to find a successful defense. In this study we focus on one-ply mate and its defense, and propose a practical idea to generate such defense moves at the leaf nodes during game-tree search in the endgame of shogi. Some experiments performed show the remarkable effectiveness of the proposed idea.

6 pgs (2005) GPW2005, 10th Game Programming Workshop, November 18-20, Hakone

More...

No. 209 Three Approaches to Game-Theoretical Value Prediction

By H. Kita, A. Cincotti and H. Iida.

One of the most important characteristics of games can be represented by the game-theoretical values. Every n-person zero-sum game with perfect information has a unique theoretical value. However, it is a time-consuming task to determine the game-theoretical value, and usually it is impossible to establish it in complex games. This paper presents our new attempt to predict the game-theoretical value with three approaches while having focus on the diminishing return, the change of game outcome and the change of score points in the framework of computer self-plays.

6 pgs (2005) GPW2005, 10th Game Programming Workshop, November 18-20, Hakone

More...

No. 208 Pruning Wrong Direction Moves

By K. Matsubara, T. Hashimoto and H. Iida.

It is important to distinguish and eliminate the implausible moves for efficient game-tree search. In complex games such as shogi, there are relatively many implausible moves. We call such moves ''wrong direction moves''.   This paper explores an idea to distinguish such implausible moves and then proposes two methods: static soppo cut (SS-cut) and dynamic soppo cut (DS-cut). The two ideas were incorporated in shogi program TACOS. Experiments performed show the effectiveness of the proposed ideas. SS-cut and DS-cut enables TACOS to become one of the final standings at 14th and 15th World Computer Shogi Championships.

4 pgs (2005) GPW2005, 10th Game Programming Workshop, November 18-20, Hakone

More...

No. 207 Effective Use of Expensive Evaluation Function and Design of Directional Asymmetric Orientation Evaluation Function for Shogi

By T. Hamada, T. Hashimoto and H. Iida.

Search and position evaluation are the cores for developing a computer shogi.   Expensive evaluation function that considers the influence of the major piece attack cannot easily be called. This paper verifies an appropriate range on a method to improve search efficiency not by calling such an expensive position evaluation in case where there are some large margins with alpha or beta value. Moreover, it proposes a new design of expensive but high-quality position evaluation based on Directional Asymmetric Orientation. The implementation task is not so difficult if all directions are equally evaluated. Nevertheless, it is inadequate in many cases. Examining only the important directions enables the position evaluation more accurate. We then implement ''short range pieces in the opponent zone '' and ''major piece mobility'' as evaluation factor based on Directional Asymmetric Orientation.

4 pgs (2005) GPW2005, 10th Game Programming Workshop, November 18-20, Hakone

More...

No. 206 Towards Periodic Table of Game Elements

By T. Yamamoto and H. Iida.

The periodic table of the elements condenses the foundations in chemistry.  Likewise the rules of a game may condense the essence of the game. The degree of freedom for players exists in all games and tends to reflect the characters derived from the rules. In this study we try to make a periodic table of the game elements in order that we may observe every type of games on the same field. The table basically covers all games for which we can measure the degree of freedom or the average number of possible moves. 

4 pgs (2005) GPW2005, 10th Game Programming Workshop, November 18-20, Hakone

More...

No. 205 Game-Refinement Theory and Poker

By Y.Uruma and H. Iida.

Poker is one of the gambling games with cards, and it is popular all over the world, especially in USA. In recent years, poker is played not only in the casinos also in game sites on the Internet. This paper summarizes the major rules of poker and defines the number pf possible options for players and the game length. We developed a computer program to simulate poker games and analyzed the game statistics such as the average possible options and game length. Based on the statistics, we compare the typical two variants of poker from the viewpoint of game-refinement theory, and show some notable differences between them.

4 pgs (2005) GPW2005, 10th Game Programming Workshop, November 18-20, Hakone

More...

No. 204 Theoretical Value Prediction in Game-Playing

By H.Kita, A.Cincotti and H. Iida.

One of the most important characteristics of a game is represented by its game-theoretical value. However, to find out the value is time expensive and it is almost impossible to establish in complex games. Therefore, we propose three different methods to predict the outcome of the game under ideal play. Such methods use information concerning diminishing return, winning rate change, and score difference obtained by self-play experiments. We apply these methods to some games and discuss the validity of each single method.

8 pgs (2005) International Workshop on Game Informatics, ACG-11, September 5, Taipei

More...

No. 203 Improvement of Shogi Program in the Opening and Middle Game

By T.Murata, J.Nagashima, T.Hashimoto, and H. Iida.

Computer shogi is strong in the endgame while there are still many weak points both in the opening and middle game. In this study we analyze the usual search structure minutely. With focus on the relation between the move generation category and the beta-cut in the frame work of the realization- probability search, we found several critical errors that have never been addressed. This paper shows our idea to improve the move generator while proposing a new move generation algorithm. With these improvements, the program has considerably strengthened.

8 pgs (2005) International Workshop on Game Informatics, ACG-11, September 5, Taipei

More...

No. 202 The Rebirth of Solved Games

By T. Nakamura, A. Cincotti and H. Iida.

There has been a tremendous advancement witnessed in the computer technology industry in recent years. With such progress, many of the traditional two-person complete information games have been solved. The game of tictactoe is one of such games and it is well known that when both players select their best moves, the game always ends in a draw. In the game of hex, Black has always a winning strategy and for small board's size it has been completely solved. In this paper we have explored the possibility of reviving a strongly solved game, such as tictactoe and hex by adding some stochastic elements to it. In our attempt we have altered the rule and allowed both players to make their moves in synchronized manners.

4 pgs (2005) JCIS2005, 8th Joint Conference on Information Sciences, July 21-26, Salt Lake City

More...

No. 201 A Master-like Opening Strategy in Computer Shogi

By J.Nagashima, T.Hashimoto and H. Iida.

Even masters are unable to play every opening line effortlessly which may be stored in the opening book. Each master has his preferred opening lines and attempts to lure his opponent to play into his hands. The same can be said about computer programs. In this paper, we demonstrate a method that tunes an opening book through self-playing games for the purpose mentioned above. We illustrate an application of the proposed method in the domain of computer shogi.

4 pgs (2005) JCIS2005, 8th Joint Conference on Information Sciences, July 21-26, Salt Lake City

More...

Research Unit for Computers and Games
Japan Advanced Institute for Science and Technology

Asahidai, Nomi 923-1292
Fax: +81.761.51.1293/1149