Depth first search vs. Breadth first search

[Suji]

I'm a depth-first searcher, and I created a thread a while back about my opponents making moves that I didn't consider. The thread is here. I'm trying to do problems, with my current study plan, and got thinking that what would help me is a breadth-first search. I'm not trying to do a lot of problems, but do them whenever I remember to do them.

Here is the one of MANY good responses that popped into my head as I was formulating my idea:

Okay, this problem stems from my exclusive chess days, and I really don't know what to do about it. Since I've gotten used to playing by my intuition at chess, it's somewhat carried over to Go. Here's the problem: I read ahead with a sequence that I consider best and make my move. The opponent thinks and makes a move that I didn't even consider. Thus, all of my reading ahead did me ZERO good. I then have to "waste" more time thinking about my next move, and when I make my next move my opponent makes ANOTHER move that I didn't expect.

This is my problem with reading ahead.

This is a great learning opportunity. If your opponent not only makes a move that you did not consider, and it was a good enough move to throw you for a loop, you have learned something.

I suspect that your problem lies in the phrase, "reading ahead". Perhaps you are reading too deeply, and not broadly enough. (Obviously, if you are not even considering the best candidates, you are not reading broadly enough.)

For technical reasons having to do with short term memory, humans handle depth first search better than breadth first search. So go ahead and read deeply. However, taking a cue from Kotov, at each step identify all of the good candidate moves that you see. (You have to trust your judgement. You can't read every branch of the tree.) As you get better, you will be able to prune better.

OC, studying tesuji and life and death will help you to identify good candidate moves and prune bad ones.

Good luck!

Okay, I'm familiar with Kotov and his method, though I haven't read his book Think Like a Grandmaster. Basically, what the method boils down to, is selecting candidate moves for yourself, and in response selecting each of your opponent's candidate moves while going deeper and deeper into the tree. Now, obviously, in a game such as Go or chess the branching factor is relatively high and no one can read the entire tree. Even if I limit my choices to two moves, and consider two responses the tree gets unmanageable fairly soon.

Here's what I came up with. During tsumego I have a hard time broadening my search, let alone in games, so doing tsumego correctly is hard (Looking at every possible variation.). Could I treat the tsumego problem like a math problem, and do it in my head while I try to write down possible variations. This way I can see the variations that I have already done, and not waste time trying to remember them. Could this help train my brain in such a way that breadth-first searches are easier? Or, is this a bad idea?

[danielm]

I think it is quite normal for mere mortals to have trouble keeping variations of a tree in your head, forget individual lines and do them twenty times over, etc. At least it's normal for me... That shouldn't discourage you though, just try your best every single time and it will become better naturally. Redundancy is probably the primary reason I get into time trouble almost every single game, but I'd rather force myself to practice and improve my reading the hard way, than to take shortcuts and not even try.

The important first step is to be aware of the issue, and not be satisfied just reading random moves ahead. That's not really reading, that's looking. Sometimes that is useful to get a quick feel for a position, but it will not give you clear answers about anything (Monte Carlo engines might disagree, but we don't have the luxury of doing a million random readouts per move.. ). Always be aware that you have to choose candidate moves at every step of the way.

Even if you don't think you are able to look through the whole tree yet, you can start by at least making a point of identifying the candidates. This will tell you a lot about the nature of the problem, e.g. if there is clearly only one reasonable candidate, the line is forced and you can just look ahead. If there are 20 reasonable candidate moves, then you already know that you should not waste time looking too deep into individual lines before starting to prune.

As for your suggestion to write down variations while doing tsumego, I don't know if that is helpful or not. Perhaps it will help you sort out your thought processes, so you are more likely to remember to do it properly next time? It doubt that it will actually make you better at keeping variations in your head though.

[flOvermind]

I don't think humans can actually do breadth-first search. It's just not possible to keep the queue of open positions in your head. Also, the constant jumping between unrelated variations is highly confusing.

When someone tells you you have to read "broader", that doesn't mean you should do breadth-first search. You should still do depth-first search, but you back up more often, and consider more alternatives of each move.

So what you do is this: You consider all alternative moves in a position. Take the one that is likely to be best, and mentally "play" it. Then again you consider all possible moves, and play one of them, and so on. Later, you back up to the same position, and consider another move. Then you back up again, and consider the next one, and so on. When you run out of likely looking moves, you back up further, and consider alternatives to the previous move.

That's a classical depth-first search algorithm. You don't have to remember any position very long. If you now want to "broaden" your search, just consider more alternatives to each position. You don't need to change anything in the algorithm itself.

[p2501]

I don't think humans can actually do breadth-first search. It's just not possible to keep the queue of open positions in your head. Also, the constant jumping between unrelated variations is highly confusing.

While that may be more common, there is a pro player that is known for starting with the least likely move when reading positions. Can't remember his name though atm and a quick google search came up with nothing.

[flOvermind]

Sure, why not. Leave the best for last

That method certainly has the benefit of not falling into the trap to play the first move that more or less works, because you *know* the best alternative is likely coming last

But that's still depth-first search

[lindentree]

I don't think humans can actually do breadth-first search. It's just not possible to keep the queue of open positions in your head. Also, the constant jumping between unrelated variations is highly confusing.

While that may be more common, there is a pro player that is known for starting with the least likely move when reading positions. Can't remember his name though atm and a quick google search came up with nothing.

Kitani?

[moonrabbit]

When we refer to calculation/reading in go, there are actually several different kinds of mental processes involved. Some of them include:

1) Brute force visualization (we've all done this)
2) Intuition
3) Logic
4) "Technique"/"Knowing the answer beforehand"

At any given time I think most people use some kind of combination of these different thought processes.

By "intuition" I mean something like having a feeling as to what the right moves are, even if you can't necessarily justify that intuition in some other way.

By "logic" I mean that there is some kind of rational thought process, whether it involves following a go proverb, or something else. For example, in a life-and-death problem you might have a thought process like "My potential eyepoints are at a and b, so I should play at c to secure both eyes." Or "this group looks cramped, so the proverb says to try the hane to reduce the eyespace."

By (4) I mean something like knowing where the vital point of a 5-point bulky shape is, or knowing the hane-connect first line endgame sequence, or any other situation where you look at the position and the stones just "plop" down automatically in your head.

It's normal when you're doing a difficult problem to spend some time fumbling around with brute-force search (1) but I think you want to convert that to (2) and (3). In other words, try to come up with a reason for why the solution works rather than try to keep the whole tree in your head. Eventually, after you've seen a position enough times, it turns into (4) where you just see the answer instantly.

[ez4u]

There is no one, right way even among the pros. From JF and TMark's "The Go Consultants", describing how the teams worked together...

"The A team [Segoe Kensaku and Suzuki Tamejiro]... were calm and their discussions ranged wide and deep. Within this team there was a notable difference. Segoe, when he faced the board, would first of all try selecting the points where he might be able to play a tesuji. Gradually, as the trial stones accumulated on the board, he would shift into assessing the profit and loss or other merits of the position. He would do this in great profusion, rapidly and in a "business-like" manner. In this he was probably unequalled, said Ikoma [author of the original Japanese book on the game].

In contrast, Suzuki did not roam as widely as Segoe. He chose fewer points to examine, but then examined them very deeply and thoroughly. In this process he would look even at moves that other pros would dismiss instantly as bad style, with the result that he could find unexpected brilliancies. Segoe had a tendency to dismiss Suzuki's discoveries because he fastened onto the bad shape aspects first. Suzuki, however, would patiently press on for another ten moves or so, and again solicit approval. Yet even when, at long last, he got the thumbs up, he did not stop there. He kept looking. He was as "superb prospector" in Ikoma's peculiar phrase..."

[moonrabbit]

I remember reading in another of John F.'s books about how Go Seigen and one of his match opponents (Kitani, perhaps?) would sometimes consider extremely different variations in analyzing a position but nevertheless come to the same conclusion as to which move was the best.

If you pose the question as "depth first or breadth first?" I don't think there's a very good answer -- I'd have to say "neither and both." But there are very interesting questions behind it, which are how one picks candidate moves, how aggressively one prunes the tree, and how one navigates the tree.

Something to keep in mind about Kotov's "tree of analysis" is that almost no one actually thinks that way, at least not systematically and routinely (There's a quote attributed to the Russian GM Anatoly Lein who says "I don't think like a tree. Do you think like a tree?") The thing is that it's hard to actually choose candidate moves until you've seen some variations already, and in any event the tree rapidly gets out of hand. So a more common thinking pattern might be to pick one candidate move, follow a variation a bit, and then evaluate the result. And then based on that evaluation, maybe you back up and revise your analysis or pick different initial candidates. (This is similar to what Bill described in the quoted post, and what flovermind said.)

For tsumego, something that often works is to just pick a candidate starting move and try to refute it. When you see the refutation, that can help you pick a better starting move. At least it sounds better than "start with the worst move" even if it is a similar idea, practically speaking.

I don't mean to bash Kotov. His book has a lot of practical advice in it. For example, he has a really great story about Capablanca, which goes like this:

...a group of masters were analysing an ending. They could not find the right way to go about things and there was a lot of arguing about it. Suddenly Capablanca came into the room. He was always fond of walking about when it was his opponent's turn to move. Learning the reason for the dispute the Cuban bent down to look at the position, said "Si, si," and suddenly redistributed the pieces all over the board to show what the correct formation was for the side that was trying to win. I haven't exaggerated at all. Don Jose literally pushed the pieces round the board without making moves. He just put them down in fresh positions where he thought they were needed.

Think Like a Grandmaster, Chapter 4

That is, before looking at any candidate moves or variations, Capa identified an objective he wanted to achieve. Then it would be a matter of technique to figure out which moves were necessary to execute the plan.

Go is different of course, but a similar sort of thought process can be powerful sometimes.