Skip to content

Instantly share code, notes, and snippets.

@Reconcyl
Created August 16, 2019 07:46
Show Gist options
  • Save Reconcyl/ec39b093a2e35cb8dd7697f0ec3022ab to your computer and use it in GitHub Desktop.
Save Reconcyl/ec39b093a2e35cb8dd7697f0ec3022ab to your computer and use it in GitHub Desktop.
Mancala Brute Forcer (txti.es/mancala)
SIDE_LENGTH = 6
HOLE_INIT = 4
STONES = 2 * SIDE_LENGTH * HOLE_INIT
class Board:
def __init__(self, holes=None):
if holes:
self.holes = holes
else:
empty_side = [HOLE_INIT] * SIDE_LENGTH
self.holes = empty_side + [0] + empty_side
def score(self):
return self.holes[SIDE_LENGTH]
def good(self):
# return True
# return self.score() > STONES/2
return self.score() > STONES/2 and all(map(lambda x: x == 0, self.holes[:SIDE_LENGTH]))
def play(self, hole):
holes = self.holes[:]
def scoop(holes, idx):
result = holes[idx]
holes[idx] = 0
return result
while True:
for _ in range(scoop(holes, hole)):
hole = (hole + 1) % len(holes)
holes[hole] += 1
if hole == SIDE_LENGTH:
return True, Board(holes)
if holes[hole] <= 1:
return False, Board(holes)
def __str__(self):
strs = [str(v) for v in self.holes]
max_len = max(map(len, strs))
strs = [s.rjust(max_len) for s in strs]
return (" ".join(strs[SIDE_LENGTH+1:][::-1]) +
"\n" + " ".join(strs[:SIDE_LENGTH+1]))
def __repr__(self):
return "Board({}, {}, {})".format(
self.holes[:SIDE_LENGTH],
self.holes[SIDE_LENGTH],
self.holes[SIDE_LENGTH+1:],
)
def print_path(path):
b = Board()
for move in path:
_, b = b.play(move)
print(str(move) + ":"); print(b); print()
paths = []
possibilities = [([], Board())]
while possibilities:
new_possibilities = []
for moves, board in possibilities:
for move in range(SIDE_LENGTH):
new_moves = moves + [move]
play_again, new_board = board.play(move)
if play_again:
new_possibilities.append((new_moves, new_board))
else:
if new_board.good():
paths.append((new_moves, new_board))
possibilities = new_possibilities
best_path = max(paths, key=lambda p: p[1].score())
print(best_path[1].score())
print("-".join(str(m) for m in best_path[0]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment