Handicap puzzle

Warren Smith has posed this puzzle on a mathematical mailing list, and it looked like a fun one:

Play "go" on an NxN grid (usual is N=19). In "H-handicap" go, the second player (white) generously passes his first H turns, before starting to play.
For example, some pro could easily give me handicap H=9 and still destroy me.

PUZZLE: for the smallest H that you can, formulate a strategy such that the first player can assure a win, even against a perfect opponent.

You can only assure a win if you are at least 3 stones stronger then the actual handicap that was given to you, and still this would not be perfect, since you can still make mistakes. But, if you are a perfect player you could do that, in more then one way, use your handicap stones to secure a side, or a coulpe of corners, or even use it to build imense force, so whute can not live confortably anywhere

I think the question is more formal... but since there are so many variables, it's hard to write out a complete strategy when H get lower.

One example 'strategy' would be:
N=19, H=180:
- place handicap stones in checkerboard pattern starting with an empty corner
- pass

So, H is at least <= 180 :-)

How about drawing a line across the middle of the board with 2 eyes embedded within it, then play symmetry? (IIRC Warren Smith himself suggested this solution.)

I'm no expert at creating minimal eyes, but I know that you can fork the end of the line at cost of 3 pieces each end. So N=19, H=25? (And N=9, H=16; N=13, H=20)

If you just fork the line with 3 stones one can still turn one of those eyes in a false eye, leaving just one eye, thne, for this strategy to work you would need, at least 4 eyes[not to mention that one could use that flase eye to create a ko, caprture and thne defned it, ending the possibility for you to play a symmetrical game

I think a group with two eye in the centre of the table is enough. Then play mirror go. The group should be itself symmetric so it would not allow white to play moves black cannot mirror. The first one I thought about has 16 stones but I found a 13 stones group.

I found an 11 stones group, but it seems there is a strategy for white at the border of the grid, so my proposal doesn't work.

Mirror-Go will not work to assure a win as setting up a quadruple-Ko will assure a repetition and therefore a trivial draw for the handicap-giver.

Good point Karthum!

How is this a false eye, I thought false eyes had to have diagonal connections, so that part of them could be killed?

##....
.#####
##....

Phil, what you have drawn is not a false eye. I think what FHvR had in mind with "just fork the line with 3 stones" was

.....<br/>#....<br/>.####<br/>#....<br/>.....<br/>

Thats exactly it Marleys, Karthum also have a really good point.

Has anyone made progress on this problem? I thought about it a little and came up with the 143-stone pattern below (the x's are the stones). Black can always pass; each single empty point serves as an eye.

.xx.xx.xx.xx.xx.xx.
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
x..x..x..x..x..x..x
.xx.xx.xx.xx.xx.xx.

Actually, since we don't need to control the whole board, we can use fewer stones.

.xx.xx.xx.xxx.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
x..x..x..x..x.....
.xx.xx.xx.xxx.....

This uses 103 stones. Black controls 144 points, and there are 95 points in the open section on the right.

@Tommah, You only have 18 points in each row. Also, do you need that many black stones at the top and bottom? If your 103 stones work, would the following 76 black stones also work? I'm thinking White could not get any live group in the leftmost 12 columns, so Black has 8*19 points controlled and even ceding the rightmost 7 columns to White is only 7*19 points.

..x..x..x..x.......<br/>..x..x..x..x.......<br/>...<br/>..x..x..x..x.......<br/>..x..x..x..x.......

I was playing it safe. Your example probably works, though. I came up with this pattern too:

..x........x
xx.xxxxxxxxx
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x
..x.x.x.x..x
..x........x

I'm pretty sure this works. This uses 71 stones, controls 157 points, and leaves 133 points to the opponent. The idea is that the solitary black stones can always connect somehow to the lefthand chain, so they live. In the 2x17 areas, black must prevent White from making live groups, but any groups White tries to form there don't threaten the black stones. The fact that the single stones can connect to the left is a consequence of the fact that in a pattern like this:

a.b
a .
a.b
a .
a.b
a .
a.b
a .
a.b
a .

where one player is trying to connect each b's to an a (along the .'s) and the other is trying to disconnect, the first player can always win.

I meant to put "etc." after my a/b pattern. It can be arbitrarily long.

Remember that you don't have to "leave" any points to the opponent as long as you can specify a strategy such that they don't all become your opponent's territory.

Mediating for the originator of the puzzle:
"""
I posted my discovery to an online go forum myself, and it got a
surprising refutation from Tuomo Salo 3 dan.

A 1 kyu then attempted (probably correctly) to produce a "54 stone
handicap solution":http://senseis.xmp.net/?ProvableStrategyForWinningFreePlacement25HandicapGo%2F54StonesIsEnough

Both my (wrong) discovery and the refutation and attempts to
rediscover the answer, all are quite interesting. Go is a lot
deeper than it seems when you learn the amazingly simple rules.
In fact, after many years play, go still is a lot deeper than
it seems and even the greatest players seem to regard it as
inexhaustible.
"""

Note, I've not read those links yet, but will do now I've passed them on
>Send Message<

In the latter URL (dunno why textile didn't href-ify it), what does
"However Black can consider the points with the same letter miai." (in the last section) mean?

In the upper link, I don't understand the refutation by bass - he's not playing rotational mirror moves, but reflective ones. There is still the symmetry he claims is no longer there, it's just at the bottom of the board that he's chopped off.

I'll have to read through all of this when I have the time. I'll just remark that I got my 71-stone solution down to 68 stones, and there is a simple explicit strategy for winning from that configuration.

H=0

Strategy: draw the game tree and put 0 in every leaf that p1 wins and 1 in every leaf that p2 wins. In all internal nodes take minimum of all chilren values if it is p1 to play and maximum if it is player 2 Now, depending on the value in the root, claim to be player 1 or 2.

Strategy: If you are player 1 always go to the child with minimum value, if you are player 2, always go to the child with the maximum value.

Thats about as explicit as a strategy gets ;)

_"In “H-handicap” go, the second player (white) generously passes his first H turns, before starting to play."_

Actually, H-handicap means that white passes his first H-1 turns, so that Black places H stones before White makes his first move. Go without komi is 1-handicap Go.

Interesting puzzle, by the way.