[computer-go] Maximum number of strings

[Hiroshi Yamashita]

> This is a practically important figure. I have severall fixed 
> data-structures which depend on the maximum number of strings. I put it to 
> 300, because I was not sure. So I can save a few entries in the future.
> There is of course the question how sure this number is. Is it some sort of 
> proove or just an example the author has found?

This is an sample of maximum.
He shows there is at least one checker-board-design position in all
 N strings positions.

OXOXOXO
XOXOXOX   checker-board-design position
OXOXOXO
XOXOXOX   take some stones from this position.
OXOXOXO

And he gives forbidden pattern.

 010    110    100    forbidden pattern
 111    100    110    
 010    000    100    "1" is stone. "0" is empty.
center corner  edge

Then he used GLPK(GNU Linear Programming Kit) and got the result up to
 15x15.

MSP( 2) = 2
MSP( 3) = 6
MSP( 4) = 12
MSP( 5) = 18
MSP( 6) = 26
MSP( 7) = 36
MSP( 8) = 49
MSP( 9) = 61
MSP(10) = 76
MSP(11) = 92
MSP(12) = 109
MSP(13) = 129
MSP(14) = 149
MSP(15) = 172
...
MSP(19) = 277

MSP(19) means "Max Strings Problem in 19x19".

Author could not solve 19x19, just showed 277 <= MSP(19) <= 281.
But Ryuhei Miyashiro reported he got the result MSP(19) was 277 by
 using CPLEX(commercial solver) for 40days calculations.

Hiroshi Yamashita