Programming Mini-Challenge: KnightBot

I like this! Here is a C solution. It might look like magic at first, but stick around and I'll explain it.

typedef uint64_t board;

board square_to_board(long square) {
    return ((board) 1) << square;
}

/*
   8 | . . . . . . . .
   7 | . . . . . . . .
   6 | . . . . . . . .
   5 | . 3 . 2 . . . .
   4 | 4 . . . 1 . . .
   3 | . . * . . . . .
   2 | 5 . . . 8 . . .
   1 | . 6 . 7 . . . .
     +----------------
       a b c d e f g h
*/

board step(board b) {
    board e4 = (0x3F3F3F3F3F3F3F00 & b) >> 6;
    board d5 = (0x7F7F7F7F7F7F0000 & b) >> 15;
    board b5 = (0xFEFEFEFEFEFE0000 & b) >> 17;
    board a4 = (0xFCFCFCFCFCFCFC00 & b) >> 10;

    board a2 = (0x00FCFCFCFCFCFCFC & b) << 6;
    board b1 = (0x0000FEFEFEFEFEFE & b) << 15;
    board d1 = (0x00007F7F7F7F7F7F & b) << 17;
    board e2 = (0x003F3F3F3F3F3F3F & b) << 10;

    return b | e4 | d5 | b5 | a4 | a2 | b1 | d1 | e2;
}

int main(int argc, char *argv[]) {
    if (argc < 4) return 1;

    long start = strtol(argv[1], 0, 10);
    long end = strtol(argv[2], 0, 10);
    long moves = strtol(argv[3], 0, 10);

    board b = square_to_board(start);
    for (; moves>0; moves--)
        b = step(b);

    if (b & square_to_board(end))
        puts("True");
    else
        puts("False");

    return 0;
}

Try it online!

The idea here is something called bitboards, which are a very common way of expressing chess positions in computers. If a chess board is 8×8 squares, then there are 64 squares total where a piece could be placed. Hmm, what else is 64 things long?

typedef uint64_t board;

We'll assign each bit to a square as follows:

  +-----------------+
8 | 0 1 2 3 4 5 6 7 |
7 | 8 9 . . . . . . |
6 | . . . . . . . . |
5 | . . . . . . . . |
4 | . . . . . . . . |
3 | . . . . . . . . |
2 | . . . . . . . . |
1 | . . . . . . . . |
  +-----------------+
    a b c d e f g h

Unfortunately, there are three coordinate systems at play: 0 at upper-left, as assigned in the challenge; a1 at lower-left, as standard chess notation; and 0 at far right, as standard bit notation. It's a bit complicated to keep these straight, so get used to tilting your monitor.

By the way, in chess notation, the numbers 1–8 are called ranks and the letters a–h are called files.

Now we'll do a standard searching procedure. At every stage, a board represents all of the reachable positions within that number of steps. For example, at stage 0, only the starting position is reachable. At stage 1, the starting position, as well as all legal moves therefrom, are reachable. A bitboard is perfect for this kind of manipulation: each step expands the number of positions that are available.

board square_to_board(long square);
board step(board b);

int main(int argc, char *argv[]) {
    /* ... */

    board b = square_to_board(start);
    for (; moves>0; moves--)
        b = step(b);

    if (b & square_to_board(end))
        puts("True");
    else
        puts("False");

    return 0;
}

Okay, put on your coordinate galoshes — it's time to get dirty.

Let's assume our knight is in one position: there is only one "on" bit in the board. I've chosen that he is on c3. There are eight possible positions he could move to.

Each of these moves is possible with a simple bit shift. To move to, say, a2, we shift him left 6 bits — leftwise shifts move down-rank (down the board) and up-file (right the board). So we can think of this as … << 8, thus moving down one rank, followed by … >> 2, thus moving left two files.

But wait! What happens if our knight falls off the right or left edge? Such moves should be illegal, but with bit shifts, he'll just warp to an adjacent rank. In order to prevent this, for each possible move, we mask off the bits that would result in a warp. Let's take a specific example: which squares can move down one and left two?

  +-----------------+
