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
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
Home Page
Find latest posts
View Blog Entries
Likes Received (0)