zoranh

In many games programming goal is to create smart engine which can beat a human. If human can beat the game without much thinking, then game is not playable and people will not like it. This article explains one method of dealing with turn-based discrete games, like chess or dominoes, where computer engine has to perform a search through a large state space.

Imagine a turn-based game with two or more players make a move each, and game ends when certain conditions are met. Examples are ...

Attached Files

• NPuzzle..zip‎ (347.9 KB, 252x views)
• npuzzle_msi..zip‎ (76.7 KB, 142x views)

n-Puzzle is a matrix of tiles with one tile missing, as given in the following picture:

Most notorious n-puzzles are 8-puzzle (3x3 tiles) and 15-puzzle (4x4 tiles).

Solving the n-puzzle is a typical informed search problem. It is search problem because program solving the puzzle must search through valid states of the puzzle in order to find a sequence of moves that transform a puzzle from any valid starting position into the solved state. It ...