8 | . . * * * * * * | - FC
7 | . . * * * * * * | - FC
6 | . . * * * * * * | - FC
5 | . . * * * * * * | - FC
4 | . . * * * * * * | - FC
3 | . . * * * * * * | - FC
2 | . . * * * * * * | - FC
1 | . . . . . . . . | - 00
  +-----------------+
    a b c d e f g h

The dot squares would fall off an edge with that move (c3 → a2); the star squares would not. Each rank of the board can be represented by eight bits, "on" where the square would result in a legal move. (Left squares are the least significant bits.) So the entire board can be represented by 64 bits. (Upper ranks are the least significant bytes.) This mask is 0x00FCFCFCFCFCFCFC.

In summary, to make a single move, we mask off the squares which would fall off the edge, then simply bit-wise shift the resulting board. When we started, we had the set of all possible positions. After the mask, we had the set of all possible positions that would survive shifting. After the shift, we had the set of all possible positions resulting from that specific move.

board step(board b) {
    board e4 = (0x3F3F3F3F3F3F3F00 & b) >> 6;
    board d5 = (0x7F7F7F7F7F7F0000 & b) >> 15;
    /* ... */
    board e2 = (0x003F3F3F3F3F3F3F & b) << 10;

    return b | e4 | d5 | b5 | a4 | a2 | b1 | d1 | e2;
}

Here's another way to think about this:

1. For every possible position on the board [for each bit in the board],
2. for every possible move direction [for each of e4, d5, etc.],
3. if the move doesn't result in warping [bit-wise and with a mask],
4. make that move [bit-wise shift],
5. and add it to the set of possible squares [bit-wise or].

Hopefully that was a useful introduction to applied bit-wise arithmetic! I'll leave the extensions as an exercise for the reader.

I'm doing this using traditional exploration methods. Nothing domain specific (I suppose there's a fancy efficient solution out there).

Here's my random walk implementation for now (later I'll post an updated BFS implementation).

#!/usr/bin/env python3

from collections import namedtuple
from random import sample
from typing import Set, List, Tuple, Optional


WIDTH = 8
HEIGHT = 8
Coord = namedtuple("Coord", ["x", "y"])


def coord_to_index(coord: Coord) -> int:
    return coord.y * WIDTH + coord.x


def index_to_coord(index: int) -> Coord:
    return Coord(index % WIDTH, index // WIDTH)


def position_valid(coord: Coord) -> bool:
    return (
        coord.x >= 0 and coord.x < WIDTH and
        coord.y >= 0 and coord.y < HEIGHT
    )


def shift_coord(coord: Coord, offset: Tuple[int, int]) -> Coord:
    return Coord(coord.x + offset[0], coord.y + offset[1])


def next_moves(current: Coord) -> Set[Coord]:
    possible_changes = [
        (1, 2), (2, 1), (-1, 2), (-2, 1),
        (1, -2), (2, -1), (-1, -2), (-2, -1)
    ]

    return {
        shift_coord(current, offset)
        for offset in possible_changes
        if position_valid(shift_coord(current, offset))
    }


def random_walk(current: Coord, seen: Set[Coord]) -> Optional[Coord]:
    try:
        return sample(next_moves(current) - seen, 1)[0]
    except ValueError:
        # Set of possible moves is empty
        return None


def knight_bot(start: int, end: int, max_moves: int) -> bool:
    current = index_to_coord(start)
    goal = index_to_coord(end)
    seen: Set[Coord] = {current}

    print(current)

    for _ in range(max_moves):
        current = random_walk(current, seen)

        if current is None:
            return False

        print(current)

        if current == goal:
            return True

        seen.add(current)

    return False


print(knight_bot(16, 21, 4))

It can eventually get a good solution :P

$ ./knightbot.py 
Coord(x=0, y=2)
Coord(x=2, y=1)
Coord(x=4, y=0)
Coord(x=5, y=2)
True

I have pretty nice solution. There is no bruteforcing, everything is calculated. It doesn't take into account infinite boards, repeating boards and sizes of boards, but I'll fix it later.

First of all, let's focus on the y coordinate. We can go to target y by rising our y position by either 1 or 2. With this knowledge, we can get list of numbers it can take us to get to y (I assume we won't go up and down again). This list is about <delta.y / 2; delta.y> (sometimes plus 1). This is the amount of turns we have to use when moving by x coordinate. Let's call this list n.

