The following file (scatter-go.py), which couldn’t be attached, contains (circle packing + random walk) part of the problem.
EDIT: https://pastebin.com/ejMPBDt1
scatter-go.py
DEBUG_MODE = False # whether to print intermediate states
N_STONE = 3 # number of stones per player, only supports 3
SIZE_BD = 19 # size of board, only supports 19
MARGIN = 2 # stone-free margin
# packing radius was estimated as follows:
# from https://en.wikipedia.org/wiki/Circle_packing_in_a_square
# which is about the euclidean (as opposed to taxicab) version of the problem
# when n = 6, side length = 5.328...
# rounding off 19 / 5.328 yields 3
R_PACKING = 3
stones = []
# print stone
def print_stone(stone):
print("({0}, {1})".format(stone[0], chr(96 + stone[1])))
# print stones
def print_stones(stones):
for a in range(len(stones)):
print_stone(stones[a])
# print the board
def print_board(stones):
# create 19 x 19 empty board
board = [' . a b c d e f g h i j k l m n o p q r s']
for a in range(1, SIZE_BD + 1):
board.append('{:>2} + + + + + + + + + + + + + + + + + + +'.format(a))
# place stones by replacing a character
for a in range(len(stones)):
x, y = stones[a][0], stones[a][1]
if a < len(stones)/2: # black stone
# I couldn't do: board[x][1 + 2*y] = '@'
# so I found the following work-around online
board[x] = '{0}{1}{2}'.format(
board[x][:1 + 2*y], '@', board[x][1 + 2*y + 1:])
else: # white stone
board[x] = '{0}{1}{2}'.format(
board[x][:1 + 2*y], '0', board[x][1 + 2*y + 1:])
# print board
for a in range(len(board)):
print(board[a])
# randomly place stones on the board
from random import randint
while True:
candidate = [randint(1, SIZE_BD), randint(1, SIZE_BD)]
if candidate in stones:
continue
else:
stones.append(candidate)
if len(stones) == N_STONE * 2:
break
# remove duplicates in list of lists
def remove_duplicates(l_orig):
l_new = []
for a in range(len(l_orig)):
if l_orig[a] not in l_new:
l_new.append(l_orig[a])
return l_new
# find all points that are at given taxicab distance from given origin
def points_at_distance(origin, distance):
x, y = origin[0], origin[1]
points = []
# from square expanded by going distance from origin in 4 cardinal directions
for a in range(distance + 1):
for b in range(distance + 1):
if a + b == distance: # taxicab distance
points.append([x - a, y - b])
points.append([x - a, y + b])
points.append([x + a, y - b])
points.append([x + a, y + b])
return remove_duplicates(points)
# intersection of two lists of lists
def intersection_ll(l_1, l_2):
l_new = []
for a in range(len(l_1)):
for b in range(len(l_2)):
if l_1[a] == l_2[b]:
l_new.append(l_1[a])
break
return l_new
# find all stones that are at given taxicab distance from given origin
def stones_at_distance(origin, distance, stones):
points = points_at_distance(origin, distance)
return intersection_ll(points, stones)
# find all points, just outside the board, that are at given taxicab distance from given origin,
# which is used as proxy for edges
def edges_at_distance(origin, distance):
points = points_at_distance(origin, distance)
edges = []
for a in range(len(points)):
x, y = points[a][0], points[a][1]
if x < 1 or x > SIZE_BD or y < 1 or y > SIZE_BD:
edges.append([x, y])
return edges
from enum import Enum
Direction = Enum('Direction', 'w n s e')
# find directions that are least crowded
def find_steps(stone, points_repulsive):
x, y = stone[0], stone[1]
density = {k:0 for k in [Direction.w, Direction.n, Direction.s, Direction.e]}
for a in range(len(points_repulsive)):
s, t = points_repulsive[a][0], points_repulsive[a][1]
if s < x: # somewhere in west
if t < y: # NW
density[Direction.n] += 0.5
density[Direction.w] += 0.5
elif t == y: # exactly west
density[Direction.w] += 1
else: # SW
density[Direction.s] += 0.5
density[Direction.w] += 0.5
elif s == x: # exactly north or south
if t < y: # north
density[Direction.n] += 1
else: # south
density[Direction.s] += 1
else: # somewhere in east
if t < y: # NE
density[Direction.n] += 0.5
density[Direction.e] += 0.5
elif t == y: # exactly east
density[Direction.e] += 1
else: # SE
density[Direction.s] += 0.5
density[Direction.e] += 0.5
density_min = min(density.values())
return [k for k in density if density[k] == density_min]
# apply step randomly chosen from candidate directions,
# making sure not to step out of bounds
from random import choice
def apply_step(stone, directions, margin):
x, y = stone[0], stone[1]
lower_bound, upper_bound = 1 + margin, SIZE_BD - margin
# pick a direction and step in that direction
while True:
if directions == []:
break
pick = choice(directions)
if pick == Direction.w:
if x == lower_bound:
directions.remove(Direction.w)
else:
x -= 1
break
elif pick == Direction.n:
if y == lower_bound:
directions.remove(Direction.n)
else:
y -= 1
break
elif pick == Direction.s:
if y == upper_bound:
directions.remove(Direction.s)
else:
y += 1
break
elif pick == Direction.e:
if x == upper_bound:
directions.remove(Direction.e)
else:
x += 1
break
return [x, y]
# modify the configuration so that stones are at least 2*R_PACKING apart
# and edges are at least R_PACKING away (circle packing)
counter = len(stones)
while True:
for a in range(len(stones)):
if counter == 0:
break
if DEBUG_MODE:
print_stone(stones[a])
for b in range(1, 2*R_PACKING + 1):
# find stones at given taxicab distance, if any
points_repulsive = stones_at_distance(stones[a], b, stones)
if b <= R_PACKING: # detect edges only within one packing radius
points_repulsive.extend(edges_at_distance(stones[a], b))
if points_repulsive == []: # none found
if b == 2*R_PACKING: # all clear
counter -= 1
break
else: # found
# reset counter as moving a stone might put it within another stone's range
counter = len(stones)
stones[a] = apply_step(stones[a], find_steps(stones[a], points_repulsive), 0)
break
if DEBUG_MODE:
print_stone(stones[a])
print_board(stones)
print("")
if counter == 0:
break
print("after circle packing with radius {}".format(R_PACKING))
print_board(stones)
# random walk, taking into account stone-free margin
directions_all = [e for e in Direction]
for a in range(len(stones)):
for b in range(R_PACKING):
stones[a] = apply_step(stones[a], directions_all, MARGIN)
print("")
print("after {0}-step random walk with stone-free margin of {1}".format(R_PACKING, MARGIN))
print_board(stones)
The circle packing algorithm works as follows. Start with randomly scattered stones. Pick one stone, then scan for stones/edges at distance 1. If found, nudge the stone in one of the least crowded directions and move on to another stone. If not found, increase the distance unless it’s already twice the packing radius for stones and single time the packing radius for edges. If we hit that point consequtively for the number of stones on the board, it’s done.
It seems to be working although I can’t tell if it succeeded in making all packing solutions equiprobable, or if all packing solutions are reachable at all.
Let me know somewhere it can be made more efficient or easier to understand.
On the other hand, does anyone know if checking the existance of an “even” move in AI -part is reasonable?
EDIT:
The file got formatted weirdly.
EDIT2:
I reformatted the code according to runarberg’s advice.
I realized that, currently, the circle packing part does not distinguish a stone at SSE (1, 2) and ESE (2, 1) when scanning radius is 3, for example.
Also, there’s a possibility to add “staying still” option in random walk.
