If they are not far away, the heuristic simply gives the number of pegs minus one (this is always a lower bound, and if the state is solvable it is also tight). The idea is to prefer states in which no two concentrated groups of pegs are so far away from each other that they will never meet. This again is similar to the previous one, but the distances of some of the positions close to the center were altered a bit to perform better (in the original board). If H,V are the horizontal and vertical distances from the center respectively, then the heuristic's value is 2 max(H,V). This is similar, but with a larger bias towards the center. This heuristic's value of a board is the sum, for each peg on the board, of the Manhattan distance from the center. This is UCS (in our case equivalent to BFS), which as mentioned is very poor for this particular game. All of them have to do with trying to concentrate the pegs on the center (when we played it ourselves it became evident that leaving pegs isolated in one of the edges was a bad strategy, and one should always try and concentrate them on the center). There is a variety of methods to estimate how "promising" a given board is. The A* algorithm turned out to be very good with a sufficiently fine tuned heuristic. On some boards DFS happened to find a solution relatively quickly (for example in the original board) and on others very slowly. 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)
