Life In 19x19 http://www.lifein19x19.com/ |
|
Difference games for whole board play http://www.lifein19x19.com/viewtopic.php?f=15&t=17082 |
Page 1 of 1 |
Author: | Bill Spight [ Mon Nov 25, 2019 3:53 am ] |
Post subject: | Difference games for whole board play |
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! ![]() 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. ![]() |
Author: | Bill Spight [ Mon Nov 25, 2019 8:50 am ] |
Post subject: | Re: Difference games for whole board play |
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. 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. ![]() ![]() Now let White play first in the difference game. ![]() ![]() White starts on the left hand board. ![]() ![]() ![]() ![]() ![]() |
Author: | Bill Spight [ Mon Nov 25, 2019 9:29 am ] |
Post subject: | Re: Difference games for whole board play |
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. ![]() 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. ![]() ![]() ![]() ![]() Black to play wins the difference game while White to play cannot win. So ![]() ![]() ![]() Note that ![]() After ![]() ![]() ![]() 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. ![]() |
Author: | Bill Spight [ Mon Nov 25, 2019 1:00 pm ] |
Post subject: | Re: Difference games for whole board play |
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. Black replies on the 2-1 point, White replies on the 1-1. Intuitively, the 2-1 reply seems better, but who knows? Obviously, Black to play wins the difference game. White to play ties by area scoring, loses by territory scoring. ![]() ![]() 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. 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. 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. |
Author: | Bill Spight [ Wed Nov 27, 2019 9:18 am ] |
Post subject: | Re: Difference games for whole board play |
One nice thing about difference games is that mirror positions are jigo. This fact can be used to short circuit search. ![]() We are comparing the 3-5 reply by Black with the 3-4 reply by White. Suppose that Black starts off by playing the keima at ![]() ![]() ![]() ![]() Another trap for Black. |
Author: | Bill Spight [ Wed Nov 27, 2019 9:31 am ] |
Post subject: | Re: Difference games for whole board play |
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%. ![]() |
Author: | Bill Spight [ Mon Dec 02, 2019 12:22 pm ] |
Post subject: | Re: Difference games for whole board play |
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. ![]() |
Author: | Bill Spight [ Tue Jan 14, 2020 12:35 am ] |
Post subject: | Re: Difference games for whole board play |
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. ![]() |
Page 1 of 1 | All times are UTC - 8 hours [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |