Complexity as width x depth

Knotwilg · Post by **Knotwilg** » Sun Jul 26, 2020 12:09 pm

As stated in another thread, the relative complexity of a go problem can be approximated by the number of variations you need to go through (width) and the length of longest variation (depth). Relative complexity because it depends on a player's strength: a stronger player will consider fewer candidates and will see earlier what the result of a variation will be. For example, the L-group is probably a complex problem for a novice, while it's an end state of a variation for an experienced player (it's dead).

My favorite app gives me a daily diet of 2 easy problems, 2 medium ones and 2 hard problems. For me, KGS 2d, the easy problems require no reading and can be solved at a glance. The medium ones require a little reading and I occasional fail. The hard problems require considerable reading and I get them wrong fairly often.

Examples:

Click Here To Show Diagram Code: [go]$$B Easy 1 $$ ---------------------- $$ | . . . . . . . . . . $$ | O O . . . . . . . . $$ | X X O O O . . . . . $$ | . X X X O . . . . . $$ | 1 a O X O . . . . . $$ | O . X X O . . . . . $$ | O X X O . . . . . . $$ | . O O O . . . . . . $$ | . . . . . . . . . . $$ | . . . . . . . . . .[/go]

Today's Easy 1 is ridiculously easy. The primitive move at A doesn't work because of White's obvious answer at

. Playing

instead comes in a split second.

Width: 2. Depth 2.

Click Here To Show Diagram Code: [go]$$B Easy 2 $$ ---------------------- $$ | . 3 . O X . . . . . $$ | X 1 O O X . . . . . $$ | X O X O X . . . . . $$ | . O 2 X X . . . . . $$ | O O O . . . . . . . $$ | . X . X . . . . . . $$ | . X . . X . . . . . $$ | . . . . . . . . . . $$ | . . . . . . . . . .[/go]

Today's Easy 2 is deceptively easy: it's easy to see what the problem conceiver wants us to see. Again, the plain move (

at

) doesn't work and

does. This time however it requires experience to assess the results of these two variations. In the failed variation, Black can still play

and it may give a beginner a hard time to figure out if this is bent 4 or not (it isn't). In the successful variation, the result is eye against no eye and one has to see the approach liberty giving Black the edge in the capturing race (or read out the whole thing). Depending on how you look at it, width = 2 and depth is 3 or 8.

The problem is harder than the previous problem, even if the number of variations is equal, because this requires more depth of reading and/or a higher level of evaluation.

Click Here To Show Diagram Code: [go]$$B Medium $$ ---------------------- $$ | . . . . . . . . . . $$ | . a X . X . . . . . $$ | . O O X . . . . . . $$ | . 2 X O X . . . . . $$ | . 1 O O X . . . . . $$ | . 5 3 X O . . . . . $$ | . O . . O . . . . . $$ | . . O . . . . . . . $$ | . . . . . . . . . .[/go]

One of the 2 medium problems is presented here. Again it's fairly easy to know what the composer wants us to do. After 5 moves there's a clear winner in the capturing race, Black 4 against White 3, but it may require additional reading to see that White can't make use of any special properties of the corner.

at

is 1 variation and best for both.

at

or at A can be quickly dismissed. Width is 2 (or 4) and depth is 5 (or 11). The problem is on the easy side of medium.

RobertJasiek · Post by **RobertJasiek** » Sun Jul 26, 2020 12:36 pm

Knotwilg wrote:the number of variations you need to go through (width)

This is not the width. Usually, width in tree assessment is the maximum number of children (moves) of all nodes (positions) at a ply (same level of nodes), for all plys.

Since alternatives can exist and pruning might be possible, one should speak of the minimum number.

Knotwilg · Post by **Knotwilg** » Sun Jul 26, 2020 12:56 pm

RobertJasiek wrote:
Knotwilg wrote:the number of variations you need to go through (width)
This is not the width. Usually, width in tree assessment is the maximum number of children (moves) of all nodes (positions) at a ply (same level of nodes), for all plys.

How's that not the same?

Since alternatives can exist and pruning might be possible, one should speak of the minimum number.

I don't understand this.

Bill Spight · Post by **Bill Spight** » Sun Jul 26, 2020 1:15 pm

I haven't delved much into this, myself, but for conscious search humans are heavily space constrained. That's why humans are much better at depth first search than breadth first search. For humans, then, the complexity of something like beam search may be appropriate.

Knotwilg · Post by **Knotwilg** » Sun Jul 26, 2020 1:47 pm

This is then one of today's hard problems:

Click Here To Show Diagram Code: [go]$$B Hard 1 $$ ---------------------- $$ | . C . O . . . . . . $$ | C a X X O . . . . . $$ | . X O O . O . . . . $$ | . . X O . . . . . . $$ | b . X O . . . . . . $$ | . X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

I have two things to work with in my low dan repertoire. The obvious thing, the capture at A, and the less obvious thing, the placement White has at B, which falsifies the whole eyespace there. At my level I don't have to read what happens with that placement. Black can't live with that eyespace alone however, needing 3 moves, so he needs to start by covering A, possibly sacrificing the 4 stones below. Possible starting moves are therefore A and the 2 circled points

I'm describing at length a thought process of 1-2 seconds.

Click Here To Show Diagram Code: [go]$$B Solid $$ ---------------------- $$ | a . b O . . . . . . $$ | . 1 X X O . . . . . $$ | 3 X O O . O . . . . $$ | . . X O . . . . . . $$ | 2 . X O . . . . . . $$ | 4 X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

is quickly dismissed. White has time to falsify the other eyespace and Black needs two moves still.

Click Here To Show Diagram Code: [go]$$B Hanging 1a $$ ---------------------- $$ | . 2 . O . . . . . . $$ | 1 4 X X O . . . . . $$ | . X O O . O . . . . $$ | 3 . X O . . . . . . $$ | . . X O . . . . . . $$ | . X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

Click Here To Show Diagram Code: [go]$$B Hanging 1b $$ ---------------------- $$ | . 2 5 O . . . . . . $$ | 1 3 X X O . . . . . $$ | . X O O . O . . . . $$ | 7 8 X O . . . . . . $$ | 4 . X O . . . . . . $$ | 6 X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

Click Here To Show Diagram Code: [go]$$B Hanging 1c $$ ---------------------- $$ | . 2 7 O . . . . . . $$ | 1 3 X X O . . . . . $$ | . X O O . O . . . . $$ | 6 8 X O . . . . . . $$ | 4 . X O . . . . . . $$ | 5 X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

Click Here To Show Diagram Code: [go]$$B Hanging 2a $$ ---------------------- $$ | . 1 . O . . . . . . $$ | 2 . X X O . . . . . $$ | 3 X O O . O . . . . $$ | a 6 X O . . . . . . $$ | 4 . X O . . . . . . $$ | 5 X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

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

It took me 6 variations (and a few more to check, like

at

) to find the solution and the longest had 8 moves before I could clearly see the result.

6x8 is a fairly big number but I've had much bigger numbers, up to 9 variations with up to 13 moves, so this hard problem was not among the hardest.

However ... while writing down this example, it dawned upon me that Black makes a sacrifice.

Click Here To Show Diagram Code: [go]$$B Extra $$ ---------------------- $$ | . 1 . O . . . . . . $$ | 3 a X X O . . . . . $$ | . X O O . O . . . . $$ | . 4 X O . . . . . . $$ | 2 . X O . . . . . . $$ | . X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

What about this? White takes the 4 stones or Black has to play a ko that risks the whole group. Suddenly the problem becomes more complex.

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

This has to be checked too.

Click Here To Show Diagram Code: [go]$$B Hard 1 $$ ---------------------- $$ | . 1 8 O . . . . . . $$ | 4 6 X X O . . . . . $$ | 9 X O O . O . . . . $$ | 3 . X O . . . . . . $$ | 2 7 X O . . . . . . $$ | 5 X X O . . . . . . $$ | . O O . . . . . . . $$ | . . . . . . . . . . $$ | . O . . . . . . . . $$ | . . . . . . . . . .[/go]

As does this reversion to the solution.

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

And this ... 4 extra diagrams.

RobertJasiek · Post by **RobertJasiek** » Sun Jul 26, 2020 2:27 pm

If you dont't call it width, it is fine.

We both want to consider a number of variations that must be read.

Depth as length of variations is less interesting because we need not always consider branches at each move.

Reading also requires decision-making between different variations.

Life In 19x19

Complexity as width x depth

Complexity as width x depth

Re: Complexity as width x depth

Re: Complexity as width x depth

Re: Complexity as width x depth

Re: Complexity as width x depth

Re: Complexity as width x depth