# I Place pieces on a chessboard randomly until 2 are adjacent

Tags:
1. Mar 18, 2016

### fluidistic

I've written a program that simulates placing pieces randomly on an nxn chessboard, one by one until 2 are adjacent. When 2 are adjacent I stop, and I report the number of pieces it took.
I've plotted a histogram of the number of pieces it took vs number of occurences just to see what kind of distribution it is. To my surprise, with big boards (such as 19x19 like in the game of go), I've noticed a very strange behavior of the histogram/distribution. There is a very slight decrease in probability to stop at 3 pieces compared than to stop at 2 pieces, something that does not happen for smaller boards. I've told this behavior to a friend who studies maths and he didn't trust my results, saying my program is faulty.
So I would like to calculate the exact probability to stop at step 2 and at step 3 for a 19x19 chessboard. I consider that 2 pieces are adjacent when when they are either at the right/left or bottom/top of each other; in diagonal they aren't adjacent.

I'd like to have some guidance on how to proceed, I don't really know where to start.

2. Mar 18, 2016

### PeroK

If I understand correctly, the probability of stopping at 2 should be roughly 4/360 and stopping at 3 roughly twice this, about 8/359 times 356/360.

I can't see how it could be more likely to stop at 2 than 3.

3. Mar 18, 2016

### PeroK

Ps from your histogram, what are the relevant probabilities? They both look about 3%.

4. Mar 18, 2016

### Merlin3189

Not an answer to your question (so not posted), but I think I agree with whoever said it doesn't look right.

How often will just two stones be adjacent?
For most squares ther are 4 adjacent squares.
There are 364 squares on the board, so after you place the first stone, there are 364 -1 -4 = 359 squares where you can put the second stone and not be adjacent.
So you expect to get two adjacent two stones adjacent less than 4/359 times. (less than, because for some first squares you have less than 4 adjacent squares.)
Call it 1/90. But you appear to have about 1/30 results for two stones. (Just a rough guess from your graph, as you don't supply raw data. Perhaps a cumulative frequency chart might help.)
For a large number of trials, 1/30 is very different from 1/90.

I haven't got time to do it at the moment, but the exact calculation doesn't look difficult for just two stones, though I can only think, so far, of approximations for higher numbers of stones (unless you do it by brute force on a computer ). My strategy would be to classify squares as having 2,3 or 4 adjacent possible squares, then multiply the fraction of each type by the probability of the next stone being adjacent and sum the results.
So for two, there are 4 squares with 2 adjacent, 68 with 3 adjacent and 292 with 4 adjacent,
then $\frac{4}{364}\times \frac{2}{363} + \frac{68}{364}\times \frac{3}{363} + \frac{292}{364}\times \frac{4}{363}$ = $\frac{4 x 2 + 68 x 3 + 292 x 4}{364 x 363}$ = $\frac{1380}{132132} = 0.0104$

5. Mar 18, 2016

### fluidistic

I'm very sorry guys but it looks like I should have never use a histogram (apparently that's used only for continuous data), but I should have used a barplot. (Someone on IRC just told me that). By doing so, I got a totally different graph and there's no such anomaly:

By the way the occurrences are 10520 and 20891 for 2 and 3 pieces respectively. So problem solved thanks to you guys!
P.S.:If you know the kind of distribution it is (similar to Poisson?), please feel free to say it.

6. Mar 18, 2016

### HallsofIvy

Staff Emeritus
7. Mar 18, 2016

### FactChecker

It does look like a Poisson distribution, but I don't see any theoretical reason that it should be Poisson. I wonder if a Chi-squared goodness of fit test would say it was Poisson. Just curious.

8. Mar 19, 2016

### ChrisVer

Well, why not a Poisson?
I mean are the different tries dependent to their previous ones?

9. Mar 19, 2016

### FactChecker

I think the answer is yes. The probabilities change as time goes on (more pieces put on the board).

10. Mar 19, 2016

### ChrisVer

oh my god, I shoudn't have tried to argue at 5am...
However the diagram is nice...
the 2x2 diagram has pretty much calculable probabilities to fail per turn:
turn 1: 0, you can position your pawn anywhere on the 4 blocks
turn 2: 0.666, you can posiition your pawn anywhere on the 4-1=3 blocs, but 2 of them are marked as "death"... (2/3) to fail, (1/3) to survive
turn 3: 0.333, you had the (1/3) chance to survive from turn 2, and now you have 4-2=2 blocks all of them marked as death. (also using possibilities are complementary)

Can you work the same for a 3x3 diagram?
turn 1: well, the probability to fail is 0, but here things can get "nasty"...because if turn 1 was on an edge (corner or side respectively), there are 2 or 3 blocks respectively marked as "death". that's why I assign to "turn 1" 3 "states", with equal probability 1/N^2= 1/9 (I assume a uniform random distribution) but different multiplicity... the one is the corner (multiplicity = 4), the other is the side (multiplicity=4) and the other is the center (multiplicity=1).
then you expand each of those states to a tree.
I made the trees for this N=3 diagram.

