OGS Joseki Dictionary update 2019-06-07

OGS Development Joseki Dictionary
21

ln(100000)/ln(2)+1=16.6+1=17.6

So the variations had a length of 17-18. The first two stones have only 1 continuation (A1 -> B1 -> C1 -> D1 and C2)

Any point on a goban can either be white, black or empty. Therefore there are at most 3^(19^2)≈1.7x10^174 individual board positions.

For the number of possible games: For Paper and Pencil Go (you aren’t allowed to play on to of any captured stones) the number of possible games lasting 240 moves maximum is about 361!/(361-240)!≈1.8x10^567.
For the first 19 moves there are already 361!/(361-19)!≈2.4x10^48 allowed variations.

You can divide the numbers by 8 of you want to remove rotated and mirrored positions/variations :wink:

For comparison there are about 10^82 atoms in the visible/known universe.

22

Assuming you only start with A1 and all variations instantly go to depth 20, we can solve this easily.

We get a 19x8 matrix, but we only need 112 cells. We notice that the number of paths to each intersection is the sum of all paths to the left and below each cell (because we can only go up or right).
R code:

resMat=matrix(rep(0,152),ncol=8)
resMat[,1]=1
resMat[19,]=1

> for (i in 18:1){
+     for (j in 2:8){
+         resMat[i,j]=resMat[i,j-1]+resMat[i+1,j]
+     }
+ }
> resMat
      [,1] [,2] [,3] [,4] [,5]  [,6]   [,7]   [,8]
 [1,]    1   19  190 1330 7315 33649 134596 480700
 [2,]    1   18  171 1140 5985 26334 100947 346104
 [3,]    1   17  153  969 4845 20349  74613 245157
 [4,]    1   16  136  816 3876 15504  54264 170544
 [5,]    1   15  120  680 3060 11628  38760 116280
 [6,]    1   14  105  560 2380  8568  27132  77520
 [7,]    1   13   91  455 1820  6188  18564  50388
 [8,]    1   12   78  364 1365  4368  12376  31824
 [9,]    1   11   66  286 1001  3003   8008  19448
[10,]    1   10   55  220  715  2002   5005  11440
[11,]    1    9   45  165  495  1287   3003   6435
[12,]    1    8   36  120  330   792   1716   3432
[13,]    1    7   28   84  210   462    924   1716
[14,]    1    6   21   56  126   252    462    792
[15,]    1    5   15   35   70   126    210    330
[16,]    1    4   10   20   35    56     84    120
[17,]    1    3    6   10   15    21     28     36
[18,]    1    2    3    4    5     6      7      8
[19,]    1    1    1    1    1     1      1      1

Again, if all we ever do is go right and up, then each intersection can only be part of a sequence whose (endpoint’s) column+row sum is 21. Since the horizontals never exceed 8 and the verticals never exceed 19, we only have seven endpoints (B19, C18, D17, E16, F15, G14, H13) for our starting point A1.

If we add up all paths for all endpoints, we get 19+171+969+3876+11628+27132+50388 = 94183.

Okay, so we need more than a single starting point (A1) but it’s pretty close. :smiley:

23

You crazy math dudes! Well I did ask!!

For me, what it did was make the number more “visceral”.

I mean - everyone knows that the total positions is a monstrous number, as quoted by flovo.

But when you start to lay out positions, and see how much of a tiny space your efforts consume … well I found it really brought it home.

1 Like
24

Hm, after a good night of sleep I’ll add the breadth-first approach as well.

The number of positions p is the sum of all paths of length n (the left-to-right downward diagonal), so for the starting point A1, we get the following distribution n(p):
1(1), 2(2), 3(4), 4(8), 5(16), 6(32), 7(64), 8(128), 9(255), 10(502), 11(968), 12(1816), 13(3302), 14(5812), 15(9908), 16(16384), 17(26333), 18(41226), 19(63004), 20(94183)

The cumulative sums are

1 3 7 15 31 63 127 255 510 1012 1980 3796 7098 12910 22818 39202 65535 106761 169765 263948

So thanks to flovo for teaching us that one neat trick. If you go breadth first, you’ll indeed have reached 100k positions before you even get to move 18 in some sequences.

1 Like
25

This seems more like what I had imagined - though why only using the diagonal as starting points? Doesn’t every NEW point visited start an additional tree?

I realise now my 2^depth doesnt work, and that the number of starting points after n steps of the original tree is more complicated than just odd or counting numbers… so basically everything I said was wrong XD

26

Well, as I said, Eugene’s description is still not terribly clear to me. This was my interpretation. I’m not using the diagonal as starting points (?), I’m only using A1 as starting point. The diagonal sums of the resulting number-of-paths-matrix just tells us the total number of positions for all paths of length n (because of the up-and-right rule).

If you first start all possible 1-trees (152), then do all possible 2-trees (152-(1+7+18)=126) etc, the whole shebang will change, because each starting point has its own number of possible paths of length n and I’m too lazy to do that calculation.

If you strictly do
A1 (+B1, +A2) —> B1 (+C1, +B2) —> C1 (+D1, +C2) —> … as Eugene indicated, that isn’t breadth-first. It’s a weird way of doing depth-first. It obviously changes the length of each position (throwing off our 17.x calculation) and the number of operations to get there. I also wouldn’t know how to calculate it, other than to actually run the algorithm.

Not sure how it would affect the total number of positions.

If we first create all 1-trees, then all 2-trees etc. (i.e. breadth-first for all possible starting points):

Number of positions p per sequence length n, so n(p):

1 (19*8*1 = 152)
2 (18*7*2 + 18*1 + 7*1 = 277)
3 (17*6*4 + 6*3 + 6 + 17*3 + 17 = 500)
4 (16*5*8 + 5*7 + 5*4 + 5 + 16*7 + 16*5 +16 = 908) cS=1837
...

and so on and so forth… if we assume that the factor stays about the same (1.8), we should get
5 (~1634), 6 (~2941), 7(~5295), 8(~9531), 9(~17157), 10(~30883), 11(~55590), so after creating all possible 10-move sequences we’ll be at about ~62000 positions and we won’t have to create all 11-move sequences to reach 100k positions.

27

LOL I was conscious as I was writing that I was approximating in the interests of conveying the idea without getting bogged in details.

It is basically depth first. Somewhat pseudo code:

ExtendSequencesFrom("root", A, 1)

ExtendSequencesFrom(parent,  x , y) {
    // place a stone of opposite colour to parent at (x,y) as the next stone in parent's sequence
   next_node = AddStoneFrom(parent, x, y) 
   
   if (stonecount < target_stone_count) {
     if (x < 'H') {
       AddStoneFrom(next_node, x+1, y)
    }
 
    if (stonecount < target_stone_count) {
     if ( y< 19) {
       AddStoneFrom(next_node, x, y + 1)
    }
}

I’m pretty sure the first thing this does is write a 26-long sequence across the bottom then up the H column :slight_smile:

It never gets to the second ‘if’ statement in the first time it’s called - the sequence A1.A2 is not started, 100,000 nodes are written well before that.

EuG

1 Like