The performance varied across different board sizes and shapes. Observe that this rules out BFS, UCS and iterative deepening: we know all goals are in the deepest level, so those algorithms would be extremely inefficient. The goals are exactly the vertices with distance 31 from the root.
Consider the following:Ĭombining these, we see that a solution must contain exactly 31 actions and any path of length 31 is a solution. Indeed, we will see that searching works well and solves the game in a very reasonable time.īefore we describe each search algorithm used, we make an important observation about the game's search graph. The game is very suitable for searching: we have a well defined initial state, goal and transitions. We compare several search methods, and show their performance on the original problem and on some variations (different board size/shape). In our project, we have studied this problem and implemented several AI algorithms from class to solve it. The goal of the game is to play until only one peg is left. The peg which was jumped over is removed from the board. A peg can only move into a vacant position, which is two positions away from it (horizontally or vertically, but not both), while jumping over another peg. On each turn, the player takes a peg and moves it.
It is a simple one player board game, and a very interesting challenge in terms of AI. We chose to solve the game Peg Solitaire, and some generalizations of it.
0 kommentar(er)
