Computer Science Canada

Recursion Checkers AI
Author:  richcash [ Fri Jun 23, 2006 2:09 pm ]
Post subject:  Recursion Checkers AI
Well, I've given up and am asking for help. This is what I want to know.

My plan was to make a checkers game against the cpu with AI. I planned to do it like this :

    -use recursion to check all of the possible combinations of moves in the next four turns by both the computer and user (then I'll store the net pieces gained or lost after each turn in an array) so it's kind of like a tree.

    -after I have all of these values, I will have the computer look for a move (or part of the array) where when that move is made the user can make a move and no matter what happens after that there will be a net loss. Then the computer would not make this original move. So, I'm not predicting what move the user will make, I'm checking if ANY of the moves the user can possibly make will trap me into getting a net loss no matter what happens for the rest of that branch of the game tree (array).

    -obviously (opposite of above), if the computer sees a move where no matter what happens after that there will be a net gain, it will go for that move.


However, I don't really know how to do the first part. I know recursion for fibonacci sequence and factorials, but I just can't seem to put it all together for this. I know the logic of where a piece can move for the user (here assuming that my boxes on the board are 50 x 50) so you don't have to explain the rules of piece movement thoroughly
Normal piece on bottom side of board
code:
var move : boolean := abs (clickedx div 50 - selectedx div 50) = 1 and clickedy - selectedy = 1

Could someone tell me how exactly to use recursion to check every possible combination for moves of checkers pieces?

Also, if you see any problems with my logic for cutting out parts of the tree (or array) and selecting the best move please tell me. I'm not trying to make an unbeatable checkers I want to make an AI that looks four moves ahead.

Thanks for any help you can give.
Author:  Cervantes [ Fri Jun 23, 2006 3:55 pm ]
Post subject: 
Here's a very basic outline that you might want to give some thought to. You'll have to do a bunch of coding still to fill this in, because I've encapsulated things like "for each possible move".

code:

proc check (step : int, net : int, board : array 1 .. *, 1 .. * of char)
    if step <= 0 then
        return
    end if
    var net_change := 0
    if you captured n pieces
        net_change += n
    end if
    if you lost n pieces
        net_change -= n
    end if
    % (You'll have to code something here using _step_ and
    % the current turn to determine whether to check your pieces
    % or your enemies pieces
    for each piece
        for each possible move
            % create a new board array and
            % copy the data from _board_ (the parameter)
            % into it, then update it with this move
            check (step - 1, net + net_change, new_board)
        end for
    end for
end check

Untested, of course.
Author:  richcash [ Fri Jun 23, 2006 9:22 pm ]
Post subject: 
Thanks as always for the help Cervantes!
Now, if anyone can give me some specific code to check every possible move for n number of turns that can be made (using recursion) it would be appreciated. You wouldn't have to explain your code that much, since I understand recursion for factorials and easy stuff. Any help or attempt is appreciated!
Author:  MysticVegeta [ Sat Jun 24, 2006 12:43 pm ]
Post subject: 
you know if you dont want to use advanced recursion. you dont HAVE to use it. Checkers is pretty basic, there are really less # of moves. Here is a basic idea:

code:

for x : 1..n
   for y :1..n
         if grid(x,y) = compPiece then
                virtuallyMoveThisPiece (x, y, 1)
end.................

proc virtuallyMoveThisPiece (int x, int y, int depth)
    var n : record
          prevX: int, prevY : int, newX : int, newY : int

    if (depth >= desiredDepth*2) then return;

     for i : # of positions this piece can go in next move
            makeMoveAndPlaceItOntoAVirtualBoard (x,y,n(i))

            for j : 1..row
                 for k : 1..col
                      if (virtualBoardPiece (x, y)) = pieceOfPlayer then
                              virtuallyMoveThisPiece (j, k, depth+1)
                              calculateProfitAndStoreItIntoAVariable
                      end if
                 end for
            end for

           resetVirtualBoardToOriginalCurrentPosition

     end for
end virtuallyMoveThisPiece



yeah I know everything is sort of screwed but I will try to explain the best i can. You see the var n is a special type which stores the legal moves for a piece. We loop through those legal moves, say our loop is at one. So we make the first legal move, then we do the same thing again and again by a recursion. What I mean is imagine this:

. . O . .
. X . . .
. . . . .
. . . . .

You see the "O" has 2 places to go correct?

So the length of n is 2. 1st move is we go to the right.
While the second is we jump over X

Say we go diagonally down-right. makeMoveAndPlaceItOntoAVirtualBoard (x,y,n(i)) is called.

Now on our virtual board the "O" is not at row 1 col 3. its at row 2 col 4.

Then at the same iternation we have a pair of nested loops, correct? Now that loop detects "X" and then virtualBoardPiece (x, y)) = pieceOfPlayer is true because "X" is player's character while "O" is computer's. Our depth increases by 1 now and virtuallyMoveThisPiece (j, k, depth+1) is called. This does the same thing that we did for "O" before, and many many many nodes are created until the condition depth >= desiredDepth*2 is reached. Note: its desiredDepth * 2 because both sides move, so when I say we played 3 moves. that means I moved 3 and you moved 3.

I know, its all confusing and stuff but I need practice with recursion too so I try to code most of them as possible. Please any for any questions because this code is UNTESTED!

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy