It is currently Thu Jul 09, 2020 1:46 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 8 posts ] 
Author Message
Offline
 Post subject: Difference games for whole board play
Post #1 Posted: Mon Nov 25, 2019 3:53 am 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
Difference games have long been used to compare endgame plays in independent regions of the board. Using them for the whole board seems ridiculously impractical.

But that's on the 19x19, which is hard enough given 361 points. Forget 722 points on two boards! ;) How about the 9x9? 2*81 = 162, less than half the size of the 19x19. Or even the 13x13? 2*169 = 338, still less than 361.

It is not that we know perfect play on these boards. But perfect play may not be necessary to tell that one play is better than another. Good enough play may do. :)

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #2 Posted: Mon Nov 25, 2019 8:50 am 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
I have already used a whole board difference game for mirror go on the 3x3 at https://lifein19x19.com/viewtopic.php?p=250500#p250500 .

Here is an example for the choice of opening play.

Difference game setup. Black will make one of the opening moves, White will make the other one on the other board.

Click Here To Show Diagram Code
[go]$$ Black first — White first
$$ ---------------
$$ | . . . | . . W |
$$ | . , B | . , . |
$$ | . . . | . . . |
$$ ---------------[/go]


For those not familiar with difference games, we start from a position worth exactly 0. The boards are independent, and the second player can always copy the first player's moves on the other board to keep the score the same. To ensure this, the ko or superko rule has to apply to each board separately, and ending play on one board does not end play on the other.

After the game is set up, as above, there are four possibilities. 1) The plays are equivalent, so the score is still 0. In that case the result with be 0 with correct play, no matter who plays first. 2) The Black play is better than the White play. In that case Black to play can win, while White to play can at best make jigo. 3) The White play is better. 4) The plays are not equivalent, but we cannot say that one play is better than the other. In that case each player can win playing first. We may still prefer one play over the other, based on other criteria. IMO, many plays on the 19x19 board, especially in the opening, are of this kind. There may be several plays in a group, none of which is better than the other. :)

OK. In this case we believe that Black's play is better. So Black to play should win. Let's see.

Click Here To Show Diagram Code
[go]$$B Black plays first
$$ ---------------
$$ | . 4 . | . . W |
$$ | 3 2 B | . 1 . |
$$ | . 5 . | . . . |
$$ ---------------[/go]


:b1: wins on the right hand board, then :w2: makes seki on the left hand board. By area scoring Black has 9 pts. on the right and 5 pts. on the left, and White has 2 pts. on the left. Black wins on the combined boards by 12 pts. By territory scoring Black has 9 pts. on the right plus 0 or 2 pts. on the left, depending on whether you count points in seki. Black wins on the combined boards by 9 or 11 pts. So Black to play wins the difference game.

Now let White play first in the difference game.

Click Here To Show Diagram Code
[go]$$W White plays first
$$ ---------------
$$ | . . . | . . W |
$$ | . 2 B | . 1 . |
$$ | . . . | . . . |
$$ ---------------[/go]


:w1: wins on the right hand board, then :b2: wins on the left. Each player gets the same number of points, for jigo.

Click Here To Show Diagram Code
[go]$$W White first, variation
$$ ---------------
$$ | . 3 . | . . W |
$$ | . 1 B | . 2 . |
$$ | . . . | . . . |
$$ ---------------[/go]


White starts on the left hand board. :b2: wins on the right, then :w3: wins on the left. The result is jigo by area scoring, Black +1 by territory scoring. In any event, White to play cannot win the difference game. So :bc: is a better play than :wc:. QED. :)

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.


Last edited by Bill Spight on Mon Nov 25, 2019 2:06 pm, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #3 Posted: Mon Nov 25, 2019 9:29 am 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
We have shown with a difference game that the first move on the 3x3 should not be in the corner. As if we didn't know. ;) Now let's compare the tengen opening with the side opening. By area scoring or territory scoring that counts territory in seki, either play should win. Is one play better than the other in terms of difference games?

Click Here To Show Diagram Code
[go]$$W Difference game setup
$$ ---------------
$$ | . . . | . . . |
$$ | . B . | . , W |
$$ | . . . | . . . |
$$ ---------------[/go]


Click Here To Show Diagram Code
[go]$$B Black first
$$ ---------------
$$ | . . . | . 3 . |
$$ | . B . | 2 1 W |
$$ | . . . | . 4 . |
$$ ---------------[/go]


By area scoring Black gets 9 pts. on the left and 2 pts. on the right for 11 pts. White gets 5 pts. on the right. Black wins by 6 pts. By territory scoring that counts points in seki, Black also wins by 6 pts. Black to play wins the difference game.

Click Here To Show Diagram Code
[go]$$W White first
$$ ---------------
$$ | . . . | . . . |
$$ | . B . | . 1 W |
$$ | . . . | . . . |
$$ ---------------[/go]


:w1: wins on the right hand board. The result is jigo by area scoring, Black +1 by territory scoring.

Click Here To Show Diagram Code
[go]$$W White first, variation
$$ ---------------
$$ | . 2 . | . . . |
$$ | . B 1 | . 3 W |
$$ | . . . | . . . |
$$ ---------------[/go]


:w1: starts on the left hand board, and :b2: replies to retain the win there. Then :w3: wins on the right. The result is the same as above.

Black to play wins the difference game while White to play cannot win. So :b1: is better than :w2:. :)

Note that :b2: is not best play in the variation.

Click Here To Show Diagram Code
[go]$$W White first, variation 2
$$ ---------------
$$ | . 4 . | . 5 . |
$$ | . B 1 | 3 2 W |
$$ | . . . | . 6 . |
$$ ---------------[/go]


After :w1: :b2: wins the difference game by area scoring. But :b2: in the first variation is good enough play to get at least jigo. Good enough play will do.

Now, we are told that the bots do not think about go the same as humans, they think better than we do. The probability of winning matters, not the margin of victory. But difference games show that the margin of victory does matter. Maybe humans are on to something. ;)

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #4 Posted: Mon Nov 25, 2019 1:00 pm 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
Another question is whether one play is better than another if both plays lose. Let's compare plays on the 3x3 board after the tengen opening.

Click Here To Show Diagram Code
[go]$$W Difference game setup
$$ ---------------
$$ | . . . | . . W |
$$ | . O B | . X . |
$$ | . . . | . . . |
$$ ---------------[/go]


Black replies on the 2-1 point, White replies on the 1-1. Intuitively, the 2-1 reply seems better, but who knows?

Click Here To Show Diagram Code
[go]$$B Black plays first
$$ ---------------
$$ | . 2 . | . . W |
$$ | 1 O B | . X . |
$$ | . 3 . | . . . |
$$ ---------------[/go]


Obviously, Black to play wins the difference game.

Click Here To Show Diagram Code
[go]$$W White plays first
$$ ---------------
$$ | . 1 . | . . W |
$$ | . O B | . X . |
$$ | . . . | . . . |
$$ ---------------[/go]


White to play ties by area scoring, loses by territory scoring.

:bc: is a better play than :wc:.

Again, the margin of victory matters.

N. B. Combinatorial Game Theory (CGT) aficionados may have noted that the Black 2-1 reply reverses, because White's reply returns the 3x3 board to a position worth the same or worse for Black than the original position. I.e., Black to play cannot win the following difference game.

Click Here To Show Diagram Code
[go]$$W
$$ ---------------
$$ | . W . | . . . |
$$ | . O B | . O . |
$$ | . . . | . . . |
$$ ---------------[/go]


You can easily verify that that is the case.

CGT says that we can simplify a game tree by playing all reversals. The game tree in this case is that of the position after White opens on tengen. If we play through all reversals we can get the following difference game.

Click Here To Show Diagram Code
[go]$$W
$$ ---------------
$$ | . W . | . . W |
$$ | W O B | . X . |
$$ | . B B | . . . |
$$ ---------------[/go]


It is obvious that this is a 0 game. Neither player can win by playing first.

One reason for the reversal in this case is that the game is basically over after the tengen opening. The board is scorable.

But nothing forces the play of the reversal. The original difference game does indeed favor Black, so there is a sense in which the 2-1 response is better than the 1-1.

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #5 Posted: Wed Nov 27, 2019 9:18 am 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
One nice thing about difference games is that mirror positions are jigo. This fact can be used to short circuit search. :) For instance suppose that we are comparing replies to tengen on the 9x9. (On the 9x9 we can be fairly certain that there is no reversal.)

Click Here To Show Diagram Code
[go]$$B Difference game setup
$$ --------------------------------------
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . W . . | . . . . . . . . . |
$$ | . . . . X . . . . | . . . . O . B . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ --------------------------------------[/go]


We are comparing the 3-5 reply by Black with the 3-4 reply by White.

Click Here To Show Diagram Code
[go]$$B Black first
$$ --------------------------------------
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . 2 . . . . | . . . . . 1 . . . |
$$ | . . . . . . W . . | . . . . . . . . . |
$$ | . . . . X . . . . | . . . . O . B . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ | . . . . . . . . . | . . . . . . . . . |
$$ --------------------------------------[/go]


Suppose that Black starts off by playing the keima at :b1: on the right hand board. Then White can make jigo by playing the keima at :w2: on the left hand board, making a mirror position, for jigo. :w2: may not be the best play on the single board, but it is good enough play to prevent Black from winning the difference game by playing first. For her first play Black must avoid all eight 3-4 points on the right hand board and White must avoid all four 3-5 points on the left hand board. ;)

Another trap for Black.

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

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #6 Posted: Wed Nov 27, 2019 9:31 am 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
A few comments. :)

1) As I pointed out in the mirror go topic, single board komi does not matter, since it is negative on the mirror board, and komi - komi = 0. Komi in the difference game must be zero, as the second player is satisfied with jigo. (I suppose that you could give the second player komi of ½, but that seems unnecessary.)

A few years ago one of the go AI developers lamented a loss with a komi of 6½ (under territory scoring) because the bot had been trained with a 7½ pt. komi. I understood the problem, and I also understood training for the specific conditions of contest. But for myself I would want a more general and robust program. Like we have now with KataGo. :)

As for the use of neural nets for difference games, it may be OK to use neural nets that have been trained on a specific komi on each board, The top module might use information from both nets to choose the next play. How well such an architecture would work is, OC, an open question. ;)

2) Although, as we have seen, the margin of victory on a single board matters, but it does not matter in the difference game. So a program could play the difference game using MCTS, which does not care about the margin of victory. And even so we would be evaluating plays on a single board based upon the margin of victory.

3) Because each board mirrors the other before the two plays to be compared are made, the difference game is relatively impervious to imbalance on a single board. High handicap games are thus not problematic. OC, bots like KataGo can handle high handicaps by estimating territory. But the difference game does not require such an estimate, because of the mirroring. Unless one of the plays being compared is really bad, the difference game should normally be close. Besides, the margin of victory does not matter. :)

4) Difference games could be useful for whole board problems, such as Igo Hatsuyoron #120. This is not to take anything away from the wonderful work and results of Cassandra and other humans, and that of lightvector training KataGo. But the ability to focus the question on comparing two specific plays in a specific position, especially positions identified as critical, could be used to check and validate those results or to suggest other options. Difference games in themselves are too specific to solve problems or play games, but they provide a strong analytical tool. :)

5) What about training? My hope is that already trained neural nets could be used for each board without specific training for difference games. OC, training for difference games is almost certainly better, but by how much?

6) What about efficiency? We can compare two plays with a top bot simply by making each play and comparing results. But the bots are built to win games, not compare plays. Difference games are designed to compare plays and positions. But there is a large performance hit from doubling the search space. In practice that may be a big drawback.

7) What about accuracy? Simply having to win or not lose a difference game reduces the labor of finding a proof by orders of magnitude of that of finding perfect play. However, for boards of size 9x9 or larger, I think that doubling the search space dwarfs that reduction. That also means that we shall probably be left with statistical indications. Suppose, for instance, that move A is superior to move B, and that Black makes move A. Then we may well have a winrate for Black playing first greater than 99% with hundreds of thousands of playouts. But when White plays first maybe the optimal result is jigo. Then we might well have a winrate for White playing first of around 40% with the same number of playouts. That is a very weak indication that White should lose, playing first.

This may still provide a better indication than simply making each play on a single board. Then we might get a winrate for A of 45% versus a winrate for B of 37%. ;)

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.


Last edited by Bill Spight on Fri Jan 17, 2020 4:41 am, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #7 Posted: Mon Dec 02, 2019 12:22 pm 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
This topic has generated another idea, not for using mirror go for training AI, but a different way of training via self play. To me the advantages of difference games, aside from comparing specific plays, are their indifference to komi and handicaps and the importance of the the margin of victory on each board, while the game is a win/lose game. :)

It strikes me that you could train a bot by having two versions play two game matches, switching sides between games, where the two game match is decided by total points. So if version A lost by 5 points on the board in one game but won by 6 points in the other game, it would win the match. That might provide the robustness of difference games without affecting the search space. :)

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Difference games for whole board play
Post #8 Posted: Tue Jan 14, 2020 12:35 am 
Honinbo

Posts: 9953
Liked others: 3232
Was liked: 3254
Another thought. Difference games should still be useful for comparing plays and positions in the endgame, even on a 19x19 board. In the endgame the number of disputed points should be less than half the number at the start of play. That means that the effective search space in the difference game should be less than 361 pts. That should be doable. :)

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

Banana Republic. It's not just a store anymore.

Everything with love. Stay safe.

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

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: Shaddy 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