A python sketch aiming to find optimal play for the Big Brother S16 Knight Moves competition.

knight_moves.py

""""
A quick sketch aiming to find optimal play for the Big Brother S16 Knight Moves
competition. As it stands, this python version is waaay to slow.

Videos of the competition:
 * http://www.cbs.com/shows/big_brother/video/fOLeybDVKA8LopMlgTZj05M__wPnnYMI/big-brother-knight-moves/
 * https://tv.yahoo.com/video/big-brother-knight-moves-015945588-cbs.html

wins found per second
{2: 343036, 3: 527582, 4: 383558} 11259.6712734
{2: 354319, 3: 586846, 4: 434611} 12152.5018645
{2: 354319, 3: 658913, 4: 486609} 12391.3047645
{2: 390865, 3: 697627, 4: 515919} 10372.5703306
{2: 433345, 3: 727448, 4: 553965} 10971.9917901
{2: 472603, 3: 772300, 4: 579392} 10935.7019839


- state rep is 4 knights position
- (move history or dually prior occupied squares)
- who's move

import Queue

search_tree = Queue.Queue()

initial_state = (
    0, # Turn: 0-3
    [(0, 0), (7, 0), (7, 7), (0, 7)], # Position of all knights.
    set(), # Used squares.
}

prior_used can be used to detect collision depending on whether the playrs current
positions are at the head of the list or not
"""
from collections import defaultdict
import threading

STACK_DEPTH = 0
KNIGHT_MOVES = [
    (-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]

WIN_COUNT = defaultdict(int)
WIN_DEPTH = defaultdict(int)


def piece_moves((x, y)):
    return set((x + xo, y + yo) for xo, yo in KNIGHT_MOVES
                             if 0 <= x + xo <= 7 and 0 <= y + yo <= 7)
          # pos = (int, int)
          #int,  [(int, pos)]  set(pos)
def search(turn, prior_positions, prior_used):
    global STACK_DEPTH
    STACK_DEPTH += 1

    player, position = prior_positions[turn]
    if len(prior_positions) == 1:
        # print 'game over, stack depth', STACK_DEPTH
        # print 'prior_positions wins', prior_positions
        # print 'prior_used', prior_used
        WIN_COUNT[player] += 1
        WIN_DEPTH[STACK_DEPTH] += 1
        STACK_DEPTH -= 1
        return

    move_options = piece_moves(position) - prior_used
    if not move_options:
        # print 'player {} eliminated, stack depth {}'.format(
            # player, STACK_DEPTH)

        new_positions = list(prior_positions)
        del new_positions[turn]
        search(turn % len(new_positions),
               new_positions,
               prior_used | set([position]))

    for move in move_options:
        capture = [(i, op) for (i, op) in enumerate(prior_positions) if move == op[1]]
        if capture:
            n, capture_player = capture[0]
            # print 'player {} captured, stack depth {}'.format(
                # capture_player[0], STACK_DEPTH)

            # print 'turn', turn
            # print 'prior_positions capture', prior_positions
            # print 'move', move
            # print 'prior_used', prior_used

            new_positions = list(prior_positions)
            new_positions[turn] = (player, move)
            del new_positions[n]
            search(turn % len(new_positions),
                   new_positions,
                   prior_used | set([position]))
        else:
            new_positions = list(prior_positions)
            new_positions[turn] = (player, move)
            search((turn + 1) % len(new_positions),
                   new_positions,
                   prior_used | set([position]))

    STACK_DEPTH -= 1

def set_interval(func, sec):
    def func_wrapper():
        set_interval(func, sec)
        func()
    t = threading.Timer(sec, func_wrapper)
    t.start()
    return t

import time
LAST_COUNT = 0
LAST_TIME = time.time()

def log():
    global LAST_TIME, LAST_COUNT
    new_time = time.time()
    new_count = sum(WIN_COUNT.values())
    rate = (new_count - LAST_COUNT) / (new_time - LAST_TIME)
    print dict(WIN_COUNT), rate

    LAST_COUNT = new_count
    LAST_TIME = new_time

set_interval(log, 10.0)
print search(0,
             [
                (1, (0, 0)),
                (2, (7, 0)),
                (3, (7, 7)),
                (4, (0, 7)),
             ],
             set([]))

print WIN_COUNT