We have our coordinate A.x and target coordinate B.x. We have to go through delta.x tiles within q, q ∊ n turns. We have two moves available: one that moves us 1 tile left/right and costs two turns (two tiles up), or one that moves us two tiles left/right and costs one turn (one tile up). To get to target position, we have to use delta.x / 2 turns (sometimes plus 2). Now, we just have to move around the position until we spend all q turns. We can move around and return to the same direction with costs 2, 5, and, if delta.x %2 == 1, we can once use 1.

This gives us nice amount of moves. Without the 1 move, we can use any amount of turns - except 1 and 3. With the extra 1 move, we can use any amount of moves.

Checkmate, bruteforce.

main(List<String> args) {
  print(canKnightMove(Point(4, 7), Point(4, 13), Settings.normal(3)));
}

bool canKnightMove(Point from, Point to, Settings settings) {
  if (from == to) return true;
  var possibleMovesOnY = getPossibleMovesOnYAxis(from, to, settings);
  return existsPathToTarget(from, to, settings, possibleMovesOnY);
}

/// Get possible number of moves on Y axis. If `maximumTurns` in settings is specified and it is not null,
/// this method can return emtpy list if there is no solution without the need
/// to know all possible moves
List<int> getPossibleMovesOnYAxis(
    Point source, Point target, Settings settings) {
  var delta = source - target;

  int minimumNumberOfTurns = delta.y ~/ 2;
  if (delta.y % 2 == 1) {
    minimumNumberOfTurns++;
  }

  if (settings.maximumTurns != null &&
      minimumNumberOfTurns > settings.maximumTurns) {
    return List<int>();
  }

  int maximumNumberOfTurnsWithoutTurningBack = (delta.y ~/ 2) * 2;
  // TODO: This only works if the solution doesn't require turning back
  // TODO: I'm not taking into account repeating board

  if (minimumNumberOfTurns > maximumNumberOfTurnsWithoutTurningBack)
    return new List<int>();

  return List<int>.generate(
      max(maximumNumberOfTurnsWithoutTurningBack,
              (settings.maximumTurns ?? 0)) -
          minimumNumberOfTurns,
      (i) => minimumNumberOfTurns + i);
}

/// Returns if there is path from `source` to `target`.
bool existsPathToTarget(Point source, Point target, Settings settings,
    List<int> allowedNumbersOfTurns) {
  var delta = source - target;

  // TODO: I'm not taking into account repeating board or board size
  // Now, I have following problem:
  // I have source destination and target destination
  // I have to get path to target
  // I have maximum number of actions I can take (`allowedNumbersOfTurns`)
  // I have two actions: One moves me two points to any x direction and costs one action
  // And the other one moves me one point to any x direction and costs two actions
  // I have to spend all action points.

  // Minimum cost: (delta is delta.x) if delta %2 == 0, then cost is delta ~/ 2
  // Minimum cost: If not, it is ~/ 2 + 2
  // If (delta %2 == 1), once additionalCost is 1
  // next additionalCosts is +2 and +5
  // If there is any cost that is minimumCost + n*add2 + m*add5 + q*add1, we have solution!
  // (where q is the once additional cost)

  int minimalCost = delta.x ~/ 2;
  if (delta.x % 2 == 1) minimalCost += 2;

  bool canUseOnceAdditionalCost = (delta.x % 2 == 1);

  // Don't worry about this statement yet, explanation is below at the end of this method
  if (canUseOnceAdditionalCost) return true;

  // These are additional costs after minimal cost was subtracted
  List<int> additionalRequiredCostAfterMinimal = List<int>.generate(
      allowedNumbersOfTurns.length,
      (i) => allowedNumbersOfTurns[i] - minimalCost);

  if (additionalRequiredCostAfterMinimal.any((value) => value == 0))
    return true;
  if (additionalRequiredCostAfterMinimal.every((value) => value < 0))
    return false;

  // Now, we have to check if any of these values can be created by combination of 2 and 5
  // If canUseOnceAdditionalCost, these values *can* be lowered by 1 before the above check
  // What is the magic of these numbers? We can create *any* number with them, except for
  // 1 or 3. So if we can use 1 (the canUseOnceAdditionalCost), we are guaranteed we get there.
  if (additionalRequiredCostAfterMinimal
      .any((value) => value != 1 && value != 3)) return true;

  return false;
}

