It is currently Thu Sep 24, 2020 2:03 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 6 posts ] 
Author Message
Offline
 Post subject: Complexity as width x depth
Post #1 Posted: Sun Jul 26, 2020 12:09 pm 
Gosei
User avatar

Posts: 1717
Location: Ghent, Belgium
Liked others: 267
Was liked: 793
Rank: KGS 2d OGS 1d Fox 4d
KGS: Artevelde
OGS: Knotwilg
Online playing schedule: UTC 18:00 - 22:00
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 :b1:. Playing :b1: 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 ( :b1: at :w2: ) doesn't work and :b1: does. This time however it requires experience to assess the results of these two variations. In the failed variation, Black can still play :b3: 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.

:w2: at :b3: is 1 variation and best for both. :b1: at :w2: 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.


Last edited by Knotwilg on Sun Jul 26, 2020 12:52 pm, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Complexity as width x depth
Post #2 Posted: Sun Jul 26, 2020 12:36 pm 
Tengen

Posts: 5056
Liked others: 0
Was liked: 698
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.

Top
 Profile  
 
Offline
 Post subject: Re: Complexity as width x depth
Post #3 Posted: Sun Jul 26, 2020 12:56 pm 
Gosei
User avatar

Posts: 1717
Location: Ghent, Belgium
Liked others: 267
Was liked: 793
Rank: KGS 2d OGS 1d Fox 4d
KGS: Artevelde
OGS: Knotwilg
Online playing schedule: UTC 18:00 - 22:00
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?

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


I don't understand this.

Top
 Profile  
 
Offline
 Post subject: Re: Complexity as width x depth
Post #4 Posted: Sun Jul 26, 2020 1:15 pm 
Honinbo

Posts: 10200
Liked others: 3438
Was liked: 3290
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.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

My two main guides in life:
My mother and my wife. :)

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Complexity as width x depth
Post #5 Posted: Sun Jul 26, 2020 1:47 pm 
Gosei
User avatar

Posts: 1717
Location: Ghent, Belgium
Liked others: 267
Was liked: 793
Rank: KGS 2d OGS 1d Fox 4d
KGS: Artevelde
OGS: Knotwilg
Online playing schedule: UTC 18:00 - 22:00
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]


:b1: 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 :w4: at :b7:) 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.

Top
 Profile  
 
Offline
 Post subject: Re: Complexity as width x depth
Post #6 Posted: Sun Jul 26, 2020 2:27 pm 
Tengen

Posts: 5056
Liked others: 0
Was liked: 698
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group