Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/
Title 落下型パズルゲームの定石形配置法とぷよぷよへの適
用
Author(s) 富沢, 大介
Citation
Issue Date 2014‑03
Type Thesis or Dissertation Text version author
URL http://hdl.handle.net/10119/12030 Rights
Description Supervisor:池田 心, 情報科学研究科, 修士
Stylized Assignment in Tile-Matching Puzzle Game and its Application to Puyo-Puyo
Daisuke Tomizawa (1010043) School of Information Science,
Japan Advanced Institute of Science and Technology February 12, 2014
Keywords: tile matching puzzle game, game tree search, representation of standard patterns, Puyo-Puyo.
In the area of Artificial Intelligence, the intelligence and thoughts of humans have been mimicked and applied in many ways. In particular, in the field of board games and puzzle games, the computer player needs, from a given board state, to find the action that will best improve his current state in relation to the final goal of the game, and a lot of research has been done to develop efficient evaluation functions and search algorithms.
There are many possible shapes and sizes of boards, depending on the game, and also many kinds of actions, like moving, adding, removing or exchanging, but in any game, some desirable patterns and sequence of moves can be found, and are often used by the players.
A representative example is the sequence of moves called joseki in the games of Go and Shogi. These sequences have been refined over the years and since they are considered as the optimal sequences for both players, they are often used by amateur and professional players as well.
Such desirable sequence of moves are also used by the computer pro- grams, with the technics of data mining, optimization or pattern matching.
These technics are now well established for example in the opening stage of the games of Go and Shogi, or the opening and ending stages of the game of Chess.
Copyright c⃝2014 by Daisuke Tomizawa
1
In this thesis, we will focus on such desirable patterns in tile-matching games. Some famous and representative tile-matching games are ”Tetris”
and ”Puyo-Puyo”.
In tile-matching games, each player usually control one board (a field), where pieces (called by different names like pieces, puyo, etc) fall regularly.
The player can mainly change the position and orientation of the falling piece, in order to place it in a particular configuration related to the other already fallen pieces, making all the pieces of the particular configuration disappear.
Like in complete and certain information games like Go and Shogi, there are desirable board states that play a key role in the design of strong algorithms, but tile-matching games differ greatly from Go and Shogi on some points. First, the influence of one player on the board of the other one is limited, and secondly, there is usually a chance element (color, shape) in the pieces given to the control of the players.
Because of the randomness of the given pieces, the player cannot al- ways achieve the pattern that he was aiming for, and he needs to adapt constantly to the current state of the board and choose to construct new patterns. For this reason, it is difficult to apply to tile-matching games the algorithms used in complete and certain information games like Go and Shogi, and we need to design specific state-evaluation functions that will help the program to obtain boards with a high evaluated value.
In games where pieces of different colors are available (for example Puyo- Puyo), it would be inefficient to list directly all the possible desirable pat- terns, because the combination of colors lead to a large number of patterns.
In our research, we focus on the relation between two possible cells, more particularly whether or not they must contain a similar kind of piece. Based on this, we describe the desirable board patterns with a weighted adjacency matrix (that we call an association matrix) that expresses whether each couple of cells should contain similar pieces, different pieces, or indifferently any pieces.
The method proposed in this research allows us to describe efficiently only the important relationships in couples of cells, which is a concept that occurs frequently in most tile-matching games.
Moreover, we have applied and implemented this method to the repre-
2
sentative tile-maching game of Puyo-Puyo. We also propose a method with an automatic order to create efficiently the data of the desirable patterns, and we show how we implement it concretely.
We also perform two experiments to check the effectiveness of the pro- posed method.
In the first experiment, we compare in how many steps the proposed method is able to complete the target pattern compared to experienced human players.
In this experiment, the proposed method obtains comparable results to humans when the target patterns are patterns often used by human players in real competitions. Also, it obtains much better results than humans when the target patterns are patterns usually not used in real matches between humans.
In Puyo-Puyo, creating ”chains” of patterns as long as possible is an important element to win the game. So, in the second experiment, we combine the proposed method with an existing search algorithm for the game of Puyo-Puyo and investigate the length of the chains that the pro- gram can create in real games.
The combination is done by first using the proposed method to start the patterns, and then switching to the existing search algorithm. We show that this combination of the proposed method with the existing search algorithms performs much better (i.e. creates longer chains of patterns) than the existing search algorithms used alone.
3
