Checkers algorithm: how to reduce nested for loops

Question

I’m trying to build a program that plays draughts/checkers. At the moment I’m trying to make the function, that allows the computer to make and evaluate moves. My idea is to have the computer look at all it’s own possible moves and for each of these moves, look at the possible opponents moves and then for each of these moves, again look at it’s own possible moves.

With each ply it will evaluate if the move is good or bad for the player and assign points, at the end it picks the moves with the highest points.

So far I have managed to get a version of this working, but involves a lot of nested for loops. The code is a mess and not very readable at the moment, but this is a simple model of the same concept. Instead of evaluating and producing more lists, it just multiplies by two for the new list.

counter = 0
    for x in list:
        counter += 1
        list_2 = [x * 2 for x in list]
        print 'list_2', list_2, counter
        for x in list_2:
            counter += 1
            list_3 = [x * 2 for x in list_2]
            print 'list_3',list_3, counter
            for x in list_3:
                counter += 1
                list_4 = [x * 2 for x in list_3]
                print 'list_4', list_4, counter

If I run this code, I get what I want, except that I can't easily control the depth of the search without copying in more for loops. I thought recursion might be a way of doing this, but I can’t figure out how to stop the recursion after x levels of search depth.

Is there a better way of getting the same output form the code above, while getting rid of all the for loops? If I can get that to work, I think I can do the rest myself.

You could possibly look into using a stack instead of recursion if that would be simpler. Also using an [Alpha-Beta](http://gamedev.stackexchange.com/a/30033) game tree search and understanding it would likely help greatly with creating your algorithm. — Alyssa Haroldsen, May 04 '16 at 16:56
If you need to recurse an arbitrary number of times, make that number an argument to your recursive function. If it's 0, that's your base case. — , May 04 '16 at 16:57
You can do this with recursion. Take a look at this [answer](http://stackoverflow.com/a/36645766/4014959) to see how to limit recursion depth. But you also need to limit recursion breadth, or the number of boards to evaluate soon becomes vast; that's where alpha-beta pruning is useful. — PM 2Ring, May 04 '16 at 17:11

Frank Bryce · Answer 1 · 2016-05-04T17:15:09.303

I thought recursion might be a way of doing this, but I can’t figure out how to stop the recursion after x levels of search depth.

Your intuition is correct, and a simple a way of doing this would be to have an incrementing number passed to each level. When the recursion gets the maximum value then the recursion is completed. A trivial example is below to demonstrate.

def countup(i=0):
  print(i)
  if i==MAX_COUNT: return
  countup(i+1)

For your algorithm, you need a value to represent the board evaluation. For instance in the range [-1,1]. Player A could be said to be winning if the evaluation is -1 and Player B is winning if the evaluation is 1 for example. A recursive algorithm could be as follows.

def evaulate(board, player, depth=0):
  if depth==MAX_DEPTH: return hueristicEvaluation(board)
  bestMove = None
  if player==PLAYER_A:
    val=999 # some large value
    for move in get_moves():
      newboard = board.makeMove(move)
      eval, _ = evaluate(newboard, PLAYER_B, depth+1)
      if eval < val:
        bestMove = move
        val = eval
  elif player==PLAYER_B:
    val=-999 # some large negative value
    for move in get_moves():
      newboard = board.makeMove(move)
      eval, _ = evaluate(newboard, PLAYER_A, depth+1)
      if eval > val:
        bestMove = move
        val = eval
  return val, bestMove

This is abstract, but the idea is there. Adjust depending on how your are representing the board or the players. The function hueristicEvaluation could be something as simple as counting the pieces on the board for each player and how close they are to the other side. Remember that this function needs to return a number between [-1,1]

Edge cases to consider, which I didn't take into account:

If all moves are winning and/or losing
If the are NO moves in the position, for example if your pieces are all blocked by your opponent's pieces

Many improvements exist to a simple search like this. Read if you're interested :)

For checkers, perhaps Memoization would speed things up a lot. I'm not sure, but I'd think it would be especially in the beginning. See python's way of doing this.
Pruning
Alpha-beta pruning
Branch and bound

Thanks a lot for your answer. At the moment, I'm just trying to get the simplest version of my program running. Once I do that, I'll start looking more in depth at some of the ideas you suggested. Thanks for the links though. : ) — foxwire, May 05 '16 at 08:38

score 1 · Accepted Answer · answered May 04 '16 at 17:16

Here's an equivalent function that uses recursion. It controls the recursion with two parameters which track the current depth and maximum depth. If current depth exceeds the maximum depth it will return immediately thus stopping the recursion:

def evaluate(l, max_depth, cur_depth=0, counter=0):
    if cur_depth > max_depth:
        return counter

    for x in l:
        counter += 1
        l2 = [x * 2 for x in l]
        print cur_depth, l2, counter
        counter = evaluate(l2, max_depth, cur_depth + 1, counter)

    return counter

If called with max_depth=2 it will produce the same output except that instead of variable name the current depth is printed.

Thanks very much, I've not had a chance to implement this in my program yet, but this looks like exactly what I needed. : ) — foxwire, May 05 '16 at 08:34

Checkers algorithm: how to reduce nested for loops

2 Answers2