Exploring LZ's search algorithm: worked examples

xela · Post by **xela** » Tue Jan 07, 2020 6:33 pm

For a while I've been playing with the LZ source code to learn a bit more about how it works. I'm now at a point where I can output a CSV file with a trace of exactly which variations it's explored, in what order, and "why" (in terms of the various numbers that get calculated along the way).

Over the next few weeks I'd like to examine some positions where we've been saying "why did LZ do that???" and see how much we can explain.

To start with, I'm looking at the position in chapter 1 of James Davies's book Tesuji. This should be relatively uncontroversial, and then I'll look for some different examples. I know there were some curly situations discussed in these forums a few months back, but I don't have them at my fingertips right now. Suggestions are welcome!

Click Here To Show Diagram Code: [go]$$Bc Black to play and capture some white stones $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X . . . | $$ . . X O . . | $$ . . X O . . | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

Davies uses this for an extended discussion of how to read. For this position, I can break down his discussion into four phases. Details behind the cut for those who want to have a go as solving it first.

First, he puts down "the obvious move" and the "obvious" (to his target audience?) reply:

Click Here To Show Diagram Code: [go]$$Bc The obvious way to start $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X 2 1 . | $$ . . X O . . | $$ . . X O 3 . | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

Success! Black has captured some stones. But then Davies cautions us to look a bit deeper. What about other white replies?

Click Here To Show Diagram Code: [go]$$Bc White's options $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X . 1 b | $$ . . X O a c | $$ . . X O . . | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

For white a or b, we see some variations where white can connect up if black is careless, and then we get black's correct answer. For white c, there's the following variation:

Click Here To Show Diagram Code: [go]$$Bc Black's failure $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X 5 1 3 | $$ . . X O 4 2 | $$ . . X O . 6 | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

Black can split white into two groups, but each piece lives independently.

At this point Davies breaks off to look at some other choices for

, and wonders whether black should tenuki instead of playing out this position. Then at the end of the chapter, he reassesses the variation above and finds that

at

will actually capture some white stones. So this is the solution.

When I first read this book, I'd only recently given up on chess, so my memory of Kotov's Think Like a Grandmaster was still fresh. Kotov was a strong advocate of structured, disciplined thinking. He writes about how to construct a tree of variations sytematically and carefully, one of his key principles being that you assess each position once and once only. No going round in circles, no indecision, no wasted effort. He would have been appalled at Davies's approach of "Explore this for a while ... no, I'm not satified, let's try something else ... actually, I want to reevaluate the first one...". Since then, Kotov's approach has been criticised as too rigid, and "the Davies method" seems like an effective approach if you've got limited time and if your assessments aren't always correct on the first go.

When I next get a spare hour, I'll post some traces of LZ looking at the same position. My feeling so far is that MCTS is surprisingly human-like in how it bounces between alternatives and reevaluates things. But this is very much work in progress, meaning that I don't actually know the answer until I write it up (and perhaps not even then). More in the next day or two, fingers crossed.

xela · Post by **xela** » Tue Jan 07, 2020 8:42 pm

Quick update: for anyone who'd like to explore in Lizzie while you're waiting for me to get organised, I'll be using this full-board position.

Click Here To Show Diagram Code: [go]$$Bc Black can capture the O17 stones $$ --------------------------------------- $$ | . O . . . . . . . . . . . . . . . . . | $$ | . X O . . O . . X O O O . . . O O O . | $$ | . O X O O . . . X X X X O O . X O . O | $$ | . . X X O . O . . , . O X X X X X O . | $$ | . . . X X O . . X O . X O . . . X . . | $$ | . . . X O . O . X X X . X . . . X . . | $$ | . . . X O . . . O O O . . . . . O . . | $$ | . X X X O . . O X X O . O X . . O . . | $$ | . O O X O . X . X O O O X X . . . . . | $$ | . . . O X X . . X O X X O . . , . . . | $$ | . . . O X . X X O O O X X X . X O O . | $$ | . . . X . X O X O . X O O X . . X O . | $$ | . . X X X O O O O O O X O O X . X O . | $$ | . . O . . . . O X X X X . O X . X X O | $$ | . O O X X X . X O . . . . O . . . O . | $$ | . X X O O O X X O X . . . . . X . . . | $$ | . O O . X O O X . . . . . X . X O . . | $$ | . . . O O X O X . . . . . . . O O . . | $$ | . . . . . . O X . . . . . . . . . . . | $$ ---------------------------------------[/go]

ex1-davies_tesuji.sgf: (2.82 KiB) Downloaded 666 times

