I have independently verified the MSP (maximum number of living strings on a board) results for board sizes up to 16 that Youhei Yano created and that Hiroshi Yamashita reported on in this mail group about a month ago.
Youhei Yano's original results are at: http://www.yss-aya.com/msp1.jpg http://www.yss-aya.com/msp2.jpg They contain 2 typos, though the diagrams are all correct. My results show answers up to board size 18 and are listed at the bottom of this email. My results include maxes and examples for board sizes 17 and 18 which, to my knowledge, were previously unknown. --- My program can also solve board size 19, but not on my computer (a 1.66 gHz Intel Duo with 1 gig of RAM). I would need a computer with 64-bit mode, more than 2.5 gig of RAM, 30 gig of free disk space, and 3 to 4 days of uninterrupted compute time. The hard part is that the program allocates 2 arrays of about 1.2 gig each. It saves 19 copies of these arrays to disk, as intermediate results to reconstruct the example board. My program is written in Java and is 360 lines long. It could easily be rewritten in C, though that would not change the machine requirements at all. It uses dynamic programming to keep track of the most stones (actually fewest liberties) that are possible on one side of a barrier, as it moves the barrier. If anyone has access to a machine that can run this program, please let me know. Thank you, Michael Wing ---------------- board size: 2 max: 2 time: 63 milliseconds .. Wb board size: 3 max: 6 time: 15 milliseconds .w. wbw b.b board size: 4 max: 12 time: 47 milliseconds b.bw wbw. .wbw wb.b board size: 5 max: 18 time: 31 milliseconds .w.wb wbwb. b.bwb wbw.w .wb.b board size: 6 max: 26 time: 62 milliseconds ..b.bw wbwbw. bw.wbw .bwb.b bwb.bw w.wbw. board size: 7 max: 37 time: 156 milliseconds b.bwb.b wbw.wbw .wbwbw. wb.b.bw .wbwbw. wbw.wbw b.bwb.b board size: 8 max: 48 time: 438 milliseconds .w.wbw.w wbwb.bwb b.bwbw.. wbw.wbwb .wbwb.bw wb.bwbw. .wbw.wbw wb.bwb.b board size: 9 max: 61 time: 1390 milliseconds .w.wbw.wb wbwb.bwb. b.bwbw.wb wbw.wbwb. .wbwb.bwb wb.bwbw.w bwbw..bwb ..wbwbwb. bwb.bw.wb board size: 10 max: 76 time: 4609 milliseconds b.b.bwb.bw wbwbw.wbw. .w.wbwb.bw wbwb.bwbw. b.bwbw.wbw wbw.wbwb.b .wbwb.bwbw wb.bwbw.w. .wbw.wbwbw wb.bwb.b.b board size: 11 max: 92 time: 16265 milliseconds b.bwb.bw.wb wbw.wbwb.b. ..bwbw.wbwb wbwb.bwbw.w bw.wbwb.bwb .bwbw.wbwb. bwb.bwbw.wb w.wbwb.b.bw bwb..wbwbw. .bwbwbw.wbw bw.wb.bwb.b board size: 12 max: 109 time: 55453 milliseconds .w.w.w.wb.bw wbwbwb.bwbw. b.b.bwbw.wbw wbwbw.wbwb.. .w.wbwb.bwbw wbwb.bwbw.wb b.bwbw.wbwb. wbw.wbwb.bwb .wbwb.bwbw.w wb.bwbw..bwb .wbw.wbwbwb. wb.bwb.bw.wb board size: 13 max: 129 time: 187203 milliseconds b.b.bwb.bwb.b wbwbw.wbw.wbw .w.wbwb.bwbw. wbwb.bwbwb.bw b.bwbw.w.wb.b wbw.wbwbwb.bw .wbwb.b.bwbw. wb.bwbwbw.wbw .wbw.w.wbwb.b wb.bwbwb.bwbw .wbwb.bwbw.w. wbw.wbw.wbwbw b.bwb.bwb.b.b board size: 14 max: 149 time: 623406 milliseconds ..bwb.bw.wbw.w wbw.w.wbwb.bwb b.bwbwb.bwbw.. wbwb.bwbw.wbwb .w.wbw.wbwb.bw wbwb.bwb.bwbw. b.bwbw.wbw.wbw wbw.wbwb.bwb.b .wbwb.bwbw.wbw wb.bwbw.wbwbw. bw.w.wbwb.b.bw .bwbwb..wbwbw. bwb.bwbwbw.wbw w.wbw.wb.bwb.b board size: 15 max: 172 time: 2073110 milliseconds b.b.b.bw.wbw.wb wbwbw.wbwb.bwb. .w.wbwb.bwb.bwb wbwb.bwbw.wbw.w b.bwbw.wbwb.bwb w.w.wbwb.bwbw.. bwbwb.bwbw.wbwb .b.bwbw.wbwb.bw bwbw.wbwb.bwbw. w.wbwb.bwbw.wbw bwb.bwbw.wbwb.b .bwbw.wbwb.b.bw bw.wbwb..wbwbw. .bwb.bwbwbw.wbw bw.wbw.wb.bwb.b board size: 16 max: 196 time: 7099422 milliseconds .w.wbw.wbw.w.w.w wbwb.bwb.bwbwbwb b.bwbw.wbwb.b.b. wbw..bwbw.wbwbwb .wbwbwb.bwbw.w.w wb.bw.wbwb.bwbwb bwb.bwbw.wbwb.b. ..wbwb.bwbw.wbwb bwbw.wbwb.bwbw.w wb.bwbw.wbwb.bwb .wbwb.bwbw.wbwb. wbw.wbwb.bwbw.wb b.bwbw.wbwb.bw.w wbw..bwbw.wb.bwb .wbwbwb.bwb.bwb. wb.bw.wbw.wbw.wb board size: 17 max: 221 time: 23763031 milliseconds ..bwb.bw.wb.bwb.b wbw.wbwb.bwbw.wbw b.bwbw.wbw.wbwb.. wbwb.bw.wbwb.bwbw .w.w.wbwb.bwbw.wb wbwbwb.bwbw.wbwb. b.b.bwbw.wbwb.bwb wbwbw.wbwb.bwbw.. .w.wbwb.bwbw.wbwb wbwb.bwbw.wbwb.bw b.bwbw.wbwb.bwbw. wbw.wb.b.bwbw.wbw .wbw.wbwbw.wbwb.b wb.bwbw.wbwb.bwbw .wbwb.bwb.bwbw.w. wbw.wbw.wbw.wbwbw b.bwb.bwb.bwb.b.b board size: 18 max: 248 time: 78762266 milliseconds ..bwb..wbw.wbw.w.w wbw.wbwb.bwb.bwbwb b.bwbw.wbw.wbwb.b. wbwb.bwb.bwbw.wbwb .w.wbw.wbwb.bwbw.w wbwb.bwbw.wbwb.bwb b.bwbwb.bwbw.wbwb. wbw.w.wbwb.bwbw.wb ..bwbwbw.wbwb.b.bw wbwb.b.bwbw.wbwbw. bw.wbwbwb.bwbw.wbw .bwbw.w.wbwb.bwb.b bwb.bwbwbw.wbw.wbw w.wbwb.b.bwb.bwbw. bwbw.wbwbw.wbwb.bw .b.bwbw.wbwb..wbwb bwbwb.bwb.bwbwbw.. w.w.wbw.wbw.wb.bwb > GPW(Game Programming Workshop) was held 10th-12th November 2006 in > Hakone, Japan. And Youhei Yano reported the maximum number of strings > in 19x19 is 277. > > 19 O . O X O . O X O . O X O . O X O . O > 18 X O X . X O X . X O X . X O X . X O X > 17 . X O X O . O X . X O X O . O X O X . > 16 X O . O X . X O X O . O X O X O . O X > 15 O X . X O X O . O X O X . X . X O X . > 14 . O X O . O X O X . X O X O X . X O X > 13 O X O . O X . X O X O . O . O X O . O > 12 X . X O X O X O . O X O X . X O X . X > 11 O X O X . . O X O X . X O X O . O X O > 10 . O . O X O X . X O X O . O X O X O . > 9 O X O X . X O X O . O X O X . X . X O > 8 X . X O X O . O X O X . X O X O . O X > 7 O X O . O X O X . X O X O . O X O X . > 6 . O X O X . X O X O . O X O X . X O X > 5 O X . X O X O . O X O X . X O X O . O > 4 X O . O . O X O X . X O X O . O . O X > 3 . X O X O X . X O X O . . X O X O X . > 2 X O X . X O X O . O X O X O X . X O X > 1 O . O X O . O X . X . X O . O X O . O > A B C D E F G H J K L M N O P Q R S T > > I tested some strong Go programs. > And there was no Go program that could handle this position :-) > Some crashed, and some could not load. > I tested Gnugo, KCC(Ginsei Igo5), Go4++(Tsuyoi Igo4), > Handtalk(ShudanTaikyoku3), Many Faces(AI Igo2004), Haruka, and FunGo. > (I don't know whether it is because of GUI or engine.) _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