class Point {
  int x, y;
  Point(this.x, this.y);
  Delta operator -(Point b) {
    return Delta(abs(this.x - b.x), abs(this.y - b.y));
  }

  bool operator ==(Object b) {
    return b is Point && this.x == b.x && this.y == b.y;
  }
}

class Delta {
  int x, y;
  Delta(this.x, this.y);
}

class Settings {
  /// Maximum number of allowed turns. Can be `null`.
  int maximumTurns;

  /// Maximum width of game board. Can be `null` (unlimited).
  int maximumWidth;

  /// Maximum height of game board. Can be `null` (unlimited).
  int maximumHeight;

  /// If one can go from one side of game board to another.
  /// This assumes `maximumWidth` and `maximumHeight` are specified.
  ///
  /// This is not supported yet.
  bool isRepeating;

  Settings.normal(int this.maximumTurns) {
    this.maximumHeight = 8;
    this.maximumWidth = 8;
    this.isRepeating = false;
  }
}

num abs(num number) => number >= 0 ? number : -number;
num max(num a, num b) => a >= b ? a : b;

^{Edit: highlighted syntax}

It's a bit late and I haven't run it through any rigorous test cases, but here's my quick and dirty brute-force PHP solution:

<?php

class KnightMoveValidator {

    private $cached_valid_moves;

    public function __construct() {
        $this->cached_valid_moves = array_fill(0, 64, null);
    }

    private function getValidMoves($start) {
        $valid_moves = array(-17, -15, -10, -6, 6, 10, 15, 16);

        $distance_from_top = floor($start / 8);
        $distance_from_left = $start % 8;

        if($distance_from_top < 1) {
            $valid_moves = array_diff($valid_moves, array(-10, -6));
        }

        if($distance_from_top < 2) {
            $valid_moves = array_diff($valid_moves, array(-17, -15));
        }

        if($distance_from_top > 5) {
            $valid_moves = array_diff($valid_moves, array(15, 17));
        }

        if($distance_from_top > 6) {
            $valid_moves = array_diff($valid_moves, array(6, 10));
        }

        if($distance_from_left < 1) {
            $valid_moves = array_diff($valid_moves, array(-17, 15));
        }

        if($distance_from_left < 2) {
            $valid_moves = array_diff($valid_moves, array(-10, 6));
        }

        if($distance_from_left > 5) {
            $valid_moves = array_diff($valid_moves, array(-6, 10));
        }

        if($distance_from_left > 6) {
            $valid_moves = array_diff($valid_moves, array(-15, 17));
        }

        return $valid_moves;
    }

    public function isMovePossible($start, $target, $max_moves) {
        if($max_moves === 0) {
            return $start === $target;
        }

        if($start === $target) {
            return true;
        }

        $valid_moves = $this->cached_valid_moves[$start] ?? $this->getValidMoves($start);

        foreach($valid_moves as $target_offset) {
            if($this->isMovePossible($start + $target_offset, $target, $max_moves - 1)) {
                return true;
            }
        }

        return false;
    }
}

$move_validator = new KnightMoveValidator();
echo $move_validator->isMovePossible(16, 21, 4) ? 'Test case passes.' : 'Test case fails.';

?>