抄録
Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1900000, indirect: 570000)
In this research, we deal with a falling block puzzle game PuyoPuyo, which has online property, as a single-player game and consider the conditions so that the player can win, that is, the player can keep playing the game forever on the gameboard of a constant height.
We have considered both the cases that the lookahead of inputs exists as in the real game and it does not exist. In both cases, we have shown sufficient conditions that the player wins and that the player loses using the number of game pieces, the width of the gameboard and the number of lookaheads as parameters. Also we have shown that the ideas of the proofs can be applied to the other similar games.
Also, we have shown algorithms and complexity of the problems to decide if the matchstick puzzles on the grid has a solution and the problem to decide the winner of a tow-player game QUIXO.