Of course the problem is that the branching of the diagrams is not constant: that is the result of having corners, sides and centers .
At each turn the possibility goes as $\frac{\text{multiplicity}}{N^2 - \#\text{turn}}$
To obtain the probability at turn k you have to start from the bottom and move to the top ( independent events conditional probability).
So for example in order to reach [starting from the center] to the maximum depth, the probability is:
$P(k=6)= 1 \Big|_{\text{turn~6}} \times \frac{1}{5}\Big|_{\text{turn~5}} \times \frac{2}{6}\Big|_{\text{turn~4}} \times \frac{3}{7} \Big|_{\text{turn~3}} \times \frac{4}{8}\Big|_{\text{turn~2}}$
if not starting from the center (general to get to depth 6):
$P(k=6)= 1 \Big|_{\text{turn~6}} \times \frac{1}{5}\Big|_{\text{turn~5}} \times \frac{2}{6}\Big|_{\text{turn~4}} \times \frac{3}{7} \Big|_{\text{turn~3}} \times \frac{4}{8}\Big|_{\text{turn~2}} \times \frac{1}{9}\Big|_{\text{turn~1}}+ \text{do~same~for~4~that~can~reach~depth~6~of~the~2nd~tree}+\text{same~for~3rd~tree}$
But the 3rd tree seems not to contribute.
Another thing you can see is that I got some fixed depth at which the game is over. I suppose it's where your distribution for large turns has to fall to zero.

So things may get worse for larger N, but I'm pretty sure it would be fun to spend some time seeing what happens... eg finding the #turn for the maximum probability vs N?

#### Attached Files:

• ###### CNGS.jpg
File size:
15.1 KB
Views:
53
Last edited: Mar 19, 2016
11. Mar 21, 2016

### fluidistic

My friend calculated the probability to stop at piece 2 and 3 for an nxn sized board (n>6). : P(stop at 2) = 4/(n^2 + n) and P(stop at 3) = (8n^4 - 8n^3 - 52n^2 + 140n - 116)/(n^2 (n^2 - 1) (n^2 - 2)). I think he had to sum up 64 terms or so to get the probability to stop at piece 3. I'm not 100% sure.
He said that for very large boards, stopping at piece 3 is twice more likely than stopping at piece 2 (it tends to the ratio 2:1 for n tends to infinity), because most squares are "middle board squares" (i.e. not corners nor sides).

12. Mar 21, 2016

### ChrisVer

For an NxN board I would say that the pobability to stop at round 2 is:
$P(\text{die~at~2}) = P_{\text{survive ~1}} \times P_{\text{hit~next~to~other~at~turn~2}}$
If you want to forget about the edges [so take $N$ very large, so that $N^2 -(4N-4) \approx N^2$] you have that each piece covers 5 boxes [1 that it occupies and 4 over a cross around it].
So the probability to survive turn 1 is $P_{\text{survive ~1}}=1$ (all board was clear).
And then it would be $P_{\text{hit~next~to~other~at~turn~2}}= \frac{4}{N^2-1}$...
Because you had $N^2 -1$ boxes left for that round and $4$ cases that achieved the end result.
Again because $N^2 \gg 1$ you obtain:
$P_{\text{die~at~2}} \approx \frac{4}{ N^2}$
Similarily to die at turn 3:
$P_{\text{die~at~3}}= P_{\text{survive~2}}P_{\text{hit~next~to~other~at~turn~3}} = (1-P_{\text{die~at~2}}) \frac{8}{N^2-2}$
$P_{\text{die~at~3}} \approx (1 - \frac{4}{N^2} ) \frac{8}{N^2} = 2 \frac{4}{N^2} - \frac{32}{N^4} = 2 P_{\text{die~at~2}} - \mathcal{O}(N^{-4})$
So I would agree that with these assumptions you can reach that it reaches a ration 1:2.
In each probability I might be off by a factor of $1/N^2$ from your friend's result because I didn't apply it to the first round; of course it is taken from both 2 and 3, and so their ratio is not influenced by it.

I tried to reproduce your algorithm to make my own checks, but there is something wrong with my checks on the board occupancy. So I can't make those tests, while you can.

Last edited: Mar 21, 2016
13. Mar 21, 2016

### fluidistic

Here's my code:
Code (Python):

import random
import numpy as np

# Size of the board
n = 19
# Number of trials
trials = 100
# Initialize the board list of lists to 0. 0 means no stone, 1 means stone.
# Note that board[0][0] is the first element and board[20][20] is the last one
# , for when n=19. That's because I define the board
# as n+2 x n+2 for the edges...
board = [[0]*(n+2) for i in range(n+2)]
counter = 0
# Generate random coordinates inside of the 19x19 board
x_coordinates, y_coordinates = random.randint(1, n), random.randint(1, n)

# Now define a boolean function that I'll use as a condition in a while loop

def check_if_stones(x_coordinates, y_coordinates):
if (board[x_coordinates-1][y_coordinates] == 1
or board[x_coordinates][y_coordinates-1] == 1
or board[x_coordinates+1][y_coordinates] == 1
or board[x_coordinates][y_coordinates+1] == 1):
return False
else:
return True

trial_list = []
for j in range(trials):
counter = 0
board = [[0]*(n+2) for i in range(n+2)]
while check_if_stones(x_coordinates, y_coordinates):
if board[x_coordinates][y_coordinates] == 0:
# Now replace a random element by 1
board[x_coordinates][y_coordinates] = 1
counter += 1
x_coordinates, y_coordinates = random.randint(1, n), random.randint(1, n)
x_coordinates, y_coordinates = random.randint(1, n), random.randint(1, n)
# Update the counter when the boolean function returns false. Do this outside of the while loop.
counter += 1
trial_list.append(counter)
x_coordinates, y_coordinates = random.randint(1, n), random.randint(1, n)
print('The average number of stones is', np.mean(trial_list))
# print(trial_list)
# print the list into a .txt file
with open('go_data.txt','w') as f:
f.write(str(trial_list))
I'm not a programmer so this is extremely likely to be a very ugly code but I think it does the job.
Edit: The indentation isn't working well when I paste it here... and that matters a lot to python!

14. Mar 21, 2016

### ChrisVer

Well, to me it's interesting that yours is in python too...maybe it can help debug my code...
Mine is this one... for some reason my checks don't work right

Code (Python):

from numpy import zeros
from pylab import show, plot, legend, xlabel, ylabel,text,xlim
import random

#Global variables ,  N variable to create (N-2) x (N-2) board
#                             SUM variable used for normalization

N=5
SUM=0.0

def check(board,x1,y1,x2,y2):
'''
checks if positions 1 and position 2 on a board are both filled
Returns True when both positions are occupied
Else returns False
'''

return board[x1,y1]==1 and board[x2,y2]==1

def end_game(board,pos):
'''
Method that takes a board and a new position pos
Checks adjacent squares to pos and ends the game if necessary
Returns True when the Filling must stop
Returns False when the Filling should continue
'''

global nTurns
x,y = pos
z= check(board,x,y,x+1,y) or check(board,x,y,x-1,y) or check(board,x,y,x,y+1) or check(board,x,y,x,y-1)

#debugging check inside this if, for N=3 shouldn't get anything
if nTurns>=6 and z==False:
print BOARD
print "x,y=",x,y
print "x,x+1",check(board,x,y,x+1,y)
print "x,x-1",check(board,x,y,x-1,y)
print "y,y+1",check(board,x,y,x,y+1)
print "y,y-1",check(board,x,y,x,y-1)
print z

return z

def FillBoard(board):
'''
Main Fill method here, takes the Board and
generates and fills randomly a non-occupied position
'''

global BOARD,nTurns

#Generate position
xt = random.randrange(1,N-1)
yt = random.randrange(1,N-1)
position=xt,yt

#If occupied retry generating, else fill and change Turn
if BOARD[xt,yt]==0:
BOARD[xt,yt]=1
nTurns+=1
else:
FillBoard(BOARD)

#Recursively move to the next turn until the last position is an end
if not end_game(BOARD,position):
FillBoard(BOARD)

def normalize(List):
'''
Method that takes a list and normalizes it
Returns a list of normalized entries
'''

m=List
global SUM
for element in m:
SUM+=elelement

for i in range(len(m)):
m[i]= 1.*m[i]/sume

return m

'''
MAIN STARTS HERE
'''

L_turns            = []

#Generate 10000 games
for i in range(10000):
#build an empty board and set the turns to 0 per game started
BOARD=zeros((N,N),int)
nTurns=0

#Start filling the board
FillBoard(BOARD)

#At the end of any game put the nTurns to end in list
L_turns.append(n)

#Create the plotting variables
cL_turns          =list(L_turns)
occurancies    = []
x                      = []

for nTurnsEnd in set(L_turns): #used set because I don't want to count doubles
x.append(nTurnsEnd)
occurancies.append(cL_turns.count(nTurnsEnd))
L_turns.remove(nTurnsEnd)

occurancies= normalize(occurancies)

#Plotting
plot(x,occurancies, 'r*', label=r' N= %g, total events: %g'%(N,SUM))
xlabel('number of turns')
ylabel('normalized occurs')
xlim(0,8)
legend(loc='upper right')
show()

Last edited: Mar 21, 2016