Exploring LZ's search algorithm: worked examples

For discussing go computing, software announcements, etc.
Bill Spight
Honinbo
Posts: 10905
Joined: Wed Apr 21, 2010 1:24 pm
Has thanked: 3651 times
Been thanked: 3373 times

Re: Exploring LZ's search algorithm: worked examples

Post by Bill Spight »

dfan wrote:
Bill Spight wrote: Well, considering that the square go board, unlike the chess board, has no essentially identifiable sides, or quadrants, or semi-quadrants, and thus has eightfold symmetry, why shouldn't the neural nets have eightfold symmetry?
I was speaking from an implementation point of view (thus my question about the form of the constraint on the convolutional kernels), rather than the mathematics of the desired output (which I agree "should be" symmetrical).
I don't know what assumptions you are making, to make things so difficult.
I'm not sure what this sentence means, but I'm also not sure it's worth pursuing! If you want to spell it out more I will try to respond, but I also don't mind just dropping it.
I've got the general idea, thanks. :)

As far as I am concerned, going into detail about implementation would not mean much to me until I get my new axe. Then I can play around with different ideas. :)
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.
Bill Spight
Honinbo
Posts: 10905
Joined: Wed Apr 21, 2010 1:24 pm
Has thanked: 3651 times
Been thanked: 3373 times

Re: Exploring LZ's search algorithm: worked examples

Post by Bill Spight »

Mike Novack wrote:
Bill Spight wrote: I wondered if they count somewhat like parrots do. Parrots can count to 6 in the sense that they can distinguish between there being 5 objects in a small enough space and there being 6 objects there, but the difference between 6 objects and 7 objects gives them trouble. I have imagined that the bots gradually learn to distinguish between N and N-1 dame as N increases.
Not just parrots. We humans can count small numbers of things if we want to, because we have learned counting as a method for when the number of things is too great for "number recognition". But we do not ordinarily count small numbers of objects. We recognize how many (just like the parrots). I believe that there have been recent papers about AI neural nets being able to learn this ability. Keep in mind, OUR brains ARE neural nets.
Rainman excepted, I think humans may not in general be as good as parrots. For instance, there are human languages with no numbers greater than three. :o
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.
xela
Lives in gote
Posts: 652
Joined: Sun Feb 09, 2014 4:46 am
Rank: Australian 3 dan
GD Posts: 200
Location: Adelaide, South Australia
Has thanked: 219 times
Been thanked: 281 times

Re: Exploring LZ's search algorithm: worked examples

Post by xela »

Bill Spight wrote:Rainman excepted, I think humans may not in general be as good as parrots. For instance, there are human languages with no numbers greater than three. :o
Can't think of too many parrot languages with numbers greater than three either.
Maharani
Lives with ko
Posts: 249
Joined: Wed Oct 09, 2019 9:47 am
Rank: OGS 9 kyu
GD Posts: 0
OGS: Maharani
Location: Pasadena, USA
Has thanked: 80 times
Been thanked: 12 times

Re: Exploring LZ's search algorithm: worked examples

Post by Maharani »

xela wrote:
Bill Spight wrote:Rainman excepted, I think humans may not in general be as good as parrots. For instance, there are human languages with no numbers greater than three. :o
Can't think of too many parrot languages with numbers greater than three either.
Lol :D
jann
Lives in gote
Posts: 445
Joined: Tue May 14, 2019 8:00 pm
GD Posts: 0
Been thanked: 37 times

Re: Exploring LZ's search algorithm: worked examples

Post by jann »

NNs like to start from random (non-random inits learn slower, if at all), and enforcing symmetries reduces randomness. Some papers showed that most NN convergences are direct results of separatable, luckily initialized weight subsets (the rest may even be left out). And because of the randomised use of the net in selfplay, if just one symmetry learns / finds out sth useful, that will also be taught to other symmetries soon.
xela
Lives in gote
Posts: 652
Joined: Sun Feb 09, 2014 4:46 am
Rank: Australian 3 dan
GD Posts: 200
Location: Adelaide, South Australia
Has thanked: 219 times
Been thanked: 281 times

Re: Exploring LZ's search algorithm: worked examples

Post by xela »

Bill has suggested an interesting position for analysis. It's an example of "LZ ignores a good move".

The game is Sakaguchi-Hayashi, GoGoD 1861-12-18e. After :w30: there's an interesting fight happening in the bottom left.
Click Here To Show Diagram Code
[go]$$Bc Black to play
$$ +---------------------------------------+
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . X . . . . . . . . . O . . . . |
$$ | . . . . . . . . . . . . . . . . X . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . O O O X . . . . . . . . . . . . |
$$ | . O b O X X X X . . . . . . . . . . . |
$$ | . a X X O O . . . . . . . . . . X . . |
$$ | . . X O . O . O X . . . . . O . . . . |
$$ | . . X O O . c . X . . . . . . O . . . |
$$ | . . e . . f d . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ +---------------------------------------+[/go]
Looking at the policy network, a is the "first instinct" move (70-80%), and all of b through d are interesting (3-10%). Possibly e and f are worth a quick look too (around 1%). LZ-258, ELF and KataGo 1.2 all broadly agree on the policy values. (Installing KataGo 1.3 is on my to-do list!)

