[Computer-go] When is a group not a group?
"I agree that group strength can't be a single number. That's why I classify groups instead. Each classification is treated differently when estimating territory, when generating candidate moves, etc. The territory counts depend on the strength of the nearby groups." this touches on an issue which is uppermost in my own mind at this stage. When is a group not a group? [answer: when Haylee rips it to shreds!]. Whereas i feel that, when playing, i envisage such a thing as a group, i do so because i was influenced by the theory of groups embodied in the Reitman-Wilcox program. From carefully listening to what Haylee has to say, it is unclear to me whether she thinks the same way. I plan to investigate this more deeply; my video series is not "Brown's Lectures on a fait-accompli" but rather a kind of freshman video blog, recording my trail of exploration as i plod along it at a snail's pace. Episode 14 uploaded: https://www.youtube.com/watch?v=OonbcgykmMk=14=PL4y5WtsvtduqNW0AKlSsOdea3Hl1X_v-S "Monte Carlo has a big advantage in that it estimates the probability of winning the game, rather than my old approach of trying to estimate the final score." Personally, i see win probability as a form of score estimation (ie move choice value estimation) . "I guess expert systems really are a dead end in Go. Too many contradicting heurestics " Oh, ye of little faith! :) It all depends on what you mean by "Expert System". Feigenbaum did for ES what Kurzweil is trying to do for Hidden Markov Models - ie popularise them to grab the attention of bankers. ESs did not live up to their over=the-top public press hype and the bankers became disenchanted at the same time that DARPA pulled the rug from under AI. But none of that means it is not a viable line of research. "The mid-term problem is not mutual contradiction of heuristics because their careful study can remove the contradictions and establish a hierarchy of principles. Only the problem of great number of principles to be coded and maybe of the complexity of time remain." There's nothing wrong with a bit of cognitive dissonance inconsistency; if you don't believe me ** - and most people do n't :) - ask Kurt Godel. **[eg that the first God invented by mankind was the female Moon; Jesus is a memetic descendant of the male Sun, etc https://www.youtube.com/watch?v=5lsQUq9EjLA=PL4y5WtsvtduooErlxg7h5dxQ2h2UALN0h=1 ] "I think we way underestimate how much complexity emerges from a single Go position, much less projecting that complexity forward temporally. " the complexity of a single position arises directly from its temporally descendant implications. Ouroboros. "give the MC strategy another good kick in the pants... to send it the rest of the way past the best human's ability. If so, that will be tragic as it means that just like Chess, brute force largely won...again." far from being tragic, it will be (should be) highly instructive when that happens, (as i anticipate it will, once an engine with the raw power of Watson gets onto it), as it will demonstrate that there is more to intelligence than being able, like Rain Man, to perform prodigious calculations within a closed-world microdomain like Go. I recommend reading anything John McCarthy has to say on this subject. -- http://sites.google.com/site/djhbrown2/home https://www.youtube.com/user/djhbrown ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[computer-go] when
test Folkert van Heusden -- MultiTail is een flexibele tool voor het volgen van logfiles en uitvoer van commando's. Filteren, van kleur voorzien, mergen, 'diff-view', etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] when to stop searching
If it's true, it's an indication of the properties of the game tree distrubution. If a first move is good, it leads to a favorable geometric position. Starting from a geometricaly favorable position more good random playing lines exist than bad random playing line(the number of the good random playing lines plus the number of the bad random playing lines equal to the total number of all possible playing lines). Actually the ladder may not be an exception. At each step of a ladder there are only two possible moves. One good and one may not be good. The chance is 50% or larger. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Sun, 11 Mar 2007 2:03 PM Subject: [computer-go] when to stop searching On 3/11/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: But to pick the best move, it's only necessary to recognize the weaknesses in all the other moves. In many cases these weaknesses can be recognized using move sequences that are far less than perfect play. The tricky part seems to be sequences can only be evaluated with perfect play for many moves such as ladders. It's unclear how often such perfection is required to pick the best move. Thus, one starts with an imperfect subset of moves and an imperfect evaluation function and feed them to a search algorithm (alpha-beta, for example). In general, the higher are the merit probabilities, the more effective is the search. With UTC, if I understand correctly, it would eventually try every possible sequence, but of course not within the time limit, so it isn't clear that it starts with an imperfect subset of moves that is separate from the other factors. AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] when to stop searching
I would add 4. The program tries to identify good moves, and only tries moves that it thinks might be good. If it is goal-directed, the good moves are good for a reason, and if the reason is not satisfied, they are discarded. This is the way Many Faces works. It's very similar to 3, but it's a different way of thinking about the problem (adding good moves rather than deleting bad ones). You are correct that this approach is inadmissible, and is self limiting. I like it because when I add new knowledge I know I'm making the program stronger. I don't like tuning parameters or algorithms and then playing hundreds of games to get statistically significant data on the better value. I'm not saying my approach better, just that I prefer it :) David 3. selective in the true sense. Such a program tries to identify bad moves and prune them from the tree, but they are pruned permanently. NO matter how deep or long you search they will never be considered. I think true selective programs, unless the pruning criteria is fully admissible, is self limiting. You can probably build a strong program but you will be bound strictly to the quality of your selective algorithm. Such an algorithm would play imperfectly even on an infinte speed computer. UCT is admissible - it will ALWAYS find a winning move if you are in a winning position. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] When is Pass the best move?
Well at least we can be sure that for any two person game, if a position occurs 3 times, at least 2 will have the same player to move ;-)ErikOn 11/8/06, John Tromp [EMAIL PROTECTED] wrote: The difference between PSK and SSK also comes up in chess.Witness these events taking place yesterday in the Tal Memorialchess festival in Moscow:Morozevich-Carlsen was interesting for a technical reason. White had some advantages but Carlsen locked up the position in sound defence.There was some shuffling around with the pieces, and at one stageMagnus Carlsen approached the deputy arbiter Eduard Dubov to announcethat he intended to play the move 46...Qc7 and produce the same position for a third time on the board. The chief arbiter GeurtGijssen was summoned and he started to check the game with Carlsen inthe analysis room. Gijssen also informed Morozevich about Carlsen'sclaim and invited him to join in the checking. But Morozevich refused. Carlsen and Gijssen replayed the game and came to the conclusion thatindeed the final position had occurred for a third time. A draw wasgiven and both players signed the scoresheets. Afterwards Gijssen had some doubts and again checked the game. It was then that he discoveredthat while the position had appeared three times on the board, it wasnot with the same player having the move. It means that the claim was wrong and my decision was wrong as well, writes Gijssen in hisreport. He informed Carlsen about this and the young Norwegian wasimmediately ready to continue the game. The organizers tried to reachMorozevich, but he was nowhere to be found. In the end his coach Kuzmin informed the organizers that, in his opinion, the draw shouldstand. And so it did.[http://www.chessbase.com/newsdetail.asp?newsid=3476] This is not the first occurrance of such confusion:In the twentieth game of the 1972 Bobby Fischer-Boris Spassky match(the Match of the Century), Fischer claimed a draw because ofthreefold repetition. Spassky did not dispute it and the arbiter agreed. After the draw had been agreed, it was pointed out that theposition had occurred after White's forty-eighth and fiftieth moves,and again after Black's fifty-fourth move (the final position). So the claim was actually invalid because it was not the same player's turnto move in all three instances (Alexander 1972:137-38).[http://en.wikipedia.org/wiki/Threefold_repetition ]Perhaps positions are more easily recognized than situations...regards,-John___computer-go mailing list computer-go@computer-go.orghttp://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] When is Pass the best move?
At 01:54 23/10/2006, you wrote: There was a posting on this list with an example of a (contrived?) situation where sacrificing a pass-alive group is appropriate, in order to win a ko that is more valuable. Is even #1 100% admissible? Weston I must have missed this, and find it surprising. Can anyone remember the example? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] When is Pass the best move?
When someone mentioned a position where a pass-alive group should be sacrificed - I wondered if it was also due to PSK issues. I want to clarify something I said about PSK. I don't think the rule is wrong in any sense - after all you can make up any rules you want as long as they are internally consistent. I just believe it's a rather arbitrary rule which has been accepted primarily because it rarely turns out to make a difference in most situations. For instance, I could add a rule to chess which says it's illegal to move a bishop to g2 on the 8th move. It would be a rather silly and arbitrary rule and wouldn't be consistent with the spirit of the game, and it would introduce a small bias against white for no good reason - but it would be a valid rule and the game could still be played reasonably. However it would be an ugly wart on the game. (Chess has a lot of funny rules in it anyway which have been added over the years to improve the game.) - Don On Mon, 2006-10-23 at 11:56 +0200, Erik van der Werf wrote: On 10/23/06, Tom Cooper [EMAIL PROTECTED] wrote: At 01:54 23/10/2006, you wrote: There was a posting on this list with an example of a (contrived?) situation where sacrificing a pass-alive group is appropriate, in order to win a ko that is more valuable. Is even #1 100% admissible? Weston I must have missed this, and find it surprising. Can anyone remember the example? I probably posted that; it is a superko anomaly. . O O # # # O O . O . O # . # O O # O O # . # O O # . # # # # # O O # # O O O O # # O O . . . O # # # # O O O O # # O O O # O O . O # O . O # # O . O # O O . # . 9x9 board, superko, area scoring, 6 komi for White It does not matter who plays first. Assuming that the players agree that white's upper left group is dead the position can be scored as it stands (jigo). Solution at http://www.cs.unimaas.nl/~vanderwerf/pubdown/stelling3.sgf Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] When is Pass the best move?
On Mon, 2006-10-23 at 16:01 -0200, Mark Boon wrote: On 23-okt-06, at 14:23, Don Dailey wrote: Then all the nonsense goes away. It then comes down to each player having his fate in his own hands.If you want to win, you will avoid cycles, That's a rather bizarre proposal. Ko is so common in Go. It would mean that he who is ahead would have to concede every possible ko, even some extremely unreasonable ones. In those cases where the game balances on the ko (which is a high percentage) you'd get a draw. I'm not very good at GO, but I would assume that it would change the game some. But it would be a change that was adjusted to. Knowing how to avoid these situations would be part of a good players strategy. How bad would it be? Would it create a situation where good players couldn't beat significantly weaker players any longer? By the way, I'm not really proposing this. I'm just thinking out loud. - Don Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] When is Pass the best move?
I'm just looking for a way out of the KO ugliness as a mental exercise. There appears to be no way unless the game is changed significantly. You could just allow simple KO under the same circumstances of move or time limited games. - Don On Mon, 2006-10-23 at 22:00 +0200, John Tromp wrote: On 10/23/06, Don Dailey [EMAIL PROTECTED] wrote: I'm not very good at GO, but I would assume that it would change the game some. But it would be a change that was adjusted to. Knowing how to avoid these situations would be part of a good players strategy. Some is an understatement. It would change the game quite a bit, since almost every game features kos, not only in actual play, but also in the considerations of both players. How bad would it be? Would it create a situation where good players couldn't beat significantly weaker players any longer? Yes; you can argue about the value of being able to win all kos in terms of handicap stones. I think it would be well over 4 stones. Being able to invade and create moonshine life is quite a perk. Could be a fun experiment to put to the test:) regards, -John ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] When is Pass the best move?
During the main search, pass is always one of the moves searched, and if is the best move found, and pass is allowed, it will play a pass. I never avoid searching pass in the main search since it gives a good lower bound on the score. If the search returns pass too early, I'll play the second best move instead. Many Faces of Go uses the following rules: - pass is always allowed if the opponent passed on the previous move otherwise - pass is allowed if the move number is at least half the board size (181 on a full size board) and the pass search found no good moves for the opponent. Before I do the main search for the color to move, I do a pass search for the opponent, to find good opponent moves if the color to move passes. These moves are searched early in the main search. I'm trying to find killer moves early. David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Don Dailey Sent: Sunday, October 22, 2006 5:08 PM To: computer-go Subject: Re: [computer-go] When is Pass the best move? I'm in a similar situation, I'm trying to identify classes of moves that I can eliminate in an admissible way - which means the move I am throwing out is either not the best move, or there are other equally good moves. I know that pass moves can be the best move in seki situations - and it's non-trivial how to identify them. I'm not good at go and this is a severe handicap for me, but here is what I come up with so far - please add to my list if you know of anything else: 1. Benson space - I use benson's algorithm to find pass-alive groups and if a small region is enclosed completely by benson groups, there is never a point moving inside of them for either color (except in cleanup situations for Chinese rules) A region is defined as strings of points that can consist of any combination of enemy stones and empty intersections. A large region can exist inside benson safe groups that allows for life - so care must be taken that you identify the correct regions. I don't know if I'm doing it the most efficient way, but I'm going by region size. A region of 7 inside a benson group cannot possibly support enemy life. So moves inside them by either color do not improve the position. 2. I have a quick and dirty pass rule - I throw out all pass moves in the early part of the game. I can't prove this rule is admissible but I feel very safe with a rule like, don't allow pass if half the points on the board are empty. I feel you can probably be a lot less conservative - but if anyone knows a way to identify when to start including pass moves in a search in a theoretically sound way - I'm all ears! 3. Unfortunately, the eye-filling rule is not admissible other than in benson situations. The eye-filling rule I use has been described on this group - don't move to a point surrounded on all sides by stones of the same color - where the opponent doesn't occupy more than 1 diagonal (different if on edge of board.) I may or may not use this rule depending on what I'm trying to do. 4. Don't move to any of the corner points on the first move. Right not I'm working on a perfect solver for 5x5 - and rule 1 and 2 are the only rules I know that are 100% admissible. I suspect rules 2 and 4 are admissible - at least on 5x5 or larger although I cannot back that up with any theory. Rule 4, the corner rule can probably be generalized - and I think that's what a good pattern database might be able to do.I would like to be able to build an admissible pattern database of the form that veto's specific moves.But the database must be provably correct, not built based on a humans intuition that a move is probably not good. So I'm basically lost here. my solver is just a step towards the goal of a pattern database that can admissibly remove many pointless moves from a tree search. - Don On Sun, 2006-10-22 at 10:47 -0700, Phil G wrote: Does anyone have an example where pass is the best move, and not part of the two passes to end the game? I'm trying to determine if passes should ever be considered in a search for the best move, and if so, how to exclude them until it is really necessary. Thanks, Phil ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http
