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>``` ````
Finally got it working with arbitrary board size and number of stones.
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.
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
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.
Idea 3: Black decides which stones belong to which player, and plays a move -> white decides whether to play on or swap colors.
EDIT:
Possibly with komi, say 3.5
After subdividing the board into rectangles, it seems possible to get random-walk-like effect by picking coordinates inside rectangles with frequencies according to numbers in Pascalās triangle. (Thereās a table containing numbers from Pascalās triangle in an article on random walk.)
Recursively subdividing a rectangle with largest area is one way but I felt itās a bit too regular.
I tentatively feel the need to bound the ratios:
Iām looking for an algorithm that randomly gives one out of all possible subdivisions. Or perhaps simpler or approximate reformulation of the problem.
Iām guessing it might be computationally more efficient than going via taxicab circle like before.
Used a simpler trapezial-shaped weights instead of Pascalās.
~ Scatter Stones via Subdivision of Go Board into Rectangles ~
Subdivide the board into small rectangles:
. 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 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Pick a pair of adjoining small rectangles and
combine them to make one big rectangle for each stone to be placed.
Numbers are weights for placing a stone in the next step and
shown in a manner of a windmill ('v'ertical and 'h'orizontal):
v + h v + + h h v + h h
v + + v + + + + h h + v
h h v h h h + v
. 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 + + 5 # 1 + + + + + + + + + 1 # # # # 4 3 2 1 + + + + + +
4 + + 5 # # + + + + + + + + + 1 2 3 4 4 # # # 1 + + + + + +
5 + + 5 # # + + + + + + + + + + + + + + + + + + + + + + + +
6 + + 5 # # + + + + + + + + + + + + + + + 1 # 1 + + + + + +
7 + + 5 # # + + + + + + + + + + + + + + + 2 # # + + + + + +
8 + + # # 5 + + + + + + + + + + + + + + + 3 # # + + + + + +
9 + + # # 4 + + + + + + + + + + + + + + + 4 # # + + + + + +
10 + + # # 3 + + + + + + + + + + + + + + + 5 # # + + + + + +
11 + + # # 2 + + + + + + + + + + + + + + + # # 5 + + + + + +
12 + + 1 1 1 + + + + + + + + + + + + + + + # # 4 + + + + + +
13 + + + + + + + + + + + + + + + + + + + + # # 3 + + + + + +
14 + + 1 % % % 3 2 1 + + + + + + + + + + + # # 2 + 1 # 1 + +
15 + + 3 3 3 3 % % 1 + + + + + + + + + + + 1 1 1 + 2 # # + +
16 + + + + + + + + + + + + + + + + + + + + + + + + 2 # # + +
17 + + + + + + + + + + 1 % 1 + 1 # # # # 4 3 2 1 + # # 2 + +
18 + + + + + + + + + + 2 % % + 1 2 3 4 4 # # # 1 + 1 1 1 + +
19 + + + + + + + + + + 2 % % + + + + + + + + + + + + + + + +
20 + + 1 # 1 + + + + + % % 2 + + + + + + + 1 % % % 3 3 3 + +
21 + + 2 # # + + + + + 1 1 1 + + + + + + + 1 2 3 3 % % 1 + +
22 + + 2 # # + + + + + + + + + + + + + + + + + + + + + + + +
23 + + # # 2 + + + + + 1 % 1 + 1 % % % % 4 3 2 1 + + + + + +
24 + + 1 1 1 + + + + + 2 % % + 1 2 3 4 4 % % % 1 + + + + + +
25 + + + + + + + + + + 2 % % + + + + + + + + + + + + + + + +
26 + + 1 # # # 3 2 1 + % % 2 + 1 % % % % 4 3 2 1 + + + + + +
27 + + 3 3 3 3 # # 1 + 1 1 2 + 1 2 3 4 4 % % % 1 + + + + + +
28 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
29 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Place 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 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
~ End ~
import copy
import random
print('\n~ Scatter Stones via Subdivision of Go Board into Rectangles ~\n')
if __debug__:
print('To run the program normally, add -O (capital o) flag:')
print('$ python3 -O scatter-go-rect.py\n')
print('Running tests...\n')
###### Adjustable Constants
SIZE_BOARD = 29
N_STONE = 13
SEP_MIN = 1 # minimum separation between stones
MARGIN_EDGE = 2 # minimum separation between stone and edge of board
SCALE_N_RECT = 3/2 # scale factor for n of smaller rectangles,
# from which adjoining pair is reserved
# for each stone
##################################################################
###### Derived Constants
END_LOW = 1 + MARGIN_EDGE
END_HIGH = SIZE_BOARD - MARGIN_EDGE
###### Custom Types
class Rect:
"""rectangle defined by northwest and southeast corner points inclusive"""
def __init__(self, nw=[0]*2, se=[0]*2):
self.nw, self.se = nw, se
def __repr__(self):
return '(%s, %s; %s, %s)' % ('{:>2}'.format(self.nw[0]), chr(96 + self.nw[1]), '{:>2}'.format(self.se[0]), chr(96 + self.se[1]))
@classmethod
def weights_trapez(cls, start, end):
"""example outputs: [1, 2, 2, 2, 1] and [1, 2, 2, 1]"""
weights = []
length = end - start + 1
if length == 1:
return [1]
ascending = [n for n in range(1, 1 + length//2)]
# if rectangle is next to edge margin,
# don't decrease weights
# example outputs: [2, 2, 2, 2, 1] and [2, 2, 2, 1]
if start == END_LOW:
weights += [length//2] * len(ascending)
else:
weights += ascending
if length % 2 == 1: # odd
weights += [length//2]
if end == END_HIGH:
weights += [length//2] * len(ascending)
else:
weights += ascending[::-1]
return weights
def random_point(self):
"""randomly pick a point inside rectangle"""
point = [self.nw[0], self.nw[1]]
for axis in range(2): # vert or horz
start, end = self.nw[axis], self.se[axis]
weights = self.__class__.weights_trapez(start, end)
# [0] since choices() return in list
point[axis] += random.choices(range(end - start + 1), weights)[0]
return point
if __debug__:
END_LOW, END_HIGH = 3, 17 # fix for test
pairs_test = [
[(4, 12), [1, 2, 3, 4, 4, 4, 3, 2, 1]],
[(3, 12), [5, 5, 5, 5, 5, 5, 4, 3, 2, 1]],
[(11, 17), [1, 2, 3, 3, 3, 3, 3]] ]
for inp, oup in pairs_test:
assert Rect.weights_trapez(inp[0], inp[1]) == oup
class Grid_Rect:
"""rectangles arranged in a grid, and weight for each"""
def __init__(self, n_stone, lens_side):
self.len = [len(lens_side[0]), len(lens_side[1])]
self.weights = [n_stone] * (self.len[0] * self.len[1])
# need for deepcopy here was extremely hard to find
self.rects = [copy.deepcopy(Rect()) for _ in range(self.len[0] * self.len[1])]
## set northwest and southeast corner points for each rectangle
for axis in range(2): # vert or horz
coord = END_LOW
for idx_side, side in enumerate(lens_side[axis]): # for each side segment of rectangle
idx_rect = [0]*2
idx_rect[axis] = idx_side # fix row or column
# for each rectangle in a row or column
axis_other = (axis + 1) % 2 # the other axis
for idx_shift in range(self.len[axis_other]):
idx_rect[axis_other] = idx_shift
self.rect_vh(idx_rect).nw[axis] = coord
self.rect_vh(idx_rect).se[axis] = coord + side - 1
coord += side + SEP_MIN
def to_vh(self, idx):
v = idx // self.len[1]
h = idx - v*self.len[1]
return [v, h]
def to_line(self, idx_vh):
return idx_vh[0]*self.len[1] + idx_vh[1]
def rect_vh(self, idx_vh):
return self.rects[self.to_line(idx_vh)]
def __repr__(self):
res = ''
for v in range(self.len[0]):
for h in range(self.len[1]):
res += repr(self.rect_vh((v, h))) + ', '
res += '\n'
return res
def neighbors_cardinal(self, idx_rect):
"""indices of rectangles in cardinal directions"""
idxs_neighb = []
idx_v, idx_h = self.to_vh(idx_rect)
for dv, dh in ((1, 0), (0, 1)):
for sign in (-1, 1):
if 0 <= idx_v + sign*dv < self.len[0] and\
0 <= idx_h + sign*dh < self.len[1]:
idxs_neighb.append(self.to_line((idx_v + sign*dv, idx_h + sign*dh)))
return idxs_neighb
def decrement_weights(self, idxs_rect):
"""decrement weight of selected rectangles"""
for idx in idxs_rect:
self.weights[idx] = max(0, self.weights[idx] - 1) # non-neg
def random_pairs(self, n_stone):
"""random adjoining pair of rectangles for each stone"""
rects_stone = []
for _ in range(n_stone):
# ensure pairing when picking the first rectangle
idxs_neighb = []
while True:
idx_first = random.choices(range(self.len[0]*self.len[1]), self.weights)[0]
idxs_neighb = self.neighbors_cardinal(idx_first)
if idxs_neighb != []:
weights_neighb = [self.weights[idx] for idx in idxs_neighb]
if max(weights_neighb) > 0:
break
# pick the second rectangle
idx_second = random.choices(idxs_neighb, weights_neighb)[0]
# adjust the weights
self.weights[idx_first] = 0
self.weights[idx_second] = 0
self.decrement_weights(idxs_neighb)
self.decrement_weights(self.neighbors_cardinal(idx_second))
# merge the pair of rectangles
pair = sorted([idx_first, idx_second])
rects_stone += [Rect(self.rects[pair[0]].nw, self.rects[pair[1]].se)]
return rects_stone
if __debug__:
lens_side_test = [[1] * 5, [1] * 4] # only grid shape matter here
grid_test = Grid_Rect(N_STONE, lens_side_test)
pairs_test = [
[3 , [2, 7]],
[8, [4, 9, 12]],
[14, [10, 13, 15, 18]] ]
for inp, oup in pairs_test:
assert sorted(grid_test.neighbors_cardinal(inp)) == sorted(oup)
###### Display Board
def print_board(n_stone, rects=None, len_row=None, draw_weights=False, stones=None):
### to start with, make a blank Go board
board = []
def width_point(char):
return '{:>2}'.format(char)
# first row shows coordinates in alphabets
board.append([width_point('.')] + [width_point(chr(97 + n)) for n in range(SIZE_BOARD)])
# remaining rows
for n in range(1, SIZE_BOARD + 1):
board.append([width_point(n)] + [width_point('+')]*SIZE_BOARD)
### draw things by substituting symbols
if rects is not None:
## color rectangles with two chars
idx_char = 1
for idx_rct, rct in enumerate(rects):
if idx_char % 2:
char = '#'
else:
char = '%'
for v in range(rct.nw[0], rct.se[0] + 1):
for h in range(rct.nw[1], rct.se[1] + 1):
board[v][h] = width_point(char)
idx_char += 1
if len_row % 2 == 0: # even
if idx_rct != 0 and (idx_rct + 1) % len_row == 0: # end of row
idx_char += 1
if draw_weights is True:
## draw weights inside rectangle in a manner of windmill
for axis in range(2):
axis_other = (axis + 1) % 2
weights = Rect.weights_trapez(rct.nw[axis], rct.se[axis])
len_side = rct.se[axis] - rct.nw[axis] + 1
idx_switch = len_side // 2
if len_side % 2: # odd
idx_switch += 1
for idx, coord_axis in enumerate(range(rct.nw[axis], rct.se[axis] + 1)):
if axis == 0:
coords = [rct.nw[axis_other]] * 2
else:
coords = [rct.se[axis_other]] * 2
coords[axis] = coord_axis
if idx >= idx_switch:
if axis == 0:
coords[axis_other] = rct.se[axis_other]
else:
coords[axis_other] = rct.nw[axis_other]
board[coords[0]][coords[1]] = width_point(weights[idx])
if stones is not None:
## draw stones
for v, h in stones:
board[v][h] = width_point('@')
## print the whole board row by row
for row in board:
print(' '.join(row))
###### Functions for Subdividing the Board into Rectangles
def calc_n_rect(n_stone):
"""calculate number of rows and columns of rectangles needed"""
n_rect = [0] * 2 # [n_row, n_col]
parity = 1
# '2' comes from the plan of combining 2 adjoining small rectangles
# to get a final big rectangle for each stone
while (n_rect[0]) * (n_rect[1]) < n_stone * 2 * SCALE_N_RECT:
if parity % 2:
n_rect[0] += 1
else:
n_rect[1] += 1
parity += 1
return n_rect
if __debug__:
SCALE_N_RECT = 3/2 # fix for test
assert calc_n_rect(5) == [4, 4]
assert calc_n_rect(9) == [6, 5]
class NotEnoughSpace(Exception): pass
def random_lens_side(size_board, n_rect):
"""random side lengths of rectangles along each axis"""
lens_side = [[], []] # [lens_vert, lens_horz]
for axis in range(2): # vert or horz
len_side_min = (SIZE_BOARD - 2*MARGIN_EDGE - SEP_MIN*(n_rect[axis] - 1)) // n_rect[axis]
if len_side_min < 1:
raise NotEnoughSpace
len_remain = END_HIGH - END_LOW + 1
for n_rect_remain in range(n_rect[axis] - 1, 0, -1): # descending loop
len_side_max = len_remain - (len_side_min + SEP_MIN)*n_rect_remain
len_side = random.randint(len_side_min, len_side_max)
lens_side[axis] += [len_side]
len_remain -= len_side + SEP_MIN
lens_side[axis] += [len_remain]
return lens_side
###### Put Everything Together
def main():
try:
rects_small = Grid_Rect(N_STONE, random_lens_side(SIZE_BOARD, calc_n_rect(N_STONE)))
except NotEnoughSpace:
print('Error: not enough space on the board')
print('''Suggestions:
- increase board size
- reduce number of stones
- reduce minimum separation between stones
- reduce minimum separation between stone and edge of board''')
quit()
print('Subdivide the board into small rectangles:\n')
print_board(N_STONE, rects_small.rects, rects_small.len[1])
rects_big = rects_small.random_pairs(N_STONE)
print(
'''
Pick a pair of adjoining small rectangles and
combine them to make one big rectangle for each stone to be placed.
Numbers are weights for placing a stone in the next step and
shown in a manner of a windmill ('v'ertical and 'h'orizontal):
v + h v + + h h v + h h
v + + v + + + + h h + v
h h v h h h + v
''')
print_board(N_STONE, rects_big, len(rects_big), True)
stones = []
for rct in rects_big:
stones += [rct.random_point()]
print('')
print('Place stones:\n')
print_board(N_STONE, stones=stones)
print('\n~ End ~')
if __debug__:
print('Passed all tests!!!')
elif __name__ == '__main__':
main()
###### END OF FILE
One thing I havenāt been able to figure out is, if we have certain number of dominoes and make a grid with the following rules:
rows * columns >= 3 * dominoes
rows - columns = 0 or 1
while keeping the grid as small as possible.
Examples: (dominoes, rows, columns) = (1, 2, 2), (2, 3, 2), (3, 3, 3), (4, 4, 3), (5, 4, 4)
If we are to place dominoes randomly in the grid, can we run out of space for some number of dominoes?
(flailing)
Rearranging the inequality from previous post:
dominoes-that-need-to-be-placed <= (1/3) * rows * columns
I checked some particular configurations; Iām not sure if they actually are the ones with least number of dominoes or, equivalently, the ones with highest number of isolated single cells (āair bubblesā).
When (rows, columns) = (anything, 3n):
dominoes-that-can-be-placed = (columns/3) * rows
= (1/3) * rows * columns
When (rows, columns) = (2m, 3n + 1):
dominoes-that-can-be-placed = rows/2 + ((columns - 1) / 3) * rows
= (1/3) * rows * columns + (1/6) * rows
When (rows, columns) = (4m, 3n + 2):
dominoes-that-can-be-placed = (rows/4) * 3 + ((columns - 2) / 3) * rows
= (1/3) * rows * columns + (1/12) * rows
I translated the rectangle one, as well as making some changes:
// Randomly place stones via subdivision of board into rectangles
// tsc --lib dom,es6 -t es6 random-placements-rect.ts
/** Length from start to end inclusive */
function len(start: number, end: number): number {
return end - start + 1;
}
/** List from start to end inclusive, with step size 1 */
function range(start: number, end: number): number[] {
return Array.from(Array(len(start, end)).keys()).map(val => val + start);
}
/** List of numbers to list of cumulative sums */
function cumul(nums: number[]): number[] {
let res = Array(nums.length);
nums.reduce((acc, val, idx) => res[idx] = acc + val, 0);
return res;
}
/** Random index, using relative weights */
function pickIndex(weights: number[]): number {
console.assert(Math.min(...weights) >= 0, 'negative weight');
console.assert(Math.max(...weights) > 0, 'weights all zero');
const total = weights.reduce((acc, val) => acc + val, 0);
const nRand = Math.floor(Math.random() * total);
return cumul(weights).findIndex(val => { // first one found
return val > nRand;
});
}
/** Random element in list, optionally using relative weights */
function pick(
options: number[],
weights: number[] = Array(options.length).fill(1)
): number {
console.assert(options.length === weights.length, 'unequal length');
return options[pickIndex(weights)];
}
/** Numbers in trapezial shape;
* E.g.: [1, 2, 2, 2, 1]
* At boundary, keep numbers high: [3, 3, 3, 3, 2, 1] */
function trapez(bounds: [number, number], start: number, end: number): number[] {
const base = len(start, end);
if (base === 1) { // special case: would return [0] otherwise
return [1];
}
const mid = Math.floor(base/2);
const ascending = range(1, mid);
let res = [];
if (start === bounds[0]) {
res = res.concat(Array(ascending.length).fill(mid));
} else {
res = res.concat(ascending);
}
if (base % 2) { // only for odd
res.push(mid);
}
if (end === bounds[1]) {
res = res.concat(Array(ascending.length).fill(mid));
} else {
res = res.concat(ascending.reverse());
}
return res;
}
/** Rectangle defined by northwest and southeast corner points inclusive */
class Rect {
corners: [[number, number], [number, number]];
constructor(nw: [number, number] = [0, 0], se: [number, number] = [0, 0]) {
this.corners = [nw, se];
}
/** random point inside rectangle */
randomPoint(bounds: [number, number]): [number, number] {
let point: [number, number] = [this.corners[0][0], this.corners[0][1]];
range(0, 1).forEach(axis => {
const start = this.corners[0][axis];
const end = this.corners[1][axis];
const options = range(1 - 1, len(start, end) - 1);
const weights = trapez(bounds, start, end);
point[axis] += pick(options, weights);
});
return point;
}
}
/** [vert, horz] -> idx */
function fromVhMaker(lenRow: number) {
return function([v, h]: [number, number]): number {
return v*lenRow + h;
}
}
/** idx -> [vert, horz] */
function toVhMaker(lenRow: number) {
return function(idx: number): [number, number] {
const v = Math.floor(idx / lenRow);
const h = idx % lenRow;
return [v, h];
}
}
/** From line segment, get endpoint inclusive */
function seg2end(start: number, seg: number): number {
return start + seg - 1;
}
/** From line segments, get list of both endpoints,
* taking into account separation between segments */
function segs2ends(start: number, segs: number[], sep: number): [number, number][] {
let curr = start;
let res = Array(segs.length);
segs.forEach((seg, idx) => {
res[idx] = [curr, seg2end(curr, seg)];
curr += seg + sep;
});
return res;
}
/** Whether point is within rectangle spanned by [0, 0] and 2 lengths,
* upper bounds excluded*/
function isInGrid(lens: [number, number], point: [number, number]): boolean {
return point[0] >= 0 &&
point[0] < lens[0] &&
point[1] >= 0 &&
point[1] < lens[1];
}
/** In 2-d array, indices of neighbors in cardinal directions */
function neighbors(lens: [number, number], [v, h]: [number, number]): [number, number][] {
let idxsNeighb = [];
[[1, 0], [0, 1]].forEach(dir => {
const dv = dir[0];
const dh = dir[1];
[-1, 1].forEach(sign => {
const candidate: [number, number] = [v + sign*dv, h + sign*dh];
if (isInGrid(lens, candidate)) {
idxsNeighb.push(candidate);
}
});
});
return idxsNeighb;
}
/** Rectangles arranged in a grid, and weight for each */
class GridRects {
private lens: [number, number];
private weights: number[];
readonly rects: Rect[];
private fromVh: ([v, h]: [number, number]) => number;
private toVh: (idx: number) => [number, number];
constructor(
numStone: number,
boundLow: number,
sepMin: number,
lensSideRect: [number[], number[]],
) {
this.lens = [lensSideRect[0].length, lensSideRect[1].length];
this.weights = Array(this.lens[0]*this.lens[1]).fill(1 << numStone);
this.rects = Array.from( {length:this.lens[0]*this.lens[1]}, () => (new Rect()) );
this.fromVh = fromVhMaker(this.lens[1]);
this.toVh = toVhMaker(this.lens[1]);
// set northwest and southeast corner points for each rectangle
const ends = [
segs2ends(boundLow, lensSideRect[0], sepMin),
segs2ends(boundLow, lensSideRect[1], sepMin)
];
this.rects.forEach((rect, idx) => {
const idxVh = this.toVh(idx);
range(0, 1).forEach(axis => {
range(0, 1).forEach(corner => {
rect.corners[corner][axis] = ends[axis][idxVh[axis]][corner];
});
});
});
}
private decrementWeights(idxsRect: number[]) {
idxsRect.forEach(idx => this.weights[idx] >>= 1);
}
/** Random adjoining pair (= domino) of rectangles for each stone */
randomPairs(numStone: number): Rect[] {
let rectsStone = [];
range(1, numStone).forEach(() => {
// ensure pairing when picking first rectangle
let idxFirst;
let idxsNeighb;
let weightsNeighb;
do {
idxFirst = pick(range(0, this.rects.length - 1), this.weights); // pick from all
idxsNeighb = neighbors(this.lens, this.toVh(idxFirst)).map(idx => this.fromVh(idx)).sort((a, b) => a - b);
weightsNeighb = this.weights.filter((_, idx) => {
return idxsNeighb.includes(idx);
});
} while (Math.max(...weightsNeighb) === 0);
// pick the second rectangle
const idxSecond = pick(idxsNeighb, weightsNeighb);
// adjust the weights
this.weights[idxFirst] = 0;
this.decrementWeights(idxsNeighb);
this.weights[idxSecond] = 0;
this.decrementWeights(neighbors(this.lens, this.toVh(idxSecond)).map(idx => this.fromVh(idx)));
// merge the pair of rectangles
const pair = [idxFirst, idxSecond].sort((a, b) => a - b);
rectsStone.push(new Rect(this.rects[pair[0]].corners[0], this.rects[pair[1]].corners[1]));
});
return rectsStone;
}
get lenRow(): number {
return this.lens[1];
}
}
/** Calculate number of rows and columns of rectangles to subdivide into */
function calcNumsRect(numStone: number): [number, number] {
let nums: [number, number] = [0, 0]; // [numRow, numCol]
let parity = 1;
// so far, the factor of 3 seems to allow randomly placing
// pair of rectangles (= dominoes) without running out of space
while (nums[0] * nums[1] < numStone * 3) {
if (parity % 2) {
nums[0] += 1;
} else {
nums[1] += 1;
}
parity += 1;
}
return nums;
}
class NotEnoughSpaceError extends Error {}
/** Along each axis, randomly divide the length of board into segments */
function randomSegs(
sizeBoard: number,
marginEdge: number,
sepMin: number,
bounds: [number, number],
numsRect: [number, number]
): [number[], number[]] {
let segments: [number[], number[]] = [[], []];
range(0, 1).forEach(axis => {
const lenAvailable = sizeBoard - 2*marginEdge - sepMin*(numsRect[axis] - 1);
const lenSideMin = Math.floor(lenAvailable / numsRect[axis]);
if (lenSideMin < 1) {
throw new NotEnoughSpaceError();
}
let lenRemain = len(bounds[0], bounds[1]);
range(1, numsRect[axis] - 1).reverse().forEach(numRectRemain => {
const lenSideMax = lenRemain - (lenSideMin + sepMin)*numRectRemain;
const seg = pick(range(lenSideMin, lenSideMax));
segments[axis].push(seg);
lenRemain -= seg + sepMin;
});
segments[axis].push(lenRemain);
});
return segments;
}
// copied over from: https://github.com/runarberg/random-go-stone-placements/blob/master/random-placements.js
// import { getNextPlayer } from "./random-placements.js";
function getNextPlayer(placements, handicap) {
if (placements.length < handicap) {
return "B";
}
return placements.length % 2 === handicap % 2 ? "B" : "W";
}
/** Assign each stone to either player */
function assignPlayers(stones: [number, number][], handicap: number) {
let placements = [];
stones.forEach(stn => {
const player = getNextPlayer(placements, handicap);
const [col, row] = stn; // directly stn[0], stn[1] in obj literal gave error
placements.push({col, row, player});
});
return placements;
}
function randomPlacementsRect(
numStone: number,
{size,
margins,
handicap,
preventAdjacent = undefined,
separation = 0}
) {
if (preventAdjacent !== undefined) {
if (preventAdjacent) {
separation = 1;
}
}
const bounds: [number, number] = [1 + margins, size - margins];
let segs;
try {
segs = randomSegs(size, margins, separation, bounds, calcNumsRect(numStone));
} catch (err) {
if (err instanceof NotEnoughSpaceError) {
console.error('Error: not enough space on the board for the parameters');
throw err;
}
}
let stones = [];
new GridRects(numStone, bounds[0], separation, segs).randomPairs(numStone).forEach(rct => {
stones.push(rct.randomPoint(bounds));
});
return assignPlayers(stones, handicap);
}
I didnāt guard against infinite loop that can happen if the domino conjecture turns out to be false, but I thought itās unlikely to be false and the consequence would just be the browser freezing (?).
These are for debugging and showing intermediate states:
// Print results of random-placements-rect.ts
// tsc --lib dom,es6 -t es6 random-placements-rect.ts random-placements-rect-print.ts
document.write('open Web Console');
const instruction = `
Copy-paste and run:
var config = {
stones: 2, // number of stones each
size: 19, // board size
handicap: 2,
margins: 2, // minimum separation to edge of board
separation: 1, // minimum separation between stones
};
randomPlacementsRectPrintParts(config.handicap + config.stones*2, config) // with intermediate states
randomPlacementsRectPrint(config.handicap + config.stones*2, config) // only final stones`
console.log(instruction);
//////////////////////////////////////////////////////////////////
enum Char {
TopLeft = '.',
Point = '+',
Stone1 = '@',
Stone2 = '$',
Color1 = '#',
Color2 = '%',
}
function whichColor(idx: number): Char {
switch (idx % 2) {
case 0:
return Char.Color1;
case 1:
return Char.Color2;
}
}
function whichStone(ident: string): Char {
switch (ident) {
case 'B':
return Char.Stone1;
case 'W':
return Char.Stone2;
}
}
/** Pad char when drawing on the board */
function makeDrawChar(width: number) {
return function(char: any): string {
return char.toString().padStart(width, '\xa0');
}
}
/** Coordinates and weight pairs on the "blades" of a windmill:
*
* v + h v + + h h v + h h
* v + + v + + + + h h + v
* h h v h h h + v
*
*/
function windmillWeights(bounds: [number, number], rect: Rect): [[number, number], number][] {
let res: [[number, number], number][] = [];
range(0, 1).forEach(axis => {
const axisOther = (axis + 1) % 2;
const start = rect.corners[0][axis];
const end = rect.corners[1][axis];
const weights = trapez(bounds, start, end);
const lenSide = len(start, end);
const idxSwitch = (lenSide % 2)? Math.floor(lenSide / 2) + 1: Math.floor(lenSide/2);
range(start, end).forEach((coord, idx) => { // along the side
let point: [number, number] = [0, 0];
switch (axis) {
case 0:
point[axisOther] = rect.corners[0][axisOther]; break;
case 1:
point[axisOther] = rect.corners[1][axisOther]; break;
}
point[axis] = coord;
if (idx >= idxSwitch) { // jump to the other side
switch (axis) {
case 0:
point[axisOther] = rect.corners[1][axisOther]; break;
case 1:
point[axisOther] = rect.corners[0][axisOther]; break;
}
}
res.push([point, weights[idx]]);
});
});
return res;
}
class Board {
private size: number;
private board: string[];
private drawChar0thCol: (char: any) => string;
private drawChar: (char: any) => string;
private fromVh: ([v, h]: [number, number]) => number;
constructor(sizeBoard: number, widthPoint: number = 1) {
this.size = sizeBoard;
this.board = Array((this.size + 1)**2);
this.drawChar0thCol = makeDrawChar(this.size.toString().length);
this.drawChar = makeDrawChar(widthPoint);
this.fromVh = fromVhMaker(this.size + 1);
// coordinate labels
this.board[this.fromVh([0, 0])] = this.drawChar0thCol(Char.TopLeft);
range(1, this.size).forEach(idx => {
this.board[this.fromVh([0, idx])] = this.drawChar(String.fromCharCode(96 + idx)); // in alphabets
this.board[this.fromVh([idx, 0])] = this.drawChar0thCol(idx); // in numbers
});
}
private blank(): void {
range(1, this.size).forEach(row => {
this.board.fill(Char.Point, this.fromVh([row, 1]), this.fromVh([row, this.size]) + 1);
});
}
/** Draw rectangles, optionally with weights in a manner of windmill */
drawRects(
rects: Rect[],
lenRow: number,
withWeights: boolean = false,
bounds: [number, number] = undefined
): void {
this.blank();
let idxColor = 0;
rects.forEach((rct, idxRct) => {
const color = whichColor(idxColor);
range(rct.corners[0][0], rct.corners[1][0]).forEach(v => {
range(rct.corners[0][1], rct.corners[1][1]).forEach(h => {
this.board[this.fromVh([v, h])] = this.drawChar(color);
});
});
idxColor += 1; // switch color
if (lenRow % 2 === 0) { // even
if (idxRct != 0 && (idxRct + 1) % lenRow === 0) { // end of row
idxColor += 1; // switch color again
}
}
if (withWeights) {
windmillWeights(bounds, rct).forEach(pair => {
const [point, weight] = pair;
this.board[this.fromVh(point)] = this.drawChar(weight);
});
}
});
}
drawStones(placements): void {
this.blank();
placements.forEach(triple => {
const {col, row, player} = triple;
this.board[this.fromVh([col, row])] = this.drawChar(whichStone(player));
});
}
print(): void {
range(0, this.size).forEach(row => {
const start = this.fromVh([row, 0]);
const end = this.fromVh([row, this.size]);
const rowStr = this.board.slice(start, end + 1).join('\xa0');
document.write('<code>' + rowStr + '</code><br>');
});
}
}
/** Maximum weight for particular subdivision */
function calcWeightMax(segs: [number[], number[]]): number {
let maxes: [number, number] = [0, 0];
range(0, 1).forEach(axis => {
maxes[axis] = Math.max(...segs[axis]);
});
return Math.floor(Math.max(...maxes) / 2);
}
function randomPlacementsRectPrintParts(
numStone: number,
{size,
margins,
handicap,
separation}
): void {
document.body.textContent = '';
const bounds: [number, number] = [1 + margins, size - margins];
let segs;
try {
segs = randomSegs(size, margins, separation, bounds, calcNumsRect(numStone));
} catch (err) {
if (err instanceof NotEnoughSpaceError) {
console.error('Error: not enough space on the board for the parameters');
throw err;
}
}
let board = new Board(size, calcWeightMax(segs).toString().length);
document.write('<br>Subdivide the board into small rectangles:<br><br>');
const gridRectsSmall = new GridRects(numStone, bounds[0], separation, segs);
board.drawRects(gridRectsSmall.rects, gridRectsSmall.lenRow);
board.print();
document.write(`
<br>
Pick a pair of adjoining small rectangles and combine them to make one big rectangle for each stone to be placed.<br>
<br>
Picking a rectangle makes its neighbors half as likely to be picked.<br>
<br>
In the following diagram, numbers are weights for placing a stone in the next step and shown in a manner of a windmill ('v'ertical and 'h'orizontal):<br>
<br>
<code>
\xa0\xa0 v + h \xa0\xa0\xa0 v + + h h \xa0\xa0\xa0 v + h h <br>
\xa0\xa0 v + + \xa0\xa0\xa0 v + + + + \xa0\xa0\xa0 h h + v<br>
\xa0\xa0 h h v \xa0\xa0\xa0 h h h + v<br><br>
</code>
`);
const rectsBig = gridRectsSmall.randomPairs(numStone);
board.drawRects(rectsBig, rectsBig.length, true, bounds);
board.print();
document.write('<br>Place stones:<br><br>');
let stones = [];
rectsBig.forEach(rct => {
stones.push(rct.randomPoint(bounds));
});
const placements = assignPlayers(stones, handicap);
board.drawStones(placements);
board.print();
}
function randomPlacementsRectPrint(
numStone: number,
{size,
margins,
handicap,
separation}
): void {
document.body.textContent = '';
let board = new Board(size);
board.drawStones(randomPlacementsRect(numStone, {size, margins, handicap, separation}));
board.print();
}
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Random placements via subdivision into rectangles</title>
</head>
<body>
<script src="random-placements-rect.js"></script>
<script src="random-placements-rect-print.js"></script>
</body>
</html>
Subdivide the board into small rectangles:
. 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 + + # # # # # # + % % + # # + % % + # # + % % + # # + % % + +
30 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
31 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Pick a pair of adjoining small rectangles and combine them to make
one big rectangle for each stone to be placed.
Picking a rectangle makes its neighbors half as likely to be picked.
In the following diagram, numbers are weights for placing a stone
in the next step and shown in a manner of a windmill
('v'ertical and 'h'orizontal):
v + h v + + h h v + h h
v + + v + + + + h h + v
h h v h h h + v
. 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 + + 1 # # # # 4 3 2 1 + + + + 3 1 + + + + + + + 1 # # 2 2 + +
4 + + 1 # # # # # # # # + + + + 3 % + + + + + + + 1 # # # # + +
5 + + 4 4 4 4 4 # # # 1 + + + + 3 % + + + + + + + 1 2 2 # 1 + +
6 + + + + + + + + + + + + + + + % 3 + + + + + + + + + + + + + +
7 + + + + + + + + + + + + 1 1 + % 2 + + + + 1 1 + + + + + + + +
8 + + + + + + + + + + + + 2 # + 1 1 + + + + 2 # + + + + + + + +
9 + + + + + + + + + + + + 2 # + + + + + + + 2 # + + + + + + + +
10 + + 1 % % 3 2 1 + + + + # 2 + 1 1 + + + + # 2 + 1 % % 2 2 + +
11 + + 2 % % % % % + + + + 1 1 + 2 # + + + + 1 1 + 1 2 2 % 1 + +
12 + + 2 % % % % % + + + + + + + 2 # + + + + + + + + + + + + + +
13 + + % % % % % 2 + + + + + + + # 2 + + + + + + + + + + + + + +
14 + + 3 3 3 % % 1 + + + + + + + 1 1 + + + + + + + + + + + + + +
15 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
16 + + + + + + + + + 1 % % 2 1 + 1 # # 2 1 + + + + + + + 1 1 + +
17 + + + + + + + + + 1 2 2 % 1 + 1 2 2 # 1 + + + + + + + 2 # + +
18 + + + + + + + + + + + + + + + + + + + + + + + + + + + 2 # + +
19 + + 1 # # 3 2 1 + + + + + + + + + + + + + 1 # # 2 1 + # 2 + +
20 + + 2 # # # # # + + + + + + + + + + + + + 1 2 2 # 1 + 1 1 + +
21 + + 2 # # # # # + + + + + + + + + + + + + + + + + + + + + + +
22 + + # # # # # 2 + 1 1 + + + + + + + 1 1 + 1 % % 2 1 + 1 1 + +
23 + + 3 3 3 # # 1 + 2 % + + + + + + + 2 # + 1 2 2 % 1 + 2 # + +
24 + + + + + + + + + 2 % + + + + + + + 2 # + + + + + + + 2 # + +
25 + + 1 % % 3 2 1 + % 2 + + + + 1 1 + # 2 + + + + 1 1 + # 2 + +
26 + + 2 % % % % % + 1 1 + + + + 2 % + 1 1 + + + + 2 % + 1 1 + +
27 + + 2 % % % % % + + + + + + + 2 % + + + + + + + 2 % + + + + +
28 + + % % % % % 2 + 1 % % 2 1 + % 2 + 1 % % 2 1 + % 2 + + + + +
29 + + 3 3 3 % % 2 + 1 2 2 % 1 + 1 2 + 1 2 2 % 1 + 1 2 + + + + +
30 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
31 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Place 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 + + + + $ + + + + + + + $ + + + + + + + + + + + + + + + + + +
30 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
31 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Continues in github repository:
If you donāt know how to use github (I didnāt), I made a minimal tutorial:
For handicap games, I wonder if starting with (n - 1) stones and blackās first move would make it any better.
There are a lot of GitHub and git tutorials that can be found online by just Googling āgit tutorialā or āgithub tutorialā.
You should know that creating and merging in branches is an optional feature, which is nice for tracking changes in parallel to other changes, however it is not necessary to do that for all new commits, and probably just a waste of time if you are anyways going to immediately merge the branch back in and delete it. You can instead just directly commit to the main/default branch.
When I tried to learn it the available tutorials felt too thorough and overwhelming for me, so I made the minimal one.
I managed to not learn much more so am not sure but if Iām working on someone elseās repository, isnāt it safer to make a branch in case the other person happens to make a change?
I guess I should qualify that somewhere?
When working with others, you may want to use branches, and might even be required to.
However, if you are just forking off someone elseās code and not pushing changes back to them, nothing prevents you from just continuing on the main branch in your local copy of the repo, if thatās more convenient. Even if the original source makes changes that you wish to pull into your repo, you can handle the merge directly into your local main.
Thanks for the clarification.
I should amend the tutorial with an explanation somewhere, but havenāt figured out where to put it to minimize mental friction for a learner. Possibly even splitting the current one into smaller pieces before doing that.
For those returning to this thread, there have been some really nice contributions made by sabu36. Regrettably I havenāt found time to publish them yet. But hopefully I will find time in October.
I updated the tutorial, restructuring them into 2 paths for single and double branch cases.
The method in the double branch case works in the minimal situation in the tutorial, but I wonder if itās an acceptable general strategy for a beginner.
I sent a request to a bot a few days ago but havenāt received a response. (I assume itās queued.)
So Iām seeking 3 human (?) opponents to try out this idea:
Combined with this idea:
The game can last a long time so I wonder if thereās a way to end it if a player got busy or lost interest etc. Iād thought itās called ęć”ęćļ¼ćć”ććļ¼ in Japanese but found (zero citations) that the word can mean either āadjournmentā (only one mentioned in Senseiās) or premature end of a game. Another evidence is the game record of a medieval player ā35å28ę3ęē¢4ęć”ęćā.
Have you only tried the first one? These bots are run by different users, some of them are relaying moves and perhaps donāt feel like playing.
Yesterday, I sent chat messages to bot maintainers if theyād accept such challenges instead of directly requesting a game because I realized I donāt know how many games they each can have in parallel. I havenāt received replies yet.
Whatās everyoneās opinion on the following method for trying to make even games fairer? I think itās potentially more intuitive than estimating a number in komi bidding.
(github issue; itās probably independent of current pull request although I donāt exactly know how it can be implemented.)
As for the current version, Iād like to try various settingsāscratch my last postāso feel free to hit me up with Live or Correspondence, Handied or Even game for experiments.