CODEWITHSUNDEEP
recursionprologalpha-beta-pruning
Sven182
Sven182

Reputation: 39

How to use dynamic lists in a recursive function in Prolog

I have a dynamic list storing a field coordinate and owner of that field

:-dynamic
    board/2.

One entry of this list looks like that:

board(e4,[w]).

There are 22 more board positions all looking similar.

I am trying to implement an AI for the game the board is for. I am using the alpha beta algorithm and therefore have to create new 'boards' to evalate the situation.

I have a copy of the original board to work with but now have a function adjusting the board for the current move like this:

move(position,boardOld,boardNew)

This is called recursive therefore in second call boardOld equals boardNew and boardNew is the oldBoard with the next move in the analysis.

My idea was to copy the old Board in every iteration, but i have no idea how to do this as this

copy_predicate_clauses(boardOld(A,B),boardNew(A,B)).

would add the old Board to the newBoard because the list already exists.

I am using the following algorithm (can't copy it, as it is an image):

http://www.cuceinetwork.net/archivos/prolog/The_Art_of_Prolog.pdf

PDF page 445 (Book page 407).

The algorithm gets Position as 'Board' while initializing, i don't know how to do this with my list and furthermore the clause move(Move,Position,Position1) return the new Board with the current move. This is called recursive and i have no idea how to create the board for position1 without overwriting the ones from before.

Edit//

ok, i get the problem. But i already used this predicate a lot in my game and don't want to change it all. I did this:

findall((X,Y),board(X,Y),CurrentBoard).

CurrentBoard gives me a list like this

[(e4,[w,w]),(g4,[s,w]),(b7,[r,w,s])]

Now i can't use my methods to determine the possible moves.

I have facts like

move(e4,d5).
move(d5,e6).

stating which move(from,to) is possible and now i tried this

findall((X,Y),listMoves(CurrentBoard,X,Y),possibleMoves).

with something like this. I am struggeling at this point. How do i generate a list with possible moves. I somehow have to get the X coordinate from currentBoard, check if the Head of the list from that coordinate (pawns on that coordinate) belongs to me and check if the Y coordinate (to) is free. 

listMoves([Coordinate|[Head|Tail]], X, Y) :-
     move(X,Y),
     ownField(X,Coordinate,Head),

Upvotes: 2

Views: 1207

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

If you read from (printed) page 401, the authors outline the basic gameplay algorithm as:

   play(Game) :-
         initialize(Game, Position, Player),
         display_game(Position, Player),
         play(Position, Player, Result).

The rest of the section uses the term "position" in a way that makes me believe they are referring to the entire state of the game. For a game like chess, this would be the state of the board itself: what pieces are where.

From there, the authors go on to discuss move/2 and move/3, which are defined thusly:

It is convenient to separate the choice of the move by choose_move/3 from its execution by move/3

And then later on page 403,

The predicate move(Position, Move) is true if Move is a possible move from the current position.

Taken together, this all suggests to me that they expect a Position to be the complete chess board (I think you're playing chess, are you?) and Move to be a legitimate move, for the purposes of defining move/2, and then move/3 is just move/2, returning the resultant board. In other words, the initial chessboard might look something like this:

starting_board([[b-r, b-b, b-n, b-q, b-k, b-n, b-b, b-r],
                [b-p, b-p, b-p, b-p, b-p, b-p, b-p, b-p],
                [nil, nil, nil, nil, nil, nil, nil, nil],
                [nil, nil, nil, nil, nil, nil, nil, nil],
                [nil, nil, nil, nil, nil, nil, nil, nil],
                [nil, nil, nil, nil, nil, nil, nil, nil],
                [w-p, w-p, w-p, w-p, w-p, w-p, w-p, w-p],
                [w-r, w-b, w-n, w-q, w-k, w-n, w-b, w-r]]).

This is how I might set it up; doubtless there are probably more efficient or wiser ways of doing it, but the point is, your Position values should always encompass the whole state of the board like this. In fact, it may need to include other information, like whose turn it is, or if you wanted to keep a log of each move, you could throw that in there as well.

From here, you're prepared to write move/2 and move/3. I would be inclined (for didactic purposes) to just write move/3 and use that to build move/2 but for efficiency you probably want to do them separately. I'm bad enough at chess that I'm going to stop here (that and I am not convinced you're doing chess anyway). But basically, what you want is to see that move(StartPosition, Move, NewPosition), given a start position, will unify Move with some sort of short description of the move and NewPosition with the whole board state after having made that move, so you get a before-and-after snapshot.

Once you have these parts built I think you can mostly use the book code as-is.

I think you basically had a few misunderstandings:

  1. The board is not a predicate with multiple solutions. It's a data structure you create that represents the whole story of what's going on.
  2. Dynamic predicates do not form a list. It's true that you can have multiple solutions and that they have an order, it is not a convenient data structure for the kinds of manipulations you're going to need to do.
  3. I really don't think you want to mix those two ideas together and see what falls out.

Upvotes: 1

Related Questions