Semi-random starting position (new)

This is a reference post summarizing ideas for improving the current model of generating varied starting positions, created by runarberg:
https://runarberg.github.io/random-go-stone-placements/

This new thread was created as the first one got pretty long (could someone add “(old)” at the end of the name and lock the previous thread?thanks @AdamR):
https://forums.online-go.com/t/semi-random-starting-position/27801

  • What constitutes an interesting/uninteresting starting position? We currently have stone-free margin (no stones near edges) and spreading apart. Is there any other factor?

  • To reduce clustering there are two types of ideas so far, each with a few specific models.

    1. Biased placing of stones
    • adaptive probability field: table of probabilities over the board that changes as stones are placed.
    • loose circle packing: guaranteeing certain length of minimum separation between stones. (edit: this feels too restrictive alone; perhaps combine?)
    1. Post-processing a randomly generated configuration
    • repulsive random walk: probability to move in each direction varies with crowdedness.
    • reluctant walker: accept or reject a candidate move according to relative crowdedness of current and candidate location (aka Metropolis-Hastings algorithm).
  • There are multiple possible definitions for crowdedness.

    • distance to nearest stone.
    • each stone weighted according to distance: diluted contributions.
    • number of stones in a given radius: neighbor counting.
  • Taxicab geometry might be suitable: kosumi and one-space jump are considered the same distance.

  • I’m thinking of relearning programming to attempt simulating and comparing those models. I’m looking at ipython as it seems simplest but let me know if anyone knows a language better suited for this (grid based simulation).

  • The only method for comparison so far is visual inspection of generated configurations.

  • Using AI to ensure certain degree of fairness, which can be circumvented somewhat by some form of I-cut-you-choose at beginning of game. Bonus problem: optimal placement of a hole, which works like the edge, to balance the configuration of stones.

  • There is an unrelated OGS group with a similar idea:
    https://online-go.com/group/1557

3 Likes

I don’t think the other thread was too long to manage. There are also drawbacks to splitting the discussion like this:

  1. It’s more cumbersome to quote and reference things that were already said in the previous thread.
  2. The older content in the other thread may be less likely to be read, and hence they become diminished.

Since @runarberg has already built a prototype (with open source code here: https://github.com/runarberg/random-go-stone-placements), you can play with that and try modifying the javascript.

This is a highly subjective question. With komi betting, perhaps any random position could be considered interesting, since it would be up to the players to judge possibly bizarre positions. With a fixed komi, maybe “interesting” should be something judged to have a roughly 50-50 win-rate (maybe within plus/minus 5%) by analysis with a strong AI engine.

There are many ways to try to quantify crowdedness, but I don’t think that alone can capture “interesting”.

2 Likes

Oh yeah, I forgot about this. I was also working on something, but I’ve never finished it… Perhaps today or tomorrow

2 Likes

It’s been a while since I played around with probabilistic programing, but I do recommend ipython (or jupyter). Python in particular has plenty of good libraries and tutorials for implementing different random walks or probability fields. I used Julia and R a lot in school (jupyter supports all three) but they might not be as approachable for beginners—if only for the fact that python has plenty of tutorials aimed for beginners.

As a bonus, if your notebook is clear enough (and the license is liberal enough) I might be able to read it and translate the algorithm to JavaScript and add as an option to my app.

Good luck, and foremost, have fun. Programing (as with all other crafts) is mostly about having fun making nice things, and sharing the things you’ve made.

1 Like

@yebellz

I’m not opposed to merging the two threads and I wasn’t aware of the consequences you mentioned. I was just thinking it might make it easier for people who haven’t been following the original thread to contribute.

Should we merge the threads?

  • merge
  • keep them separate

0 voters

Regarding javascript, my plan is to experiment in an easier language (or one that is natural to the problem) and worry about translating later.

Regarding the evaluation of generated positions, I was thinking of something like generating and mixing large number of configurations and vote like/dislike (or possibly finer options) without knowing which model they belong to, but it’s started to dawn on me that the difference might be too multifaceted to decide which model is better.

Even when working with AI, we might need a way to generate promissing candidates as I assume AI-based evaluation is the costly part of the process.

Also, if possible, I feel the swap rule (white can choose to swap colors on first move) is more elegant than komi-betting, although the configurations need to be in certain band of fairness as black’s best first move needs to be good enough.

1 Like

Came up with a potential name: 散碁(さんご sango). 散る(ちる) means to scatter and is also used to describe falling of leaves in autumn or of cherry blossom petals in spring. It didn’t seem to be taken judging by casual web searching.

It could also be written 3go if we restrict the number of stones per player to 3, as 3 is pronounced “san” in japanese. I feel 3 is a natural candidate for an even game but that might be confusing.

EDIT:
ちらし碁, analogous to ちらし寿司, has the advantage of having less homophones.

2 Likes

Or just “35” regarless of how manyn stones are used. :smiley:

1 Like

(loose circle packing + random walk) starts out with even coverage over the board and adds variation.

The question is: Is there a way to set this up so that configurations are fair with the swap rule?

EDIT:
loose circle packing with radius r;
r-step random walk, introducing stone-free margin here (stone-free margin < r);
with komi 3.5, is there a move for black that AI can play that makes the game approximately even?;
if not, swap colors, check the existance of a move again;
if not, start from beginning

1 Like

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.

If you want to format code I recommend surrounding it in triple (fenced) backticks and a language indicatator e.g:

```py
# This is python code
print("Hello, world!")
```
```js
// This is JavaScript
console.log("Hello, world!");
```

aside: To format this I surrounded the snippet in four backticks ```` ```lang <snippet>``` ````

4 Likes

Finally got it working with arbitrary board size and number of stones.

Result:
  Scatter Stones on Go Board

  To run the program normally, add -O (capital alphabet 'O') flag:
  $ python3 -O scatter-go.py

  To run tests, without the flag:
  $ python3 scatter-go.py

Randomly Place Stones (@: black, &: white):
 . a b c d e f g h i j k l m n o p q r s t u v w x y z { | }
 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 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Spread Apart Stones (numbers show radii of separation):
 . a b c d e f g h i j k l m n o p q r s t u v w x y z { | }
 1 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
 2 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
 3 + + + 2 + 2 + @ + 2 + 2 + & + 2 + + + + + + + + + + + + +
 4 + + 2 + 2 + 2 + 2 + + + 2 + 2 + + + + + + + + + + + + + +
 5 + + + & + 2 + 2 + + + + + 2 + + + + + + + + + + 2 + + + +
 6 + + 2 + 2 + + + + + + + + + + + + + + + + + + 2 + 2 + + +
 7 + + + 2 + + + 2 + + + + + + 2 + + + + + 3 + 2 + & + 2 + +
 8 + + 2 + + + 2 + 2 + + + + 2 + 2 + + + 3 + 3 + 2 + 2 + + +
 9 + + + 2 + 2 + @ + 2 + + 2 + & + 2 + 3 + + + 3 + 2 + + + +
10 + + & + 2 + 2 + 2 + + + + 2 + 2 + 3 + + @ + + 3 + + + + +
11 + + + 2 + + + 2 + + + + + + 2 + + + 3 + + + 3 + + + + + +
12 + + 2 + + + 3 + + + + + + + + 2 + + + 3 + 3 + + + + + + +
13 + + + + + 3 + 3 + + + + + + 2 + 2 + + + 3 + + + + + 2 + +
14 + + + + 3 + + + 3 + + + + 2 + @ + 2 + + + 2 + + + 2 + + +
15 + + + 3 + + @ + + 3 + + + + 2 + 2 + + + 2 + 2 + 2 + & + +
16 + + + + 3 + + + 3 + + + + + + 2 + + + 2 + & + 2 + 2 + + +
17 + + + + + 3 + 3 + + + + + + + + 3 + + + 2 + 2 + 3 + 2 + +
18 + + 2 + + + 3 + + + + + + + + 3 + 3 + + + 2 + 3 + 3 + + +
19 + + + 2 + + + + + + 2 + + + 3 + + + 3 + + + 3 + + + 3 + +
20 + + & + 2 + + + + 2 + 2 + 3 + + @ + + 3 + 3 + + @ + + + +
21 + + + 2 + + 2 + 2 + @ + 2 + 3 + + + 3 + + 3 3 + + + 3 + +
22 + + 2 + + 2 + 2 + 2 + 2 + + + 3 + 3 + + 3 + 3 3 + 3 + + +
23 + + + + 2 + & + 2 + 2 + + + + + 3 + + 3 + + + 3 3 + + + +
24 + + + + + 2 + 2 + + + + + + + + + + 3 + + @ + + 3 3 + + +
25 + + + + 2 + 2 + + + 2 + + + + + + 2 + 3 + + + 3 3 + 3 + +
26 + + + 2 + 2 + + + 2 + 2 + + + + 2 + 2 + 3 + 3 3 + + + + +
27 + + 2 + @ + 2 + 2 + & + 2 + + 2 + & + 2 + 3 3 + + @ + + +
28 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
29 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Random Walk on Stones (%: previous location):
 . a b c d e f g h i j k l m n o p q r s t u v w x y z { | }
 1 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
 2 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
 3 + + + 2 + 2 + % + 2 + 2 + & + 2 + + + + + + + + + + + + +
 4 + + 2 + 2 + 2 + @ + + + 2 + 2 + + + + + + + + + + + + + +
 5 + + + % + 2 + 2 + + + + + 2 + + + + + + + + + + 2 + + + +
 6 + + 2 + 2 + + + + + + + + + + + + + + + + + + 2 + 2 + + +
 7 + + + & + + + 2 + + + + + + 2 + + + + + 3 + 2 + & + 2 + +
 8 + + 2 + + + 2 + 2 + + + + & + 2 + + + 3 + 3 + 2 + 2 + + +
 9 + + + 2 + 2 + % + 2 + + 2 + % + 2 + 3 + + + 3 + 2 + + + +
10 + + % + 2 + 2 + 2 + + + + 2 + 2 + 3 + + % + + 3 + + + + +
11 + + + & + + + @ + + + + + + 2 + + + 3 + @ + 3 + + + + + +
12 + + 2 + + + 3 + + + + + + + + @ + + + 3 + 3 + + + + + + +
13 + + + + + 3 + 3 + + + + + + 2 + 2 + + + 3 + + + + + 2 + +
14 + + + + 3 + + + 3 + + + + 2 + % + 2 + + + 2 + + + 2 + + +
15 + + + 3 + + % @ + 3 + + + + 2 + 2 + + + & + 2 + 2 + & + +
16 + + + + 3 + + + 3 + + + + + + 2 + + + 2 + % + 2 + 2 + + +
17 + + + + + 3 + 3 + + + + + + + + 3 + + + 2 + 2 + 3 + 2 + +
18 + + 2 + + + 3 + + + + + + + + 3 + 3 + + + 2 + 3 + 3 + + +
19 + + + 2 + + + + + + @ + + + 3 + + + 3 + + + 3 + @ + 3 + +
20 + + % + & + + + + 2 + 2 + 3 + @ % + + 3 + 3 + + % + + + +
21 + + + 2 + + 2 + 2 + % + 2 + 3 + + + 3 + + 3 3 + + + 3 + +
22 + + 2 + + 2 + 2 + 2 + 2 + + + 3 + 3 + + 3 + 3 3 + 3 + + +
23 + + + + 2 + % + 2 + 2 + + + + + 3 + + 3 + + + 3 3 + + + +
24 + + + + + 2 + & + + + + + + + + + + 3 + + % + + 3 3 + + +
25 + + + + 2 + 2 + + + 2 + + + + + + & + @ + + + 3 3 + @ + +
26 + + + 2 + @ + + + 2 + 2 + + + + 2 + 2 + 3 + 3 3 + + + + +
27 + + 2 + % + 2 + 2 + % + & + + 2 + % + 2 + 3 3 + + % + + +
28 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
29 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Only Show Stones:
 . a b c d e f g h i j k l m n o p q r s t u v w x y z { | }
 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 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

The packing algorithm now starts out with separate radii of 1 for all stones and progressively increment the radius of one of them at a time when they get successfully separated by the current radii. It quits after failing to improve for certain number of times consecutively, which can be adjusted.

I wonder if there’s a way to get similar result by starting with uniform probability distribution over the board and applying some kind of transformation to it after each stone placement. It might be more efficient since there would be no trial/error involved.

scatter-go.py
import copy
import enum
import itertools
import random

print(
"""
  Scatter Stones on Go Board

  To run the program normally, add -O (capital alphabet 'O') flag:
  $ python3 -O scatter-go.py

  To run tests, without the flag:
  $ python3 scatter-go.py
""")

if __debug__:
  print('\nRunning tests...\n')

###### Adjustable Constants

SIZE_BOARD = 29
N_STONE_BLK, N_STONE_WHT = 11, 11
MARGIN_EDGE = 2  # stone-free margin
FACTOR_NONEMPTY = 25  # scale factor for n of consecutive failures to tolerate in spread_stones()

#################################################################################################

###### Derived Constants

N_STONE = N_STONE_BLK + N_STONE_WHT
END_LOW = 1 + MARGIN_EDGE
END_HIGH = SIZE_BOARD - MARGIN_EDGE

###### Custom Types

class Vec:
  """2-d vector: v(ertical), h(orizontal)"""
  def __init__(self, vert, horz):
    self.v, self.h = vert, horz
  def __neg__(self):
    return self.__class__(-self.v, -self.h)
  def __add__(self, other):
    return self.__class__(self.v + other.v, self.h + other.h)
  def __sub__(self, other):
    return self + (-other)
  def __repr__(self):
    return '(%s, %s)' % (self.v, self.h)
  def __eq__(self, other):
    try:
      return self.v == other.v and self.h == other.h
    except:
      return self.v == other[0] and self.h == other[1]
  def __lt__(self, other):
    if self.v < other.v:
      return True
    elif self.v == other.v:
      return self.h < other.h
    return False

if __debug__:
  assert Vec(4, 9) - Vec(2, -2) == (2, 11)

class CoordOutOfBounds(Exception): pass
def assertCOOB(stmt):  # stmt must be passed in quotes
  try:
    eval(stmt)
    assert False, 'expected CoordOutOfBounds'
  except CoordOutOfBounds: pass

class Coord(int):
  """coordinate on Go board"""
  def __new__(cls, val):
    if val < END_LOW or val > END_HIGH:
      raise CoordOutOfBounds
    return super().__new__(cls, val)
  def __add__(self, other):
    res = super().__add__(other)
    return self.__class__(res)
  def __sub__(self, other):
    return self + (-other)
  @classmethod
  def random(cls):
    return cls(random.randint(END_LOW, END_HIGH))

if __debug__:
  assertCOOB( 'Coord(4) - 2' )

class Stone(Vec):
  def __init__(self, vert, horz):
    try:
      self.v, self.h = Coord(vert), Coord(horz)
    except:
      raise
  def __repr__(self):
    return '(%s, %s)' % (self.v, chr(96 + self.h)) 

if __debug__:
  assertCOOB( 'Stone(4, 9) - Vec(2, -2)' )

class Direction(enum.IntEnum):
  """4 cardinal directions"""
  south = 0
  east = 1
  north = 2
  west = 3
  def __neg__(self):
    return self.__class__((self + 2) % 4)
  def apply_sign(self, num):
    if num < 0: return -self
    else: return self
  def sign(self):
    if self < 2: return 1
    else: return -1
  @classmethod
  def vert(cls):
    return cls(0)
  @classmethod
  def horz(cls):
    return cls(1)
  def apply_step(self, stone):
    stn = copy.deepcopy(stone)  # avoid side effect
    if self % 2 == Direction.vert():
      step = Vec(self.sign(), 0)
    elif self % 2 == Direction.horz():
      step = Vec(0, self.sign())
    try:
      return stn + step
    except CoordOutOfBounds:
      raise

if __debug__:
  stn_test = Stone(4, 9)
  stn_test = Direction.north.apply_step(stn_test)
  assert stn_test == (3, 9)
  assertCOOB( 'Direction.north.apply_step(stn_test)' )

class NonNegInt(int):
  def __sub__(self, other):
    res = super().__sub__(other)
    return self.__class__(max(0, res))

if __debug__:
  assert NonNegInt(2) - 4 == 0

###### Randomly Place Stones

def random_stones():
  stones = []
  while len(stones) < N_STONE:
    candidate = Vec(Coord.random(), Coord.random())
    if candidate not in stones:
      stones.append(candidate)
  return stones

###### Spread Apart Stones

def pairs_with_total(total):
  """[a, b] where a + b == total"""
  for n in range(total // 2 + 1):
    yield (n, total - n)

if __debug__:
  expected = [(0, 7), (1, 6), (2, 5), (3, 4)]
  assert sorted(pairs_with_total(7)) == sorted(expected)

def circle_taxicab(radius):
  """relative position of points on taxicab circle"""
  vecs = []
  for pair in pairs_with_total(radius):
    for vert, horz in itertools.permutations(pair, 2):  # [a, b], [b, a]
      # reflective symmetries
      for sign_v, sign_h in itertools.product([-1, 1], repeat=2):
        candidate = Vec(sign_v * vert, sign_h * horz)
        if candidate not in vecs:
          vecs.append(candidate)
  return vecs

if __debug__:
  expected = [(0, 7), (0, -7), (7, 0), (-7, 0),
    (1, 6), (-1, 6), (1, -6), (-1, -6), (6, 1), (-6, 1), (6, -1), (-6, -1),
    (2, 5), (-2, 5), (2, -5), (-2, -5), (5, 2), (-5, 2), (5, -2), (-5, -2),
    (3, 4), (-3, 4), (3, -4), (-3, -4), (4, 3), (-4, 3), (4, -3), (-4, -3)]
  assert sorted(circle_taxicab(7)) == sorted(expected)

def sparsity_direction(stn, radius, stones):
  """
  Sparsity in each direction starts with given radius.
  Stones on taxicab circle, if any, reduce the sparsity
  by their component in that direction. (0 <= component <= radius)

  For example, a stone directly in some direction reduces sparsity
  by full radius, making the sparsity in that direction 0.
  In contrast, a stone orthogonal to that direction does not affect
  the sparsity in that direction at all.
  """
  spars_dirs = {key:NonNegInt(radius) for key in [dr for dr in Direction]}
  for d in circle_taxicab(radius):
    try:
      candidate = Stone(stn.v + d.v, stn.h + d.h)
      if candidate in stones:
        spars_dirs[Direction.vert().apply_sign(d.v)] -= abs(d.v)
        spars_dirs[Direction.horz().apply_sign(d.h)] -= abs(d.h)
    except:
      continue
  if min(spars_dirs.values()) == radius:  # no stones on circle
    return None
  return spars_dirs

if __debug__:
  origin_test = Stone(9, 8)
  stones_test = [origin_test,
                 Stone(9, 7), Stone(8, 8),
                 Stone(9, 6), Stone(8, 9),
                 Stone(6, 8), Stone(10, 6), Stone(11, 9),
                 Stone(6, 9), Stone(8, 5), Stone(11, 10)]
  # south, east, north, west
  expected = [ [1, 1, 0, 0],
               [2, 1, 1, 0],
               [0, 2, 0, 1],
               [2, 1, 0, 1] ]
  for idx in range(len(expected)):
    spars_dirs = sparsity_direction(origin_test, idx + 1, stones_test)
    assert list(spars_dirs.values()) == expected[idx]
  assert sparsity_direction(origin_test, 5, stones_test) is None

def pick_direction(spars_dirs):
  """probability to be picked is proportional to sparsity"""
  dirs = list(spars_dirs.keys())
  spars = list(spars_dirs.values())
  return random.choices(dirs, spars)[0]  # choices() return in list

def increment_at_boundary(nums):
  """[1, 1, 0, 0, 0] -> [1, 1, 1, 0, 0]"""
  n_min = min(nums)
  for idx, n in enumerate(nums):
    if n == n_min:
      nums[idx] += 1
      break

if __debug__:
  nums_test = [1, 1, 1, 0, 0]
  expected = [[1, 1, 1, 1, 0],
              [1, 1, 1, 1, 1],
              [2, 1, 1, 1, 1]]
  for idx, nums_e in enumerate(expected):
    increment_at_boundary(nums_test)
    assert nums_test == nums_e

def spread_stones(stones_):
  stones = copy.deepcopy(stones_)
  count_empty = len(stones)
  count_nonempty = len(stones) * FACTOR_NONEMPTY
  radii_repel = [1 for _ in range(len(stones))]
  stones_backup = copy.deepcopy(stones)
  radii_backup = radii_repel[:]
  while count_nonempty > 0:
    for idx, stn in enumerate(stones):
      rad_max = radii_repel[idx] + max(radii_repel)
      for rad in range(1, rad_max + 1):
        spars_dirs = sparsity_direction(stn, rad, stones)
        if spars_dirs is None:  # no stones at radius
          if rad == rad_max:
            count_empty -= 1
            if count_empty == 0: # all stones made it at current radii
              if __debug__:
                print_board(stones, stones, radii_repel)
              # reset counters
              count_empty = len(stones)
              count_nonempty = len(stones) * FACTOR_NONEMPTY
              # prepare for challenge
              stones_backup = copy.deepcopy(stones)
              radii_backup = radii_repel[:]
              # increment radius for one of the stones
              increment_at_boundary(radii_repel)
        else:  # found stones at radius
          # reset count_empty as moving a stone might put it
          # within another stone's range
          count_empty = len(stones)
          count_nonempty -= 1
          # look ahead one step farther
          spars_dirs_next = sparsity_direction(stn, rad + 1, stones)
          if spars_dirs_next is not None:
            for dr in spars_dirs:
              # scaling analogous to when adding fractions
              spars_dirs[dr] *= rad + 1
              spars_dirs[dr] += spars_dirs_next[dr] * rad
          try:  # possibly at edge margin
            stones[idx] = pick_direction(spars_dirs).apply_step(stn)
          except:  # possibly cornered
            break  # move to next stone in case it really is
          break
      if count_nonempty == 0:
        break
  # go back to before it was still working
  return stones_backup, radii_backup

###### Random Walk

def random_walk_stones(stones_, radii_repel):
  stones = copy.deepcopy(stones_)
  directions = [dr for dr in Direction]
  for idx in range(len(stones)):
    for _ in range(radii_repel[idx]):
      while True:
        try:
          stones[idx] = random.choice(directions).apply_step(stones[idx])
          break
        except: 
          continue
  return stones

###### Display

def print_board(stones, stones_prev=None, radii_repel=None):
  board = []
  # we start by making a blank board
  # first row shows coordinate names in alphabets
  board.append([' .'] + [chr(97 + n) for n in range(SIZE_BOARD)])
  # remaining rows
  for n in range(1, SIZE_BOARD + 1):
    board.append(['{:>2}'.format(n)] + ['+']*SIZE_BOARD)
  # draw things by substituting symbols
  if radii_repel is not None:
    for idx, rad in enumerate(radii_repel):
      stn = stones_prev[idx]
      for d in circle_taxicab(rad):
        try:
          board[stn.v + d.v][stn.h + d.h] = '%s' % (rad)
        except:
          continue
  if stones_prev is not None:
    for stn_prev in stones_prev:
      board[stn_prev.v][stn_prev.h] = '%'
  for idx, stn in enumerate(stones):
    if idx < N_STONE_BLK:
      board[stn.v][stn.h] = '@'
    else:
      board[stn.v][stn.h] = '&'
  # print row by row
  for row in board:
    print(' '.join(row))
  print('')

###### Put Everything Together

def main():
  print('Randomly Place Stones (@: black, &: white):')
  stones = random_stones()
  print_board(stones)
  stones, radii_repel = spread_stones(stones)
  print('Spread Apart Stones (numbers show radii of separation):')
  print_board(stones, stones, radii_repel)
  stones_prev = copy.deepcopy(stones)
  print('Random Walk on Stones (%: previous location):')
  stones = random_walk_stones(stones, radii_repel)
  print_board(stones, stones_prev, radii_repel)
  print('Only Show Stones:')
  print_board(stones)

if __debug__:
  print('Passed all tests!!!')
elif __name__ == '__main__':
  main()

###### END OF FILE
2 Likes

Regarding the fairness of starting positions, an alternative to asking AI might be to add a rule that slightly favors stones toward the center, if the fairness has something to do with stones near corners and edges being more efficient than ones toward the center.

The following is an idea that might work as such: Once in a while, say every 11th moves, one of the players (perhaps starting with white), in turn, gets to move one of her stones exactly certain number of steps, say 5, in one of cardinal directions, as well as playing a normal move.

Another idea is to draft stones on the board. Thue-Morse sequence, which was discussed in another thread a while ago, might be useful for this.

1 Like