Databases
StackOverflow2013
Postsdbo
POSWI-Prolog depth-first search?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSWI-Prolog depth-first search?
    primarykey
    data
    text
    <p>My aim is to develop a simple program to run a game called 'Kayles' which is similar to Skittles. You have a row of bottles, 2 players knock them down in turns, and the player to knock the last bottle(s) down wins. You can knock 1 or 2 bottles down only, and they have to be next to each other.</p> <p>The first part of this program was to decide how to represent a bottle, and an empty space. I have decided to use a list, where 1 represents a bottle and 0 represents an empty space.</p> <p>The second part of this program was to print the current state to the terminal where a bottle is represented by an asterisk * and an empty space is represented by a gap.</p> <p>The third part of this program was to list and print all the possible next states reachable from a current state. For example, if you have 3 bottles [1,1,1], one possible next state is [0,1,1] as the first bottle was knocked down. So this predicate is supposed to print a list of all possible next states, again represented by * and space.</p> <p>I have successfully done the above, and this is my code so far:</p> <pre><code>printstate([]) :- nl. printstate([B|L]) :- (B=0 -&gt; write(' '); write('*')), printstate(L). next([1|S], [0|S]). next([1,1|S], [0,0|S]). next([0|S], [0|T]) :- next(S,T). next([1|S], [1|T]) :- next(S,T). printnextstates(S,T) :- next(S,T), printstate(T), fail. </code></pre> <p>The next bit is the bit I am stuck on! So the aim is to define the value of a state to be 1 if the first player to move can force a win, and 0 otherwise. I am to write a predicate value(S,X) which will compute the value X of any game state S by a depth-first search through the game tree. I should use assert if possible to avoid the search exploring any position more than once. </p> <p>I have no idea how to do this! </p> <p>So far this is what I can come up with: </p> <pre><code>value(S,X) :- S = 1, ([S,T] = 1); 0. </code></pre> <p>But I'm sure it's not that simple, yet I have no idea how to begin this question! I've researched depth-first search but I don't really understand it enough to write this... does anyone have any idea how one may go about in starting this question?</p> <p>Any help is much appreciated!</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USfalse
    1. USuser2127447
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSWI-Prolog depth-first search?
      1. USksoo
      1. VTFavorite
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload