It is currently Mon Sep 01, 2025 9:41 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 12 posts ] 
Author Message
Offline
 Post subject: A little game of perhaps some interest
Post #1 Posted: Wed Apr 22, 2020 7:28 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
While observing the discussion on the topic, "Indefinite improvement" for AlphaZero-like engines ( https://lifein19x19.com/viewtopic.php?f=18&t=17397 ) between lightvector and moha, I came up with the following little game.

The game is played with stacks of Blue chips and stacks of Red chips on a table. Two players, Black and White, take turns removing one or more chips from the table. At the end of play the player who has collected more chips wins. Black plays first. The game may be played with komi.

On her turn Black may take one stack of Blue chips off the table, or take the top chip from one of the Red stacks. Similarly, on his turn White may take one stack of Red chips off the table, or take the top chip from one of the Blue stacks.

That's it. :) So what's the best strategy and proper komi? :D

----

Mike Novack pointed out that the number of chips in each stack matters and that for stacks with only one chip in them, the color of the chip does not matter. :)

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #2 Posted: Wed Apr 22, 2020 7:37 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
To get started on what's the best strategy, here is a game with two stacks of chips. The Blue stack has one chip and the Red stack has 3 chips. Black to play.

----

Game 2. The Blue stack has 3 chips and the Red stack has 1 chip. Black to play.

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #3 Posted: Wed Apr 22, 2020 10:16 am 
Lives in gote

Posts: 502
Liked others: 1
Was liked: 153
Rank: KGS 2k
GD Posts: 100
KGS: Tryss
Game 1

Black take one chip from the red stack, then if white take the red stack, the game end with 2-2, and if it take the blue chip, the game end with 2-2 too after black take the top chip, then white take the last chip

So komi is 0


Game 2

Here black strategy don't matter :

If black take the 3 blue chips, white take the last red ship, and the game end with 3-1

If black take the red chip, white take a blue ship, then black take the last 2 blue chips

So komi is 2


But what of game 1+2? Two blue stack with 1 and 3 chips, and two red stack with 1 and 3 chips.

Black can't win, as white can always play a symetrical move, and if white break the symetry, black can play mirrors moves too. Correct seki is 0



And what of game 1+1? Two blue stack with 1 chip and two red stack with 3 chips

Black remove one red chip, white take the stack of 2 red chips, Black remove one red chip, white take the stack of 2 red chips, Black take one blue chip, and white take the last blue chip

Komi : -2 pts


And game 2+2? Two blue stack with 3 chip and two red stack with 1 chips

Black remove one blue stack, white take one blue chip, Black remove the blue stack, white take one red chip, black take the last red chip
Komi : 4 pts


This post by Tryss was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #4 Posted: Thu Apr 23, 2020 11:10 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
Thanks, Tryss. Nice idea to double the games. :)

Still looking for strategy, here are a couple of more games.

Game 3. There is one stack of 5 blue chips and one stack of 4 red chips.

Game 4. There is one stack of 4 blue chips and one stack of 5 red chips.

Game 5. There is one stack of 3 blue chips and four stacks of 2 red chips.

Game 6. There is one stack of 3 red chips and four stacks of 2 blue chips.

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #5 Posted: Fri Apr 24, 2020 7:43 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
Game 3. There is one stack of 5 blue chips and one stack of 4 red chips.

Well, if Black takes the Blue stack, White will take the Red stack and Black wins by 1. But what if Black takes the top red chip? Now if White takes the Red stack, the Black takes the Blue stack and wins by 2. So let Red take the top Blue chip, leaving a stack of 4 blue chips and a stack of 3 red chips, with each player having taken one chip. This is a similar situation to the start. If Black takes the Blue stack he will win by 1. What if Black takes the top red chip? Then White takes the top blue chip, leaving a stack of 3 Blue chips and 2 Red chips, with each player having the same number of chips in hand. By similar reasoning we can come down to a stack of 2 Blue chips and a stack of 1 Red chip. However she play Black will win by 1.

So there seem to be two basic strategies. 1) Take your own stack if it has more chips in it; 2) Take the top chip from your opponent's stack. With best play the end result is the same, but strategy 2) gives the opponent the chance to make a mistake.

Game 4. There is one stack of 4 blue chips and one stack of 5 red chips.

Here if Black takes her own stack, she loses, but if she takes the top Red chip she wins by 1.

So, somewhat counterintuitively, the simple strategy of taking one chip from the opponent's stack seems to be the best strategy we have found so far. ;)

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #6 Posted: Fri Apr 24, 2020 3:40 pm 
Dies with sente

Posts: 91
Liked others: 8
Was liked: 29
Bill Spight wrote:
So, somewhat counterintuitively, the simple strategy of taking one chip from the opponent's stack seems to be the best strategy we have found so far. ;)

But you did not yet do the Game 5 homework.
It follows that Black should take his own stack of 3 in that case. (In Game 6 the first move does not matter.)
By the way: the difference between Black starting and White starting in a given position (that is, interchanging Red and Blue) is always 0 or 2.


This post by vier was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #7 Posted: Fri Apr 24, 2020 4:10 pm 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
vier wrote:
Bill Spight wrote:
So, somewhat counterintuitively, the simple strategy of taking one chip from the opponent's stack seems to be the best strategy we have found so far. ;)

But you did not yet do the Game 5 homework.
It follows that Black should take his own stack of 3 in that case. (In Game 6 the first move does not matter.)
By the way: the difference between Black starting and White starting in a given position (that is, interchanging Red and Blue) is always 0 or 2.


For extra credit, what is special about four stacks of 2 chips of the same color? Also, do you see the relevance of these games to go?

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #8 Posted: Sat Apr 25, 2020 2:26 am 
Lives in gote

Posts: 502
Liked others: 1
Was liked: 153
Rank: KGS 2k
GD Posts: 100
KGS: Tryss
Bill Spight wrote:
Also, do you see the relevance of these games to go?


Your game 3 in a go setting :
Click Here To Show Diagram Code
[go]$$c Black to play, territory scoring
$$ ---------------------------------------
$$ | . . . . . . O . . . . . |
$$ | X X X X X X O O O O O O |
$$ | . . . . . X . . . . . O |
$$ ---------------------------------------[/go]


Or

Click Here To Show Diagram Code
[go]$$c Black to play, area scoring
$$ ---------------------------------------
$$ | . . . . . O . . . . |
$$ | X X X X X O O O O O |
$$ | . . . . X . . . . O |
$$ ---------------------------------------[/go]


This post by Tryss was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #9 Posted: Sat Apr 25, 2020 3:45 pm 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
Well, the cat is out of the bag. These games are equivalent to closed empty corridors in go by area scoring. Go players understood them long before combinatorial game theory. However, they may be taken as prototypes for fractional errors at chilled go, and as examples for "rounding", both of which came up in the discussion. :)

Anyway, here is Game 1, as a go game.

Click Here To Show Diagram Code
[go]$$ Game 1
$$ --------------------
$$ . . X C O C C C X . .
$$ . . X X O O O O X . .
$$ . . . . . . . . . . .
$$ . . . . , . . . . . .[/go]


The game is scored on the :ec: points. The Black corridor corresponds to the stack with 1 Blue chip, the White corridor corresponds to the stack with 3 Red chips. OC, go players know how to play this game.

Click Here To Show Diagram Code
[go]$$ Game 1
$$ --------------------
$$ . . X 3 O . 2 1 X . .
$$ . . X X O O O O X . .
$$ . . . . . . . . . . .
$$ . . . . , . . . . . .[/go]


The result by area scoring is 2 pts. for Black and 2 pts. for White, for a net score of 0.

Game 2 is the mirror image of Game 1.

Click Here To Show Diagram Code
[go]$$ Game 2
$$ --------------------
$$ . . X . . 1 O 2 X . .
$$ . . X X X X O O X . .
$$ . . . . . . . . . . .
$$ . . . . , . . . . . .[/go]


The result is 2 pts. for Black.

Go players also know the mean value of these games. It is -1¾ for Game 1 and +1¾ for Game 2, from Black's perspective, for both area and territory scoring. Black to play rounds up the score in Game 1 to 0 by area scoring, -1 by territory scoring, and she rounds up the score in Game 2 to +2 in both forms of scoring. Note that the rounding in territory scoring is to the next integer, to the next even integer in area scoring. (OC, if we were scoring on an odd number of empty point the area score would round to an odd integer.)

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #10 Posted: Sat Apr 25, 2020 4:36 pm 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
What about the games with four stacks of 2 chips of the same color? They are equivalent to a final integer score of +2 or -2, so there is no rounding to be done on them.

Click Here To Show Diagram Code
[go]$$ 2 pts. for White
$$ ------------------------
$$ . . O O O O O O O O O . .
$$ . . O . O . O . O . O . .
$$ . . O . O . O . O . O . .
$$ . . X X X X X X X X X . .
$$ . . . . . . . . . . . . .
$$ . . . . . . . . . . . . .[/go]


It does not matter who plays first, White can always guarantee 2 pts. in the corridors and Black can always guarantee no more than 2 pts. for White there.

Click Here To Show Diagram Code
[go]$$ Black first
$$ ------------------------
$$ . . O O O O O O O O O . .
$$ . . O 5 O . O 6 O . O . .
$$ . . O 1 O 2 O 3 O 4 O . .
$$ . . X X X X X X X X X . .
$$ . . . . . . . . . . . . .
$$ . . . . . . . . . . . . .[/go]


Result: -2

Click Here To Show Diagram Code
[go]$$W W first
$$ ------------------------
$$ . . O O O O O O O O O . .
$$ . . O . O 5 O . O 6 O . .
$$ . . O 1 O 2 O 3 O 4 O . .
$$ . . X X X X X X X X X . .
$$ . . . . . . . . . . . . .
$$ . . . . . . . . . . . . .[/go]


Result: -2

----

This example illustrates that the sum of four small errors may not have a wider variation than a single error, the sum may have no variation at all under territory or area scoring. :o This is why the rounding of mean values is possible, unless kos widen the variation.

Now the discussion that prompted this was about Elo values as play approaches perfection. IIUC, the tight bounds of the scores, which are in turn the sums of errors, violate the assumptions of the Elo system when the errors are less than 1 pt. (I know next to nothing about the Elo system, myself. :))

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #11 Posted: Sun Apr 26, 2020 12:56 pm 
Lives in gote

Posts: 311
Liked others: 0
Was liked: 45
Rank: 2d
Bill Spight wrote:
Black to play rounds up the score
This was the point that seemed problematic the other thread. If rounding direction depends on sente, then 6.1+sente is better than 6.7+gote. If there is no rounding in chilled go, then correct play there (which presumably maximizes the chilled/fractional score) is not necessarily correct play in territory even without kos. OC not likely for two similar scores to have different dame parities and roundings, but still seems possible if an early decision is between choices that lead / doesn't lead to seki. Where is the flaw in this reasoning?

Top
 Profile  
 
Offline
 Post subject: Re: A little game of perhaps some interest
Post #12 Posted: Sun Apr 26, 2020 2:12 pm 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
moha wrote:
Bill Spight wrote:
Black to play rounds up the score
This was the point that seemed problematic the other thread. If rounding direction depends on sente, then 6.1+sente is better than 6.7+gote. If there is no rounding in chilled go, then correct play there (which presumably maximizes the chilled/fractional score) is not necessarily correct play in territory even without kos. OC not likely for two similar scores to have different dame parities and roundings, but still seems possible if an early decision is between choices that lead / doesn't lead to seki. Where is the flaw in this reasoning?


How do you define a fractional error under territory or area scoring? I can define a fractional error as one that results in a fractional difference in the final score, assuming correct play otherwise. IOW, I can define it only for chilled go, because chilled go has fractional scores.

What is true is that, without ko complications, the fractional scores of chilled go are equal to the mean values of territory and area scoring. Those mean values are estimates of the final territory or area scores, which are integers before applying komi. I do think, as estimates, that the size of the fraction indicates which way the final integer score will likely turn out. An estimate of 0.2 is, given correct play up to the end of the game, more likely to become an integer score of 0 than an integer score of 1, and an estimate of 0.6 is more likely to become an integer score of 1 than an integer score of 0. (I haven't tried to check that out, but it is an empirical question.) So, yes, sometimes a fraction in chilled go will "round" to the more distant integer in territory and area scoring.

However, it is not true that, given correct play after the fractional errors have occurred, and no ko complications, a smaller chilled go fraction will round up while a larger chilled go fraction will round down. The reason is that each possible fraction between the same integers will round in the same direction. And the reason for that is the phenomenon of reverses. Suppose, with correct play, that Black has the move and makes a play that gains so much and then White makes a play that gains more than that. That is something that would be necessary for the fractional chilled score to round down instead of up. But in that case Black has a play or sequence of play that will gain at least as much as she has lost so far. Were that not so, Black's initial play would have been a mistake. Now, kos can cause Black to lose points, even with correct play, but that's another question. There is an example in the Mueller, Berlekamp, Spight paper of 1996. I think it is available on Martin's web site.

Edit: In terms of the thermograph, with no kos, the Left wall, which indicates the minimax results at each temperature when Black plays first, consists of 0 or more vertical line segments and 1 or more line segments at 45° with the Black score increasing as the temperature drops. If the chilled score rounds down, the final line will be vertical at the final integer score, with an intersection below temperature 1. If the chilled score rounds up, the final line will be at 45°. again with an intersection below temperature 1. For the chilled score that rounds down to be greater for Black than the chilled score that rounds up, these two lines would have to intersect below temperature 1. No es possible.

Using rounding to 0 or 1 the possible thermographic lines that round down look like this up to temperature 1.

Code:
Rounding down to 0
______________________ T = 1
            /
           |
           |
___________|___________ T = 0
           0


Code:
Rounding up to 1
______________________ T = 1
          | 
         /   
        /   
_______/_______________ T = 0
     1     


At T = 1 the Left scaffold will be at a fraction less than 0 when the fraction rounds down to 0 and at a fraction greater than 0 when the fraction rounds up to 1. That mean that when both are possible from the same starting position, the sequence that rounds to 1 will dominate the sequence that rounds to 0 at these temperatures, and the chilled go score will be for the score that rounds to 1.

Edit2: For people who are unfamiliar with thermography, which will probably be most of you, the thermographic lines represent plays or lines of play in the game. The two parts of scaffolds here represent lines of play starting from two different options that Black can choose to play, to which White has already chosen his replies to minimize the results for Black at each temperature. Black then chooses her options to maximize the results at each temperature. See https://senseis.xmp.net/?TemperatureCGT .

At territory scoring Black tries to maximize the result at temperature 0, i.e., when any plays in the background are dame. In chilled go Black tries to maximize the result at temperature 1. The graphs show that when the choice Black has is between an option that "rounds" to 0 at territory scoring (temperature 0) and one that rounds to 1 at territory scoring, which Black will choose at territory scoring, Black also maximizes her score at chilled go (temperature 1) by making the same choice. (Assuming no ko complications, OC. ;))

Edit3: There is an apparent paradox here, in that the estimate of the final territory score, which we get by projecting the lines at temperature 1 down to temperature 0, may be greater for the scaffold that rounds to 0 than for the estimate for the scaffold that rounds to 1. How can that option be less for chilled go than the one that gives a lower estimate? The answer lies in the inclination of the line at temperature 1. The line for the result that gets rounded to 1 is vertical, which means that White has made the same number of moves and Black, but the line for the result that gets rounded to 0 is inclined, which means that Black has made one more move than White. Chilling penalizes Black one point for that extra play. ( https://senseis.xmp.net/?Chilling ). That's why the chilled go result is less.

For instance, suppose that one line of play estimates the territory result to be ¾ but gets rounded down to 0 and other line of play estimates the territory result to be ½ but gets rounded up to 1. The one that estimates a result of ¾ by territory scoring has a chilled go score of -¼, while the one that gets rounded up to 1 has a chilled go score of ½.

This failure to distinguish between the estimated territory score and the chilled go score is my fault. I just never thought about it before. :oops: :oops: :oops: It is the estimate that gets rounded up or down, not the chilled go score. I misunderstood David Wolfe's comment to me years ago.

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

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 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:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group