CODEWITHSUNDEEP
pythonrecursionnested-loopschess
foxwire
foxwire

Reputation: 23

Checkers algorithm: how to reduce nested for loops

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.

Upvotes: 2

Views: 366

Answers (2)

niemmi
niemmi

Reputation: 17263

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.

Upvotes: 1

Frank Bryce
Frank Bryce

Reputation: 8446

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 :)

Upvotes: 1

Related Questions