Recursion Checkers AI

[richcash]

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.

[Cervantes]

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.

[richcash]

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!

[MysticVegeta]

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!