It was surprisingly hard to make a realistic full-board position where finding the tesuji and the correct follow-up is the difference between winning and losing! LZ is quick to say "actually, this other part of the board looks more interesting". Thanks to Go Seigen and Yamabe Toshiro for providing a context that almost matches what I want to look at, and apologies to same for mangling their creation. This position is GoGoD game 1953-04-08e at move 164 with a few stones added.

I suggest trying a few different LZ networks. The recent ones can solve the problem largely on "intuition", with minimal reading, so they're less interesting to explore in this respect. I'll start off with network number 157.

Bill Spight · Post by **Bill Spight** » Tue Jan 07, 2020 9:54 pm

xela wrote:For a while I've been playing with the LZ source code to learn a bit more about how it works. I'm now at a point where I can output a CSV file with a trace of exactly which variations it's explored, in what order, and "why" (in terms of the various numbers that get calculated along the way).

Over the next few weeks I'd like to examine some positions where we've been saying "why did LZ do that???" and see how much we can explain.

Bravo!

More power to you.

When I first read this book, I'd only recently given up on chess, so my memory of Kotov's Think Like a Grandmaster was still fresh. Kotov was a strong advocate of structured, disciplined thinking. He writes about how to construct a tree of variations sytematically and carefully, one of his key principles being that you assess each position once and once only. No going round in circles, no indecision, no wasted effort. He would have been appalled at Davies's approach of "Explore this for a while ... no, I'm not satified, let's try something else ... actually, I want to reevaluate the first one...". Since then, Kotov's approach has been criticised as too rigid, and "the Davies method" seems like an effective approach if you've got limited time and if your assessments aren't always correct on the first go.

I also like Kotov's approach.

It fits with Terence Reese's advice for contract bridge: Don't dither. I was somewhat surprised to find out later that research has disproven Kotov's once only dictum. (OC, you can revisit nodes in the search tree without dithering.

)

But there are a couple of reasons to question the once only rule, anyway. For one thing, iterative deepening, even though it is not the best search strategy, has been shown to be surprisingly effective. And it violates the once only rule about as much as you can! (Without dithering.

) Second, going back to The Chess Mind, we know that chess grand masters often see the best move instantaneously, with no conscious search at all. Kotov's method is a way of guiding conscious, linear processing. But, truth to say, the brain's unconscious, parallel search is more powerful.

The only bridge book I gave my sister, a social player, was one by the great bridge author, Victor Mollo, in which, for amateurs, he advocates seeing, not the methodical calculation of variations. As readers here may be aware, I advocate seeing for go. I believe that Kotov's method is great for training, but in actual play I think you have to allow your unconscious to work, as well.

Today's top bots are showing us plays that human have largely overlooked for centuries. Is it possible to train ourselves to see more of these plays? Yes. Play over games and guess where the bot played or wants to play. Then see if you are right.

OC, humans are still better than the bots at local depth first search, so there is no reason not to train those skills, as well.

FWIW, here is what I saw in Davies' problem.

Click Here To Show Diagram Code: [go]$$Bc Black to play and capture some white stones $$-------------+ $$ . . . . . . | $$ . O O a b . | $$ . . X O O . | $$ . . X X O . | $$ . . X 2 1 . | $$ . . X O . . | $$ . . X O 3 . | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

is indeed obvious. OC, I knew that

does not work, but I saw that variation, anyway.

Because the task is to capture some stones, I took a quick look at the corner stones, and didn't see anything there. I suppose that unconsciously I noticed that if Black cuts at a, White can reply at b, but nothing came to my consciousness.

Click Here To Show Diagram Code: [go]$$Bc Variation $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X a 1 c | $$ . . X O 2 3 | $$ . . X O . b | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

Next, I saw this variation as far as

. I knew that White could not play at a, and that Black could fill at c in response to b. I did not check that White's cut off stones were dead, because

is the only play.

Click Here To Show Diagram Code: [go]$$Bc Variation 2 $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X 4 1 3 | $$ . . X O 6 2 | $$ . . X O 5 . | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

Next, I looked at

. Again,

was obvious, to keep White cut in two. OC, I saw

in response to

. I could tell that

was futile, and did not consciously see the capture with

. I was aware that damezumari was a theme here, which prevented White from playing at 4, but I did not articulate it.

Click Here To Show Diagram Code: [go]$$Bc Variation 3 $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O . | $$ . . X . 1 3 | $$ . . X O 4 2 | $$ . . X O a 5 | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

Next, I looked at this variation. It was obvious that

was correct. It did not register consciously that

prevented a one point eye at a,

Reflecting on this later, I wondered if I would have seen

if I had not already seen variation 2.

Click Here To Show Diagram Code: [go]$$Bc Variation 4 $$-------------+ $$ . . . . . . | $$ . O O . . . | $$ . . X O O . | $$ . . X X O 5 | $$ . . X 6 1 2 | $$ . . X O . 3 | $$ . . X O 7 4 | $$ . . . X O . | $$ . . . X O . | $$ . . . X O . | $$ . . . X X . | $$ . . . . . . |[/go]

