Answers.Body: <p>Your approach seems reasonable to me. The edges do not necessarily have to be numbers, but, if you wish, you could also encode the actions as numbers. For example, the weight of an edge could represent the "cost" of the corresponding action. If there's no natural cost associated with an action, then you can add a unit cost for each action.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-05-18T14:46:56.563Z
Answers.LastActivityDate: 2019-05-18T15:59:15.077Z
Answers.LastEditDate: 2019-05-18T15:59:15.077Z
Answers.UserDisplayName: nbro
Body: <h3>Problem</h3>
  <p>I've been reading research papers on how to solve a peg solitaire using graph search, but all the papers kind of assume you know how to do the reduction(polynomial time conversion) from the peg solitaire to the graph, which I do not, but this is how I assumed it was done.</p>
  <p>For those of you unfamiliar, <a href="https://www.youtube.com/watch?v=Bt6GpGvUNeQ" rel="nofollow noreferrer">here</a> is a video that illustrates how to play this game, and here's an image of a board.</p>
  <p><a href="https://i.sstatic.net/c9rQB.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/c9rQB.jpg" alt="Peg Solitaire" /></a></p>
  <p>The goal is to only have one peg on the board and you get rid of pegs by jump one peg over another. A peg can only jump if the it's jumping into an empty space as shown in the picture above.</p>
  <h3>What I've tried</h3>
  <p>I had the idea of converting the problem to a tree where each node represents the state after an action is taken and each edge represents the action taken. So the root node would the initial state which is the board shown above then it's children would be the state of the board after any of the possible legal actions that can be taken.</p>
  <p>So, for example:</p>
  <p><a href="https://i.sstatic.net/YJ4BR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YJ4BR.png" alt="enter image description here" /></a></p>
  <p>Then the children of each of those nodes would be the possible moves for them and you can find a solution once you've reached depth 31 in the tree because there are 32 pegs and you win the game where there's only 1 left.</p>
  <p>Is this the right approach? It feels a little too abstract because I'd have to represent the edges as peg moves, but that's weird cause they're usually numbers or constraint.</p>
  
Tags: <game-ai><search><graphs>
Title: How to solve peg solitaire with a graph search?
UserDisplayName: Gooby
ThreadText: # How to solve peg solitaire with a graph search?
  
  (Asked by: username_0 on 2019-05-18)
  
  ### Problem
  
  I've been reading research papers on how to solve a peg solitaire using graph search, but all the papers kind of assume you know how to do the reduction(polynomial time conversion) from the peg solitaire to the graph, which I do not, but this is how I assumed it was done.
  
  For those of you unfamiliar, [here](https://www.youtube.com/watch?v=Bt6GpGvUNeQ) is a video that illustrates how to play this game, and here's an image of a board.
  
  [![Peg Solitaire](https://i.sstatic.net/c9rQB.jpg)](https://i.sstatic.net/c9rQB.jpg)
  
  The goal is to only have one peg on the board and you get rid of pegs by jump one peg over another. A peg can only jump if the it's jumping into an empty space as shown in the picture above.
  
  ### What I've tried
  
  I had the idea of converting the problem to a tree where each node represents the state after an action is taken and each edge represents the action taken. So the root node would the initial state which is the board shown above then it's children would be the state of the board after any of the possible legal actions that can be taken.
  
  So, for example:
  
  [![enter image description here](https://i.sstatic.net/YJ4BR.png)](https://i.sstatic.net/YJ4BR.png)
  
  Then the children of each of those nodes would be the possible moves for them and you can find a solution once you've reached depth 31 in the tree because there are 32 pegs and you win the game where there's only 1 left.
  
  Is this the right approach? It feels a little too abstract because I'd have to represent the edges as peg moves, but that's weird cause they're usually numbers or constraint.
  
  **Tags:** game-ai, search, graphs
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-05-18. Score: 2
  
  Your approach seems reasonable to me. The edges do not necessarily have to be numbers, but, if you wish, you could also encode the actions as numbers. For example, the weight of an edge could represent the "cost" of the corresponding action. If there's no natural cost associated with an action, then you can add a unit cost for each action.
  
  
  ---
  
  