What would you play here? Spoilers behind the cut.
Hayashi actually played a. He went on to lose the game: black soon tenukis, the bottom left is left either unresolved or beyond my reading ability, and there's a big fight at the top left.
According to the ELF commentary, c is a bit better (assuming 7.5 komi, whereas in fact it's a no komi game). This is based on about 2,800 playouts for a (winrate 41.6%) and 155,000 playouts for c (winrate 50.5%).

LZ-258 on a few thousand playouts from the starting position will choose a as the best move, but if you put c on the board it will get a higher evaluation. So here's a case where it can see in hindsight that there's a better move but it won't find the move on its own. Although for LZ-258 the difference isn't quite as big, 46% for c versus 41% for a.

(Actually, LZ-258 may find the right move after about half a million playouts, depending on the random number seed. With a "bad" seed, it will in principle still get there, but I haven't checked how many million playouts are needed.)

LZ using the ELF network will replicate what's in the official ELF commentary, and goes to c almost right away.

For what it's worth, I'm not convinced that Hayashi's move is a "mistake" as such. KataGo 1.2 analysing without komi has black about 8 or 9 points ahead and sees both a and c as winning moves. It's like LZ-258 in that left to its own devices it will prefer a, whereas c gets a higher score in hindsight. But the winrate difference is only about 3%. KataGo would have us believe that black lost the game later, with a blunder at move 55.
Here's the full game for your entertainment. More detailed AI analysis to come soon...

Attachments
sakaguchi-hayashi-1861-12-18.sgf
(763 Bytes) Downloaded 664 times
xela
Lives in gote
Posts: 652
Joined: Sun Feb 09, 2014 4:46 am
Rank: Australian 3 dan
GD Posts: 200
Location: Adelaide, South Australia
Has thanked: 219 times
Been thanked: 281 times

Re: Exploring LZ's search algorithm: worked examples

Post by xela »

Here's a trace of 10,000 playouts (SGf summary only, the CSV files for this many playouts are huge!) I'll give you three versions:
  • LZ-258 from the starting position: it spends most of its time exploring B5, and only gives 43 playouts to G3. (Playing with different random number seeds, I can persuade it to give over 60 visits to G3, but the evaluations don't change much.)
  • LZ-258 analysing the position after G3 has been played.
  • LZ with the ELF network from the starting position. It still looks at B5 first, but starts paying serious attention to G3 after about 2,000 playouts, and looks at G3 exclusively from playout 4,319 onwards.






Remember that the difference between LZ-258 and LZ-ELF here is only the network. It's still the same software running the same search algorithm. So how do the different networks affect the choice of B5 or G3?

The policy values tell us that both networks will look at B5 first. But that's not the full story. LZ-258 gets to G3 at playout 93, and on a first look thinks that it's a 60% winrate for white, not that much different from the initial 59% for B5. But after a few playouts, G3 starts to look worse, so LZ-258 gives up on it. LZ-ELF starts off similarly, looking at G3 from playout 21, and scoring G3 at 46% for white compared with 49% for B5, again in the same ballpark. But on more playouts, LZ-ELF rates B5 as getting a lot worse for black, while the rating for G3 doesn't change much. So the difference isn't between those two positions specifically, but further down the tree.

Looking at the variations after B5, I haven't yet found a massive difference between 258 and ELF. But here's something interesting for the G3 variations:
Click Here To Show Diagram Code
[go]$$Bc
$$ | . . . . . . . . . .
$$ | . . . O O O X . . .
$$ | a O 6 O X X X X . .
$$ | . 5 X X O O . . . .
$$ | b . X O . O . O X .
$$ | . . X O O . 1 . X .
$$ | . 3 2 4 . . . . . .
$$ | . c . . . . . . . .
$$ +--------------------[/go]
Both networks have a as the first instinct. But it's not actually a good move. ELF spends 15 playouts on it, and then gives 994 playouts to c (and has another look at a later on). Meanwhile it's been spending a lot of time on B5 at the start, so it's not until around playout number 3,000 that c is seen to be clearly better than a in this diagram.

LZ-258 gives 18 playouts to a, but then its second choice is b, which also doesn't work well (and is discarded after four playouts). Starting from the initial position, LZ-258 will never even look at c (the policy value is around 1%). By playout number 5,000 it's given up on G3 (at least for the time being; it will come back by playout number 100,000 if you let it run that long). Maybe this is a little blind spot in LZ-258's network that skews the evaluations slightly. Not the full story, there are still a lot of other variations to look at.

Finally, G3 in the initial position has a policy value of around 7% for LZ-258, or around 10% for ELF. Does that 3% difference have a big influence on the search? I suspect not -- we've seen examples of where 1% moves can get a lot of playouts if the evaluations are promising -- but it's hard to say for sure (I've tried scribbling down some equations based on the UCT formulae, and the maths gets pretty messy). I might come back to that later. Or I might get distracted by something else...
Attachments
trace_1861-12-18e-move31-LZ-ELF.sgf
(1.6 MiB) Downloaded 649 times
trace_1861-12-18e-move32-LZ258.sgf
(1.7 MiB) Downloaded 632 times
trace_1861-12-18e-move31-LZ258.sgf
(1.75 MiB) Downloaded 640 times
xela
Lives in gote
Posts: 652
Joined: Sun Feb 09, 2014 4:46 am
Rank: Australian 3 dan
GD Posts: 200
Location: Adelaide, South Australia
Has thanked: 219 times
Been thanked: 281 times

Re: Exploring LZ's search algorithm: worked examples

Post by xela »

I was going to post some ladder positions here, but it got complicated, so I started a separate thread for them.
Post Reply