I did not see

, but I believe that beginners should consider it, if only to find this snapback.

And, even though not consciously considering

in a game would not bother me, I cannot claim to have solved the problem.

Aficionados of Sonoda may note that the four Black stones,

-

, all have a diagonal relationship.

----

OT, but I don't think I can refrain from a comment on current events. The world is on fire, both literally and figuratively. The Buddha saw that centuries ago: All things, O Bhikkus, are on fire.

jlt · Post by **jlt** » Wed Jan 08, 2020 3:30 am

Bill Spight wrote:The only bridge book I gave my sister, a social player, was one by the great bridge author, Victor Mollo, in which, for amateurs, he advocates seeing, not the methodical calculation of variations. As readers here may be aware, I advocate seeing for go. I believe that Kotov's method is great for training, but in actual play I think you have to allow your unconscious to work, as well.

If I understand correctly, during actual play you let sequences pop up to your mind without trying to read "all" variations. But in order to get an efficient neural net (=brain), you need to train it by studying go problems, pro games, etc. During that training process, you think that the methodical calculation of variations is "great", but do you consider it as necessary?

Bill Spight · Post by **Bill Spight** » Wed Jan 08, 2020 5:32 am

jlt wrote:
Bill Spight wrote:The only bridge book I gave my sister, a social player, was one by the great bridge author, Victor Mollo, in which, for amateurs, he advocates seeing, not the methodical calculation of variations. As readers here may be aware, I advocate seeing for go. I believe that Kotov's method is great for training, but in actual play I think you have to allow your unconscious to work, as well.
If I understand correctly, during actual play you let sequences pop up to your mind without trying to read "all" variations. But in order to get an efficient neural net (=brain), you need to train it by studying go problems, pro games, etc. During that training process, you think that the methodical calculation of variations is "great", but do you consider it as necessary?

It is important not to dither. It is important to supplement the human tendency to depth first search and shore up its weaknesses. Kotov's method does that. As for the best way to train the human brain, quien sabe? I don't think that we know the best way to train neural networks.

I have touched on these questions over the years. See the SL page about the fudge factor, for instance. https://senseis.xmp.net/?GoProblemsTheFudgeFactor

I look forward to seeing what xela is finding out about LZ's searches.

xela · Post by **xela** » Wed Jan 08, 2020 6:46 am

Bill Spight wrote:I look forward to seeing what xela is finding out about LZ's searches.

OK, I can give you the first instalment of raw data now, but I'll have to keep you in suspense another day or two for my commentary.

Here's a line-by-line trace of 100 playouts (LZ network number 157, using 1 thread with random number seed 42) with calculations (showing rejected second choice move at each node, as well as the chosen move):

ex1-davies_tesuji-trace157_100po.csv: (107.91 KiB) Downloaded 694 times

SGF file showing all variations with the evaluation of each playout (first choice moves only):

Bill Spight · Post by **Bill Spight** » Wed Jan 08, 2020 8:08 am

Hmmmm. It looks like maybe you need to put a Black stone at H-18 or maybe G-18.

RobertJasiek · Post by **RobertJasiek** » Wed Jan 08, 2020 8:35 am

jlt wrote:during actual play you let sequences pop up to your mind without trying to read "all" variations.

Such might be ok for strategic planning but for tactical reading it is a total failure. For tactical reading, in order not to read all variations, apply correct methods (such as Regular Reading) and valid, applicable simplifications (such as ignoring dominated moves).

During that training process, you think that the methodical calculation of variations is "great", but do you consider it as necessary?

It is mandatory and essential. Omitting it blocks tactical improvement.

RobertJasiek · Post by **RobertJasiek** » Wed Jan 08, 2020 8:44 am

xela wrote:Kotov's Think Like a Grandmaster was still fresh. Kotov was a strong advocate of structured, disciplined thinking. He writes about how to construct a tree of variations sytematically and carefully

What are his major principles for choosing among several next (half-)moves?

How does he walk through trees?

Bill Spight · Post by **Bill Spight** » Wed Jan 08, 2020 9:55 am

RobertJasiek wrote:
xela wrote:Kotov's Think Like a Grandmaster was still fresh. Kotov was a strong advocate of structured, disciplined thinking. He writes about how to construct a tree of variations sytematically and carefully
What are his major principles for choosing among several next (half-)moves?

How does he walk through trees?

Kotov's first chapter is on the calculation of variations. It is 74 pages long.

