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)