It is slightly surprising because the fitness is somewhat chaotic (a small change in the numbers on the board can give rise to a large change in the fitness). Two fit "parents" (boards of numbers), when combined, can often result in a very fit child. We thus define the number of pegs removed from the playing board as the fitness of the board of numbers. The less pegs in the end of that game, the better the board of numbers is for our purposes. Equality between actions is broken by an arbitrary (but constant) rule.Ī board of numbers can thus be mapped to a unique game played according to it. Suppose each position has a number, and then we place the peg and play by the following rule: always choose an action that maximizes the sum of numbers on the board, where the sum is taken over positions filled with pegs. The concept of assigning numbers to positions on the board (like in the first few heuristics) was appealing, and we decided to try a different approach where the numbers can have a more distinct meaning. Since in either case it returns a lower bound, it is also admissible (in fact the only admissible heuristic except the zero heuristic). If they are, the state is not solvable and it returns infinity. 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)