His basic approach appears to be breadth first. The first thing to do is to identify candidate plays. And when, in analysis, he spends 30 min. on a position, he may well have done that at each ply. In an actual game, with an average of only a few minutes per move, I doubt if he explored hundreds of variations to a shallow depth, however.

Kirby · Post by **Kirby** » Wed Jan 08, 2020 11:20 am

breadth first seems harder to do for humans. I like the idea of identifying some candidate plays, especially at the root of the tree. but after that, it's confusing.

let's say you have candidate moves 'A', 'B', and 'C'. then you want to do breadth first search on that. you take 'A0' and think of candidate responses to that move: 'A_0', 'A_1', and 'A_2' - and you visualize them. and you don't know if any of them work. then you stop visualizing them, and move onto the children of 'B'. What are the responses to 'B'? Let's say they're 'B_0', 'B_1', and 'B_2'. And you still don't know whether any of them are ideal. you keep going this way until you get to a leaf node. By that time, you may have explored almost the entire tree. And when you get to a leaf node, you can finally say, "Oh - leaf at 'A_0_0_0_0_0' doesn't work. let's rule that out." contrast this with depth first search. with depth first search, you can look at 'A'. Then immediately see what a response 'A_0' may yield, and then go to 'A_0_0', ... until you get to a leaf node in lg(N) time. and at that point, you can already start pruning options.

thinking in terms of breadth is important, because you don't want to miss moves. but it's pretty darn hard to keep the entire game tree in your head before you can start eliminating options from search.

RobertJasiek · Post by **RobertJasiek** » Wed Jan 08, 2020 11:38 am

Bill Spight wrote:His basic approach appears to be breadth first. The first thing to do is to identify candidate plays.

Once more: how does he choose among next candidates? In my Regular Reading method, one successful optimal candidate (e.g. "achieves independent life") is enough; no need to find all. When you just refer to breadth first, this says nothing about reading fewer than all next candidates. He must give some advice on that, mustn't he?

Bill Spight · Post by **Bill Spight** » Wed Jan 08, 2020 11:46 am

Kirby wrote:breadth first seems harder to do for humans. I like the idea of identifying some candidate plays, especially at the root of the tree. but after that, it's confusing.

I like the idea, from SOAR, of generating subgoals. For instance, in this problem you can quickly form the subgoal of preventing White from playing R-15. That makes the first line hane obvious for

. When

jumps to the first line, you have a new subgoal of preventing White from connecting underneath. It turns out that the descent to the third line achieves both subgoals. Then, when

connects to the jump, you have a new subgoal of preventing a one point eye. And there is a play that achieves both that goal and prevents R-15. Bingo!

Back in the 90s I was unable to program a go search program in SOAR, however.

Bill Spight · Post by **Bill Spight** » Wed Jan 08, 2020 11:50 am

RobertJasiek wrote:
Bill Spight wrote:His basic approach appears to be breadth first. The first thing to do is to identify candidate plays.
Once more: how does he choose among next candidates? In my Regular Reading method, one successful optimal candidate (e.g. "achieves independent life") is enough; no need to find all. When you just refer to breadth first, this says nothing about reading fewer than all next candidates. He must give some advice on that, mustn't he?

Of course he does. I refer you to the book.

Kirby · Post by **Kirby** » Wed Jan 08, 2020 12:35 pm

Bill Spight wrote:
Kirby wrote:breadth first seems harder to do for humans. I like the idea of identifying some candidate plays, especially at the root of the tree. but after that, it's confusing.
I like the idea, from SOAR, of generating subgoals. For instance, in this problem you can quickly form the subgoal of preventing White from playing R-15. That makes the first line hane obvious for . When jumps to the first line, you have a new subgoal of preventing White from connecting underneath. It turns out that the descent to the third line achieves both subgoals. Then, when connects to the jump, you have a new subgoal of preventing a one point eye. And there is a play that achieves both that goal and prevents R-15. Bingo!

Back in the 90s I was unable to program a go search program in SOAR, however.

you can create subgoals to guide your search, but doesn't it still mean you have potentially more to keep in your head with bfs? with depth first search, i really like that you can prune entire branches of the tree (i.e. this is no longer worth exploring, because i've come to a terminal state and identified that it's bad) - you don't have to revisit nodes in the tree once you've eliminated them. but with breadth first, you aren't "done" with a node yet after you've first seen it, because you might come back to it after searching later in the tree..

you could do that with subgoals, too: i no longer want to explore this branch at all, because after i searched down the tree a bit, i found out that it cannot meet my subgoal.

if there's one optimal move in the game tree, both approaches, in worst case, find the result after looking through the entire tree. but at least with bfs, you don't have to keep the moves you've already explored in your head.

Life In 19x19

Exploring LZ's search algorithm: worked examples

Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples

Re: Exploring LZ's search algorithm: worked examples