Re: [computer-go] an idea... computer go program's rank vs time
It is true that MC-programs has a bias towards overconcentration. But... 1) A improvements to the simulations of MC-program as implemented by MoGo and Valkyria does diminish the problem. In fact most of the strength of these programs from doing that. I think it is next to possible to explicitly program the concept of overconcentration, but fortunately you do not have to. The problem goes away when you fixed other more immediate problems with the simulations. 2) Deeper search makes these programs stronger. Valkyria always get stronger with increased search. Just playing MoGo on fixed time limits does not tell you anything about what it could possibly find out. It is more informative to watch the principal variation change over time. As it goes deeper the sequence always get better and better, and when you see that you know that increased thinking will imrove the principla variation forever. This does not mean that always plays the best move in the end, but it means that algorithm recursively improves the analysis all over the tree and only a serious bug can stop that from happen. Note that MC-programs do not have high level concepts programmed into them. Thus you will alwyays be able to say it played X because it does not understand Y whenver it plays a bad move but this is wrong. Correct is: it played X because it did not search deep enough. -Magnus Quoting terry mcintyre [EMAIL PROTECTED]: From: Don Dailey [EMAIL PROTECTED] On Mon, 2007-01-22 at 03:43 +0100, alain Baeckeroot wrote: The few games i played against mogobot on 19x19 shows that it does not know overconcentration. And i can safely bet that increasing thinking time will not solve this, By definition, a scalable program can solve all problems so your statement is incorrect. Is Computer Go infinitely scalable? Is Mogobot, in particular, scalable? Most programs reach scalability limits at some point. If the concept of overconcentrated shape is not inherent in a given program, it might take a vast number of simulations to compensate for that lack. I suspect that monte carlo will need to be merged with some method of learning patterns and concepts to play higher-level Go in human-scale timeframes. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea for a new measure of a computer go program's rank.
Yes, we heard that argument for years in computer chess and it never happened. Do you have some kind of basis for believe that? i wouldn't argue that future algorithms can't be time-doubled beyond the existing skill level of people, just that the current evidence is weak that we already have such algorithms in hand. s. TV dinner still cooling? Check out Tonight's Picks on Yahoo! TV. http://tv.yahoo.com/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Note that professionals do not play perfect endgame, ... Enough, apparently, that it separates a world champion from a run-of-the-mill 9-dan. Also, post-mortem analysis of pro games published in go magazines routinely finds some game-result changing improvements in the endgame. Yes, though in the Honinbo book I mentioned there is something like Ishida lost by 0.5pt in one game and in the post-mortem they decided he had played at least the last 100 moves correctly. (from my fuzzy memory - I don't have the book to hand). However he was probably the world's strongest endgame player at the time and at the peak of his concentration. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
Been following this thread pretty closely and thought I would jump in with a thought and try to find some common ground. I think there is truth to be found in both sides of this argument. Of course people improve with time and so do computers with certain algorithms. The question is about the curve and whether there is a significant difference in this curve between chess and go. Don believes there is probably no difference and states a rule: doubling thinking time = linear improvement in play. What if we look at it mathematically by looking at the branching factor? Go’s branching factor is generally considered to be about an order of magnitude greater than chess – perhaps a bit less, right? That means that after each ply go becomes another additional order of magnitude more complex. Now of course, in practice it’s not so simple, as breaking the game into regions and doing local reading and global analysis reduces the complexity somewhat, but in general go explodes a lot faster than chess and this fact is commonly used as one of the reasons methods used for computer chess don’t work on go especially combined with the lack of reliable evaluation. For the sake of argument if we assume that doubling thinking time allows one to double the number of positions and alternatives that can be analyzed, this doubling would seem to have lesser impact in go where the explosion is much quicker than in chess and thus the same relationship may not hold. The improvement may not be linear or it may not hold for very long. The point of diminishing returns for a human due to this could be much earlier in go than in chess. As go players get better they must learn to “sense” the board based on years of experience combined with our evolutionary tuned super parallel visual pattern matcher. This provides the player shortcuts that otherwise would be impossible (for humans) to read out. Assuming enough processing power and memory this problem would not necessarily hold for computer-go. By the way, I think some of this very same thing applies to both chess and go, just a matter of different degrees. From my own experience with chess and go, I can say that I don’t feel overwhelmed when playing chess. That is, I always feel like I can think and reason about the moves fairly deeply and use simple evaluation like piece counts, protection, mobility, etc. to decide between lines of play. I may be entirely wrong but I feel like I can think about it anyway. I’m not a real strong player, but I had a friend in high school and college whose Dad was a Grand Master. His son was pretty good and we would play a lot of chess together. Once in while I would play against his Dad and usually get slaughtered. One time he was doing one of those events where he would play 30 people at once. I played and managed to keep him challenged well into the middle game. I could tell he was worried. On one trip around I still hadn’t made my move and was forced to make the best one I had. It was a blunder but I didn’t see it yet. Immediately he took advantage of it and I didn’t have a chance after that. He confirmed this after the game was over and set the pieces up as they were at that point and showed me what I should have done (I thought an amazing feat given he was playing 30 or more different simultaneous games). Anyway in this situation where I had a lot more time than he did I was able to challenge him and only after making a blunder was I in trouble. So I see where Don is coming from with Chess. Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed without enough tools to understand how to plan and evaluate moves in all but the simplest isolated cases. I know that giving me tons of extra time against a good player would not help. The interactions between areas and the explosion of the game and lack of experience to be able to “sense” good shape and proper balance early enough to lead to life and territory just simply overwhelms me. The feeling is not as severe as it was when I first learned, but it is still there. I wonder whether even for strong amateurs this is still the case, but just happens a bit deeper. Is this the time limit that Ray talks about where any more time is not helpful? It is that point when it becomes so terribly complex and overwhelming that no more thinking can help given your current ability to judge potential in the positions. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: libgoboard v0.97 released
Direct link:
http://www.mimuw.edu.pl/~lew/download.php?file_no=8
Łukasz
On 1/22/07, Łukasz Lew [EMAIL PROTECTED] wrote:
Hi,
Few interesting things has happened so I decided to announce new version:
- bug-fix: komi was too big (1 point) so program as white tended to
loose by 0.5 point
- improve portability (if just make is not enough for You, please tell me)
- simple_playout::run is a simplest playout loop (80% performance)
You can use it as a starting point/tutorial for Your Monte-Carlo Go.
(I dare to paste the code at the end of the message)
- more convenient printing functions
- column coordinates around the board printed as letters (was numbers)
- faster RNG + more accurate performance measurement
- performance
43 kpps on 1.4 GHz
70 kpps on 2.2 GHz
will anybody send me info about 3.2 GHz?
- no more darcs repository, will publish mercurial repository soon.
Best Regards,
Łukasz Lew
Code of simple playout loop ---
player::t run (board_t* board, player::t first_player) {
v::t v;
bool was_pass[player::cnt];
uint move_no;
player::t act_player;
act_player = first_player;
player_for_each (pl)
was_pass [pl] = false;
move_no = 0;
do {
v = play_one (board, act_player);
was_pass [act_player] = (v == v::pass);
act_player = player::other (act_player);
move_no++;
if ((was_pass [player::black] was_pass [player::white]) |
(move_no max_playout_length)) break;
} while (true);
return board-winner ();
}
v::t play_one (board_t* board, player::t player) {
v::t v;
uint start;
// find random place in vector of empty vertices
start = pm::rand_int (board-empty_v_cnt);
// search for a move in start ... board-empty_v_cnt-1 interval
for (uint ev_i = start; ev_i != board-empty_v_cnt; ev_i++) {
v = board-empty_v [ev_i];
if (!board-is_eyelike (player, v)
board-play (player, v) != board_t::play_ss_suicide) return v;
}
// search for a move in 0 ... start interval
for (uint ev_i = 0; ev_i != start; ev_i++) {
v = board-empty_v [ev_i];
if (!board-is_eyelike (player, v)
board-play (player, v) != board_t::play_ss_suicide) return v;
}
board-check_no_more_legal (player); // powerfull check
return v::pass;
}
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea for a new measure of a computer go program's rank.
On 21-jan-07, at 19:27, Don Dailey wrote: not considering biological factors which would cut into this a bit. There was a time when there were no time-limits in Go, which was abused by many players by turning a game into a stamina contest. I believe this practice was abandoned when someone collapsed at the board and died. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: libgoboard v0.97 released
On 1/22/07, Vlad Dumitrescu [EMAIL PROTECTED] wrote: Hello Lukasz, On 1/22/07, Łukasz Lew [EMAIL PROTECTED] wrote: Few interesting things has happened so I decided to announce new version: I have a few observations: * in order to make libgoboard compile under cygwin I had to rename const float infinity, it wasn't used and there is a clash with infinity() from math.h Thanks, I will fix it. * running playout_test_opt on Ubuntu Linux gives a weird result, looks like an overflow of some kind: from 20 playouts, black wins 85732 and white wins 3213567648 or 3219491824 or some number in that neighbourhood. Which version? What about engine_opt / engine_debug / playout_test_debug? Maybe it is not initialized properly. Can You print the value before any playout? On Cygwin, the results are ok and always the same. I will add randomization of seed. Thanks for that, Lukasz best regards, Vlad ___ 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] Re: libgoboard v0.97 released
Randomization of seed may not be a good idea. For some experiments it is better to know the starting seed and keep it the same, for others, like play against humans, randomization is probably preferable. I would suggest having a runtime flag that can be set either way. Cheers, David On 22, Jan 2007, at 2:01 PM, Łukasz Lew wrote: On Cygwin, the results are ok and always the same. I will add randomization of seed. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] an idea... computer go program's rank vs time
At 09:27 AM 1/22/2007, you wrote: ... Don believes there is probably no difference and states a rule: doubling thinking time = linear improvement in play. i agree with this over some small range of powers of two. ..., as breaking the game into regions and doing local reading and global analysis reduces the complexity somewhat, but in general go explodes a lot faster than chess ... ... I can say that I donât feel overwhelmed when playing chess. ... Now with Go as a beginner still, on the other hand, I almost always felt and still feel quite overwhelmed ... yes, i usually feel this way in tournament games. and again more time will help (for some small powers of 2). i think more time works better because go has more battles going on at the same time. ... The interactions between areas and the explosion of the game and lack of experience to be able to âsenseâ good shape and proper balance early enough to lead to life and territory just simply overwhelms me. The feeling is not as severe as it was when I first learned, but it is still there. I wonder whether even for strong amateurs this is still the case, but just happens a bit deeper. Is this the time limit that Ray talks about where any more time is not helpful? ... if you are analyzing one battle, maybe more powers of two. if it's many battles, maybe fewer powers of two as you will hit your mental limit sooner. thanks --- vice-chair http://ocjug.org/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
