My friend and former NASA colleague Mel Montemerlo made this beautiful Konane set for me:
I don't have the woodworking skills to make anything nearly as nice as that, so instead I thought I'd use my coding skills to make a nice program to solve the game. It's the least I can do to return the favor to Mel.
Konane (or Kōnane) is a two-player board game from Hawaii. To set up the game, fill each space with a marble, alternating between black and white marbles in a checkerboard pattern. To complete the set-up, remove two adjacent marbles (one black, one white) from the board.
From there on, the players take turns, with black moving first. A move consists of jumping a marble of your color over an adjacent opponent marble, removing that marble, and landing on the empty space beyond it. If there is another opponent marble followed by another empty space in the same direction, the player may optionally make a double (or more) jump. Jumps may not be diagonal, and a multiple jump may not change directions.
When one player is unable to jump, that player loses.
(Some rules say the removed marbles must be either in a corner or in the very center; others say the two can be anywhere on the board. If you accept that they must be in a corner or the center, then there are only two distinct starting positions; the others ten are equivalent under rotation and reflection.)
A game is said to be solved if, for any state of the game that occurs during play, you can instantly say whether the player to move can force a win from that state.
The first thing to consider is whether a 6 by 6 board is small enough that we can solve the game by exhaustive search of the graph of possible states of the game. By state I mean an indication of everything that matters: whose turn it is to play, and what marbles are in what spaces. The player to move is either black or white, and each of the 36 spaces can either hold a marble or not, so an upper bound is 237 ≈ 137 billion game states. However, the rules for jumping constrain the possible states of the game; most of those theoretical states are unreachable from the start state. As a wild guess, I estimate that maybe 100 million to a billion states are rechable. That's few enough that I should be able to solve the game with exhaustive search. I'm lucky that Mel chose 6 by 6; even a 7 by 7 board would be far too large for exhaustive search.
I will define a function winner(state)
that will return the player who can force a win from that state, regardless of what the other player does. (There must be one such player, because ties are not allowed and there is no randomness.) Once I have cached the values of winner
, the optimal strategy is easy:
The number of states for the 6 by 6 board puts us right on the edge: small enough that I'm confident I can get the program to work; big enough to require some judicious implementation choices to save time and space. For example, a straightforward way to implement a game state would be a structure with two fields, player and board, where the board is a 6 by 6 array where each element is either black, white, or empty. But a billion of those structures would consume a lot of memory. A more efficient encoding is to represent the board as a bit string: a binary integer where bit s is a 1 if there is a marble in space s, according to the following numbering scheme:
0 1 2 3 4 5
6 7 8 9 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35
The bit representation for a board doesn't have to say whether a marble is black or white; black marbles can only be in spaces numbered 0, 2, 4, 7, 9, 11, ... (spaces where the x coordinates plus y coordinate is even) and white only in spaces 1, 3, 5, 6, 8, 10, ... (spaces where the x coordinate plus y coordinate is odd).
The representation of a state can also be a single int
, with the low-order bit being 1 for black, 0 for white, and the other bits being a board shifted left a bit.
Given this, the implementation choices are as follows:
int
) indicating which spaces hold marbles.get(board space)
returns the player on that space, or empty
.remove(board, spaces)
returns a new board with the marbles on spaces
removed.int
) indicating both the board and the player whose turn it is.start_state(removed)
returns a state with a full board except for removed
spaces.encode_state
and decode_state
join and split a board/player pair.space(x, y)
returns an integer representing the space with given x
and y
coordinates.x_(space)
and y_(space)
invert that.'*'
for black and 'o'
for white.other(player)
gives the opponent player.go(space, direction, k)
gives the space that is k
steps in direction
from space
.Here is the code:
from typing import *
from dataclasses import dataclass
from functools import lru_cache
from collections import Counter, defaultdict
from itertools import takewhile
import random
################ Types
Board = int # A board is a bit string with a 1 bit for each space with a marble
State = int # A state is a board shifted left, with a bit indicated whose turn it is
Space = int # A space is an integer from 0 to N**2 - 1
Player = str # A character, '*' or 'o'
Direction = int # Direction of movement (left, right, up, down)
################ Constants
N = 6
black = '*'
white = 'o'
empty = '·'
################ Boards
def get(board, space) -> str:
"""Get the contents of space on board: black, white, or empty."""
return (empty if board & (1 << space) == 0 else
black if (x_(space) + y_(space)) % 2 == 0 else
white)
def remove(board, spaces) -> Board:
"""Return a new board with the marbles on spaces removed."""
return board - sum(1 << s for s in spaces)
################ States
def start_state(removed=(0, 1)) -> State:
"""A new NxN board with a marble in all spaces, except `removed`,
which should be a tuple of two spaces (default upper-left corner)."""
full = sum(1 << s for s in range(N * N))
return encode_state(remove(full, removed), black)
def encode_state(board, player) -> State:
"""Combine the board and the player into a single int."""
return board * 2 + (player == black)
def decode_state(state) -> Tuple[Board, Player]:
"""Split the state into board and player components."""
return state // 2, (black if state & 1 else white)
################ Spaces
def space(x, y) -> int: return N * y + x
def x_(space) -> int: return space % N
def y_(space) -> int: return space // N
def center() -> Tuple[Space, Space]:
"""Two spaces in the center of the board."""
m = N // 2
return space(m, m), space(m - 1, m)
################ Players
def other(player) -> Player: return white if player == black else black
################ Directions
L, R, U, D = directions = (-1, +1, -N, +N)
def go(space, direction, steps=1) -> Optional[Space]:
"""The space that is `steps` in `direction` from `space`,
or `None` if going in that direction ends up off the board."""
x, y = x_(space), y_(space)
return (space + steps * direction
if (direction == L and steps <= x)
or (direction == R and steps < N - x)
or (direction == U and steps <= y)
or (direction == D and steps < N - y)
else None)
The representation of a state is not very informative to look at, neither in decimal nor binary notation:
start_state()
137438953465
bin(_)
'0b1111111111111111111111111111111111001'
I'll define a function, state_str
, to create better-looking output for a state:
def state_str(state) -> str:
"""A string depicting the given state of the game."""
board, player = decode_state(state)
def row(y): return f'{y + 1} | {" ".join(get(board, space(x, y)) for x in range(N))}'
return (f' {" ".join(columns[:N])} ({player} to move)\n +{"--" * N}\n' +
'\n'.join(row(y) for y in range(N)))
columns = 'abcdefghijklmnopqrstuvwxyz'
print(state_str(start_state()))
a b c d e f (* to move) +------------ 1 | · · * o * o 2 | o * o * o * 3 | * o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o *
print(state_str(start_state(removed=center())))
a b c d e f (* to move) +------------ 1 | * o * o * o 2 | o * o * o * 3 | * o * o * o 4 | o * · · o * 5 | * o * o * o 6 | o * o * o *
The next step is to define legal_moves(state)
which returns a list of the available legal moves from a state, and make_move(state, move)
which returns a new state that is the result of the chosen move.
A move is a structure with fields for the starting space, the ending space, and the space(s) of the opponent marble(s) that were jumped. I'll divide the task of finding legal moves into two phases: first define all the potential_moves
that start at a given square and go in a given direction. In that direction there can be a single jump, a double jump, etc.; as long as the jump doesn't go off the edge of the board. The jumps are processed in that order, so when we get to, say, a triple jump, we know that the single- and double-jumps were legal; that makes checking each jump for legality easier. The function potential_moves
doesn't consider what marbles are on the board; the function legal_moves
does.
I have these two separate functions and put a @lru_cache
on potential_moves
so that Move
objects are created only once (for each of the 36 spaces and 4 directions), not millions of times for each state. Because Move
s are not created millions of times, I'm not worried about trying to make them be efficient bit strings.
@dataclass
class Move:
"""A jumping move."""
start: Space
jumped: List[Space]
end: Space
def __str__(self):
start, end, *jumped = [f'{columns[x_(s)]}{y_(s) + 1}'
for s in (self.start, self.end, *self.jumped)]
return f'{start} → {end} jumping {" and ".join(jumped)}'
def legal_moves(state) -> List[Move]:
"""All possible moves for player from this state."""
board, player = decode_state(state)
opponent = other(player)
def legal(move) -> bool:
return get(board, move.jumped[-1]) == opponent and get(board, move.end) == empty
return [move for start in range(N * N) if get(board, start) == player
for d in directions
for move in takewhile(legal, potential_moves(start, d))]
@lru_cache(None)
def potential_moves(start: Space, d: Direction) -> List[Move]:
"""All potential moves starting from space and going in direction, shortest first."""
moves = []
for steps in range(2, N, 2):
end = go(start, d, steps)
if end is not None:
moves.append(Move(start, list(range(start + d, end, 2 * d)), end))
return moves
def make_move(state, move) -> State:
"""Make a move from this state to yield a new state."""
board, player = decode_state(state)
board2 = remove(board | 1 << move.end, [move.start, *move.jumped])
return encode_state(board2, other(player))
Here are some examples of how these functions work:
state1 = start_state()
state2 = make_move(state1, Move(start=12, jumped=[6], end=0))
print(state_str(state1))
{str(m): m for m in legal_moves(state1)}
a b c d e f (* to move) +------------ 1 | · · * o * o 2 | o * o * o * 3 | * o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o *
{'a3 → a1 jumping a2': Move(start=12, jumped=[6], end=0)}
print(state_str(state2))
{str(m): m for m in legal_moves(state2)}
a b c d e f (o to move) +------------ 1 | * · * o * o 2 | · * o * o * 3 | · o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o *
{'d1 → b1 jumping c1': Move(start=3, jumped=[2], end=1), 'c2 → a2 jumping b2': Move(start=8, jumped=[7], end=6), 'b3 → b1 jumping b2': Move(start=13, jumped=[7], end=1)}
potential_moves(space(0, 0), D)
[Move(start=0, jumped=[6], end=12), Move(start=0, jumped=[6, 18], end=24)]
We're now ready to play a game. The function play_game
takes as input a dictionary with two keys, black and white, each mapped to a strategy for that player. A strategy is a function that takes a state as input and returns a move.
Strategy = Callable[[State], Move]
def play_game(strategies: Dict[Player, Strategy], start=None, verbose=True) -> Player:
"""Play a game between black and white, using their respective strategies.
Return the player that wins the game."""
state = start or start_state()
while True:
board, player = decode_state(state)
if verbose: print(state_str(state))
moves = legal_moves(state)
if not moves:
if verbose: print(f'\n{player} has no moves and loses')
return other(player)
else:
move = strategies[player](state)
if verbose: print(f'\n{player} moves {move}\n')
assert move in moves
state = make_move(state, move)
def play_games(strategies, k, start=None) -> Counter:
"""Play k games silently; return a count of winning players."""
return Counter(play_game(strategies, start, False) for _ in range(k))
def random_strategy(state) -> Move:
"""Pick a random legal move."""
return random.choice(legal_moves(state))
Below black and white each play randomly:
randomly = {black: random_strategy, white: random_strategy}
play_game(randomly)
a b c d e f (* to move) +------------ 1 | · · * o * o 2 | o * o * o * 3 | * o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * * moves a3 → a1 jumping a2 a b c d e f (o to move) +------------ 1 | * · * o * o 2 | · * o * o * 3 | · o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * o moves d1 → b1 jumping c1 a b c d e f (* to move) +------------ 1 | * o · · * o 2 | · * o * o * 3 | · o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * * moves c3 → c1 jumping c2 a b c d e f (o to move) +------------ 1 | * o * · * o 2 | · * · * o * 3 | · o · o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * o moves e2 → a2 jumping d2 and b2 a b c d e f (* to move) +------------ 1 | * o * · * o 2 | o · · · · * 3 | · o · o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * * moves a5 → a3 jumping a4 a b c d e f (o to move) +------------ 1 | * o * · * o 2 | o · · · · * 3 | * o · o * o 4 | · * o * o * 5 | · o * o * o 6 | o * o * o * o moves e4 → e2 jumping e3 a b c d e f (* to move) +------------ 1 | * o * · * o 2 | o · · · o * 3 | * o · o · o 4 | · * o * · * 5 | · o * o * o 6 | o * o * o * * moves b4 → b2 jumping b3 a b c d e f (o to move) +------------ 1 | * o * · * o 2 | o * · · o * 3 | * · · o · o 4 | · · o * · * 5 | · o * o * o 6 | o * o * o * o moves c4 → e4 jumping d4 a b c d e f (* to move) +------------ 1 | * o * · * o 2 | o * · · o * 3 | * · · o · o 4 | · · · · o * 5 | · o * o * o 6 | o * o * o * * moves b6 → b4 jumping b5 a b c d e f (o to move) +------------ 1 | * o * · * o 2 | o * · · o * 3 | * · · o · o 4 | · * · · o * 5 | · · * o * o 6 | o · o * o * o moves b1 → b3 jumping b2 a b c d e f (* to move) +------------ 1 | * · * · * o 2 | o · · · o * 3 | * o · o · o 4 | · * · · o * 5 | · · * o * o 6 | o · o * o * * moves b4 → b2 jumping b3 a b c d e f (o to move) +------------ 1 | * · * · * o 2 | o * · · o * 3 | * · · o · o 4 | · · · · o * 5 | · · * o * o 6 | o · o * o * o moves d5 → b5 jumping c5 a b c d e f (* to move) +------------ 1 | * · * · * o 2 | o * · · o * 3 | * · · o · o 4 | · · · · o * 5 | · o · · * o 6 | o · o * o * * moves f2 → d2 jumping e2 a b c d e f (o to move) +------------ 1 | * · * · * o 2 | o * · * · · 3 | * · · o · o 4 | · · · · o * 5 | · o · · * o 6 | o · o * o * o moves f1 → b1 jumping e1 and c1 a b c d e f (* to move) +------------ 1 | * o · · · · 2 | o * · * · · 3 | * · · o · o 4 | · · · · o * 5 | · o · · * o 6 | o · o * o * * moves e5 → e3 jumping e4 a b c d e f (o to move) +------------ 1 | * o · · · · 2 | o * · * · · 3 | * · · o * o 4 | · · · · · * 5 | · o · · · o 6 | o · o * o * o moves b1 → b3 jumping b2 a b c d e f (* to move) +------------ 1 | * · · · · · 2 | o · · * · · 3 | * o · o * o 4 | · · · · · * 5 | · o · · · o 6 | o · o * o * * moves d6 → b6 jumping c6 a b c d e f (o to move) +------------ 1 | * · · · · · 2 | o · · * · · 3 | * o · o * o 4 | · · · · · * 5 | · o · · · o 6 | o * · · o * o moves a2 → a4 jumping a3 a b c d e f (* to move) +------------ 1 | * · · · · · 2 | · · · * · · 3 | · o · o * o 4 | o · · · · * 5 | · o · · · o 6 | o * · · o * * moves b6 → b4 jumping b5 a b c d e f (o to move) +------------ 1 | * · · · · · 2 | · · · * · · 3 | · o · o * o 4 | o * · · · * 5 | · · · · · o 6 | o · · · o * o moves d3 → d1 jumping d2 a b c d e f (* to move) +------------ 1 | * · · o · · 2 | · · · · · · 3 | · o · · * o 4 | o * · · · * 5 | · · · · · o 6 | o · · · o * * moves b4 → b2 jumping b3 a b c d e f (o to move) +------------ 1 | * · · o · · 2 | · * · · · · 3 | · · · · * o 4 | o · · · · * 5 | · · · · · o 6 | o · · · o * o moves f3 → d3 jumping e3 a b c d e f (* to move) +------------ 1 | * · · o · · 2 | · * · · · · 3 | · · · o · · 4 | o · · · · * 5 | · · · · · o 6 | o · · · o * * moves f6 → d6 jumping e6 a b c d e f (o to move) +------------ 1 | * · · o · · 2 | · * · · · · 3 | · · · o · · 4 | o · · · · * 5 | · · · · · o 6 | o · · * · · o moves f5 → f3 jumping f4 a b c d e f (* to move) +------------ 1 | * · · o · · 2 | · * · · · · 3 | · · · o · o 4 | o · · · · · 5 | · · · · · · 6 | o · · * · · * has no moves and loses
'o'
We can play 1000 random games and see who has an advantage:
play_games(randomly, 1000)
Counter({'o': 512, '*': 488})
It looks like white has a slight advantage if both players play randomly. But what if they are more clever?
As promised, here I define:
winner
to determine which player can force a win from a given state.optimal_strategy
to play perfectly, taking advantage of the knowledge cached in winner
.@lru_cache(None)
def winner(state) -> Player:
"""The player that can force a win from this state."""
_, player = decode_state(state)
return (player if any(winner(make_move(state, move)) == player
for move in legal_moves(state))
else other(player))
def optimal_strategy(state) -> Move:
"""Make a winning move if there is one."""
_, player = decode_state(state)
for move in legal_moves(state):
if winner(make_move(state, move)) == player:
return move
return move
Before starting a time-consuming computation of the winner for a 6 by 6 board, I'd like to quickly validate the program on a smaller board; let's say 4 by 4. But I can't simply execute the statement N = 4
, because other parts of the program depend on the value of N
: the "up" and "down" directions U
and D
, as well as the caches for potential_moves
and winner
. So I'll introduce the function set_N
:
def set_N(n):
"""Use an n x n board; set global variables accordingly."""
global N, R, L, U, D, directions
if n != N:
N = n
L, R, U, D = directions = (-1, +1, -N, +N)
potential_moves.cache_clear()
winner.cache_clear()
Now we can solve 4 by 4 Konane:
set_N(4)
winner(start_state()), winner(start_state(removed=center()))
('o', 'o')
That says that white is the winner on a 4 by 4 board, from either starting position.
Here's an optimally-played 4 by 4 game:
optimally = {black: optimal_strategy, white: optimal_strategy}
play_game(optimally)
a b c d (* to move) +-------- 1 | · · * o 2 | o * o * 3 | * o * o 4 | o * o * * moves a3 → a1 jumping a2 a b c d (o to move) +-------- 1 | * · * o 2 | · * o * 3 | · o * o 4 | o * o * o moves d1 → b1 jumping c1 a b c d (* to move) +-------- 1 | * o · · 2 | · * o * 3 | · o * o 4 | o * o * * moves c3 → c1 jumping c2 a b c d (o to move) +-------- 1 | * o * · 2 | · * · * 3 | · o · o 4 | o * o * o moves b1 → d1 jumping c1 a b c d (* to move) +-------- 1 | * · · o 2 | · * · * 3 | · o · o 4 | o * o * * has no moves and loses
'o'
As expected, white wins.
Although white will win every game with optimal play, if white plays randomly, an optimal black player can win a majority of games:
play_games({black: optimal_strategy, white: random_strategy}, 1000)
Counter({'*': 541, 'o': 459})
We can repeat the exercise on a 5 by 5 board. This time I will check how long it takes to solve:
set_N(5)
%time winner(start_state()), winner(start_state(removed=center()))
CPU times: user 668 ms, sys: 3.7 ms, total: 671 ms Wall time: 671 ms
('*', '*')
With a 5 by 5 board, black wins from either starting position. The computation takes about 2/3 of a second.
Finally we are ready to solve the 6 by 6 board. A 6 by 6 board has 211 = 2048 times more states than a 5 by 5 board, and each state is bigger and thus will take more time to process. So I estimate it will take about a half hour to fill the winner
cache for a 6 by 6 board. Let's find out (one starting position at a time):
set_N(6)
%time winner(start_state())
CPU times: user 3min 55s, sys: 439 ms, total: 3min 55s Wall time: 3min 58s
'o'
So white wins a 6 by 6 game when we start with corner marbles removed. And the computation was a lot faster than I guessed!
How many states were explored? The cache_info
method will tell us:
winner.cache_info()
CacheInfo(hits=8397349, misses=10071659, maxsize=None, currsize=10071659)
The currsize
field is the number of states in the cache; about 10 million.
Now let's see who wins if we start with the center marbles removed:
%time winner(start_state(removed=center()))
CPU times: user 1h 10min 59s, sys: 7.85 s, total: 1h 11min 7s Wall time: 1h 13min 34s
'o'
White wins there too, but my celebration over the speed of the program was a bit premature–that took a full hour, double my estimate. We can count the total number of states from both starting positions:
winner.cache_info()
CacheInfo(hits=188641148, misses=145177949, maxsize=None, currsize=145177949)
That's 145 million states. I guess it makes sense that there would be more reachable states starting from a position with the center pieces removed, because we can spread to any corner. It also makes sense that the corner-removed board leads to a search space that is more tree-like (the ratio of hits/misses–that is, the ratio of paths that lead to a state a second time to total states–is 0.8) and the center-removed board leads to a search space that is more graph-like (the ratio is 1.3).
Here's an optimally-played game (which we expect white to win):
play_game(optimally)
a b c d e f (* to move) +------------ 1 | · · * o * o 2 | o * o * o * 3 | * o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * * moves a3 → a1 jumping a2 a b c d e f (o to move) +------------ 1 | * · * o * o 2 | · * o * o * 3 | · o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * o moves d1 → b1 jumping c1 a b c d e f (* to move) +------------ 1 | * o · · * o 2 | · * o * o * 3 | · o * o * o 4 | o * o * o * 5 | * o * o * o 6 | o * o * o * * moves a5 → a3 jumping a4 a b c d e f (o to move) +------------ 1 | * o · · * o 2 | · * o * o * 3 | * o * o * o 4 | · * o * o * 5 | · o * o * o 6 | o * o * o * o moves f1 → d1 jumping e1 a b c d e f (* to move) +------------ 1 | * o · o · · 2 | · * o * o * 3 | * o * o * o 4 | · * o * o * 5 | · o * o * o 6 | o * o * o * * moves c5 → a5 jumping b5 a b c d e f (o to move) +------------ 1 | * o · o · · 2 | · * o * o * 3 | * o * o * o 4 | · * o * o * 5 | * · · o * o 6 | o * o * o * o moves c2 → a2 jumping b2 a b c d e f (* to move) +------------ 1 | * o · o · · 2 | o · · * o * 3 | * o * o * o 4 | · * o * o * 5 | * · · o * o 6 | o * o * o * * moves e5 → c5 jumping d5 a b c d e f (o to move) +------------ 1 | * o · o · · 2 | o · · * o * 3 | * o * o * o 4 | · * o * o * 5 | * · * · · o 6 | o * o * o * o moves a2 → a4 jumping a3 a b c d e f (* to move) +------------ 1 | * o · o · · 2 | · · · * o * 3 | · o * o * o 4 | o * o * o * 5 | * · * · · o 6 | o * o * o * * moves a5 → a3 jumping a4 a b c d e f (o to move) +------------ 1 | * o · o · · 2 | · · · * o * 3 | * o * o * o 4 | · * o * o * 5 | · · * · · o 6 | o * o * o * o moves e2 → c2 jumping d2 a b c d e f (* to move) +------------ 1 | * o · o · · 2 | · · o · · * 3 | * o * o * o 4 | · * o * o * 5 | · · * · · o 6 | o * o * o * * moves d4 → d2 jumping d3 a b c d e f (o to move) +------------ 1 | * o · o · · 2 | · · o * · * 3 | * o * · * o 4 | · * o · o * 5 | · · * · · o 6 | o * o * o * o moves f3 → f1 jumping f2 a b c d e f (* to move) +------------ 1 | * o · o · o 2 | · · o * · · 3 | * o * · * · 4 | · * o · o * 5 | · · * · · o 6 | o * o * o * * moves f4 → d4 jumping e4 a b c d e f (o to move) +------------ 1 | * o · o · o 2 | · · o * · · 3 | * o * · * · 4 | · * o * · · 5 | · · * · · o 6 | o * o * o * o moves c4 → a4 jumping b4 a b c d e f (* to move) +------------ 1 | * o · o · o 2 | · · o * · · 3 | * o * · * · 4 | o · · * · · 5 | · · * · · o 6 | o * o * o * * moves f6 → f4 jumping f5 a b c d e f (o to move) +------------ 1 | * o · o · o 2 | · · o * · · 3 | * o * · * · 4 | o · · * · * 5 | · · * · · · 6 | o * o * o · o moves c2 → e2 jumping d2 a b c d e f (* to move) +------------ 1 | * o · o · o 2 | · · · · o · 3 | * o * · * · 4 | o · · * · * 5 | · · * · · · 6 | o * o * o · * moves d6 → f6 jumping e6 a b c d e f (o to move) +------------ 1 | * o · o · o 2 | · · · · o · 3 | * o * · * · 4 | o · · * · * 5 | · · * · · · 6 | o * o · · * o moves e2 → e4 jumping e3 a b c d e f (* to move) +------------ 1 | * o · o · o 2 | · · · · · · 3 | * o * · · · 4 | o · · * o * 5 | · · * · · · 6 | o * o · · * * moves b6 → d6 jumping c6 a b c d e f (o to move) +------------ 1 | * o · o · o 2 | · · · · · · 3 | * o * · · · 4 | o · · * o * 5 | · · * · · · 6 | o · · * · * o moves a4 → a2 jumping a3 a b c d e f (* to move) +------------ 1 | * o · o · o 2 | o · · · · · 3 | · o * · · · 4 | · · · * o * 5 | · · * · · · 6 | o · · * · * * moves c3 → a3 jumping b3 a b c d e f (o to move) +------------ 1 | * o · o · o 2 | o · · · · · 3 | * · · · · · 4 | · · · * o * 5 | · · * · · · 6 | o · · * · * o moves a2 → a4 jumping a3 a b c d e f (* to move) +------------ 1 | * o · o · o 2 | · · · · · · 3 | · · · · · · 4 | o · · * o * 5 | · · * · · · 6 | o · · * · * * moves a1 → e1 jumping b1 and d1 a b c d e f (o to move) +------------ 1 | · · · · * o 2 | · · · · · · 3 | · · · · · · 4 | o · · * o * 5 | · · * · · · 6 | o · · * · * o moves f1 → d1 jumping e1 a b c d e f (* to move) +------------ 1 | · · · o · · 2 | · · · · · · 3 | · · · · · · 4 | o · · * o * 5 | · · * · · · 6 | o · · * · * * has no moves and loses
'o'
Here's a chart of who has a forced win for various values of N, in the cases where the two marbles are removed from the corner and from the center:
N | Corner | Center |
---|---|---|
4 | white | white |
5 | black | black |
6 | white | white |
7+ | ????? | ????? |
I'll stop here, but here are some things that you could look into if you are interested:
int
returned by start_state()
uses 32 bytes of memory. There is overhead to store the reference count, the type of the object, etc. Other languages can represent a state in just 8 bytes, as a 64-bit integer.Some simple tests of the low-level functions:
def test():
set_N(6)
state = start_state()
board, player = decode_state(state)
assert state == encode_state(board, player)
assert player == black
assert get(board, 0) == empty and get(board, 2) == black and get(board, 3) == white
board2 = remove(board, [3, 4])
assert get(board2, 3) == empty
s = space(0, 0)
assert (go(s, R), go(s, L), go(s, U), go(s, D)) == (1, None, None, 6)
s = space(2, 1)
assert s == 8 and x_(s) == 2 and y_(s) == 1
assert go(s, R) == space(3, 1)
assert go(s, L) == space(1, 1)
assert go(s, U) == space(2, 0)
assert go(s, D) == space(2, 2)
assert go(s, L, 2) == space(0, 1)
assert go(s, L, 3) == None
assert other(black) == white and other(white) == black
assert potential_moves(0, R) == [Move(start=0, jumped=[1], end=2),
Move(start=0, jumped=[1, 3], end=4)]
return True
test()
True