Re: [computer-go] Dynamic komi at high handicaps
I 100% agree with Don, dynamic komi just cant be the right approach in my opinion. One idea I just have is this : In the tree search part, instead of using a rule wich converges to MAX, use a rule wich converges to alpha*MAX + beta*AVERAGE. Do this only for plies where it is the weaker player turn (the player who benefits from handicap stones) When beta is high, it may simulate the fact that the weak player cant actualy read out sequences reliabily, thus increasing the chances of succes of the stronger player. Just a wild guess anyway... - Original Message - From: Don Dailey To: computer-go Sent: Wednesday, August 12, 2009 11:11 PM Subject: Re: [computer-go] Dynamic komi at high handicaps The problem with MCTS programs is that they like to consolidate. You set the komi and thereby give them a goal and they very quickly make moves which commit to that specific goal. Commiting to less than you need to actually win will often involve sacrificing chances to win.Sometime it won't, but you cannot have a scalable algorithm which is this arbitrary. However, if the handicap is too high, the program thinks every line is a loss and it plays randomly. That's why we even consider doing this. Dynamically changing komi could be of some benefit in that situation if there is no alternative reasonable strategy, but it does not address the real problem - which is what I call the "committal consolidation" problem. You are giving the program an arbitrary short term goal which may, or may not be compatible with the long term goal of winning the game. Whether it's compatible or not is based on your own credulity - not anything predictible or that you can scale. And as the base program gets stronger this aspect of the program becomes more and more of a wart. If this can be made to work in the short term, it should be considered a temporary hack which should be fixed as soon as possible. We have to think about this anyway sooner or later because if programs continue to develop and the predictive ability of the playouts and tree search gets several hundred ELO better, these programs may start to see more and more positions as either dead won or dead lost. I'm sure we will want some kind of robust mechanism for dealing with this which is better at estimating chances that the opponent will go wrong as opposed to doing something that is a random benefit or hindrance. - Don 2009/8/12 terry mcintyre Ingo suggested something interesting - instead of changing the komi according to the move number, or some other fixed schedule, it varies according to the estimated winrate. It also, implicitly, depends on one's guess of the ability of the opponent. An interesting test would be to take an opponent known to be weaker, offer it a handicap, and tweak the dynamic komi per Ingo's suggestion. At what handicap does the ratio balance at 50:50? Can the number of handicap stones be increased with such an adaptive algorithm? Even better, play against a stronger opponent; can one increase the win rate versus strong opponents? The usual range of computer opponents is fairly narrow. None approach high-dan levels on 19x19 boards - yet. Terry McIntyre “We hang the petty thieves and appoint the great ones to public office.” -- Aesop From: Brian Sheppard To: computer-go@computer-go.org Sent: Wednesday, August 12, 2009 12:33:13 PM Subject: [computer-go] Dynamic komi at high handicaps >The small samples is probably the least of the problems with this. Do you >actually believe that you can play games against it and not be subjective in >your observations or how you play against it? These are computer-vs-computer games. Ingo is manually transferring moves between two computer opponents. The result does support Ingo's belief that dynamic Komi will help programs play high handicap games. Due to small sample size it isn't very strong evidence. But maybe it is enough to induce a programmer who actually plays in such games to create a more exhaustive test. ___ 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://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http:/
Re: [computer-go] Ko in light playouts
It has been discussed already on this list. The common approach is to not even bother to try detect ko in playouts. In case of infinite game (very rare but happens) you can just put a threshold on the number of moves and igore the result. Of course you have to detect ko in the tree search part though. - Original Message - From: "Heikki Levanto" To: "computer-go" Sent: Monday, June 15, 2009 10:45 PM Subject: [computer-go] Ko in light playouts I am slowly getting my little bot to do very light playouts. I came to think about detecting ko. Is it even necessary in a simple playout? During the earlier stages of the game, the playouts have no idea of wanting to recapture the ko, of ko threats, or anything else. Only in the endgame can we run into problems, when everything else is filled up, and the only points left are in a ko fight. At that point the playout moves are fast, repeating the same position all over again, until a limit to the number of moves puts a stop to it all. I suppose that in the end the right thing is to do the right thing, and detect at least a simple ko properly and according to the rules. But I thought I'd ask if people are trying alternative tricks? - Heikki P.S. My progress is awfully slow, as I work full time with other things, and have several hobbies cometing for my spare time. Still, I am making slow progress, and at some point I get my "halfgo" playing on cgos. Very badly, to begin with... It is a simple program, written in C, using bitmaps for the board images. I just wanted to see how far I could take that approach. Now it seems to be a good foundation for my next experiments, which I will have to do before discussing them here. -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ 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] Monte-Carlo Simulation Balancing
I noticed that, in general, changes in the playout policy have a much bigger impact on larger boards than on smaller boards. Rémi I think rating differences are emplified on larger boards. This is easy to see if you think about it this way : Somehow a 19x19 board is like 4 9x9 boards. Let us define a new game that I would call 4-Go where instead of playing one game, you play simultenously 4 games and determine the winner by calculating the sum of the scores of the four games. Certainly rating differences would be bigger with 4-go than with go (given the same two players). This explains why rating differences are bigger on 19x19 than 9x9. Ivan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCB/UCT and moving targets
This same topic already occured on the list some time ago. I think the idea is to "forget" older results. For exemple you can compute the win rate based only on the last 500 simulations. Older information may not be up to date and will not help much because 500 simulations is enough to compute an accurate winrate. The problem is that you have to store the result of 500 simulations at each node. I think some people reported that it does indeed increase the strength of their program. - Original Message - From: "Peter Drake" <[EMAIL PROTECTED]> To: "Computer Go" Sent: Wednesday, June 25, 2008 5:48 PM Subject: [computer-go] UCB/UCT and moving targets UCB (and hence UCT) would treat the following sequences of wins (1) and losses (0) the same: 01010101010101010101010101010101 Clearly, it would be better to favor the second sequence, because that move has done more for us lately. Because the tree is growing, the values of the moves are moving targets. Has anyone done any work dealing with this phenomenon, e.g., somehow giving more weight to more recent playouts? Peter Drake http://www.lclark.edu/~drake/ ___ 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] chess study
I have a question : If the lines in the graph are straight lines and they dont have the same increase rate, then isnt there a point where they should cross ? Do they all cross at the same point ? I guess this point (if it exists) would indicate some kind of starting point : It would correspond to the weakest possible strenght. Any thoughts ? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Calculate the number of stones in the same group?
M Interesting problem lol. April fools'day, I guess? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] solving the nakade problem
You are right, it is not a "perfect" solution. I find it attractive though because it is very simple and I think it will work well on "a lot" of situations. Currently Zoe is losing a lot of games on cgos because it doesnt even know about seki. At least it should be an improvement over what is done in Zoe now. You said Valkyria had a lot of logic about what self-ataris should be allowed. It seems to be usefull, from what I have seen valkyria doesnt seem to have flaws in its life and death understanding, unlike most other MC programs (including mine) - Original Message - From: "Magnus Persson" <[EMAIL PROTECTED]> To: Sent: Thursday, March 13, 2008 8:57 AM Subject: Re: [computer-go] solving the nakade problem Quoting Ivan Dubois <[EMAIL PROTECTED]>: Hello, I think there is a very easy and straigthforward solution to the "nakade/seki" problem, here it is : For moves that are self-atari on a group that contains MORE than 5 stones : Both in the tree and the playouts, strictly forbid them (exactly like you forbid filling an eye). (This is to handle seki and have efficient playouts). For moves that are self-atari on a group that contains LESS than 5 stones : Allow them both in the tree and the playouts. In the playouts, they should be played with a low probability. But they should be played when there is no other move left. (This is to ensure groups with are dead with nakade are eventualy captured in "some" playouts). What do you think about this solution ? I will probably implement it in Zoe to see if it efficient, unless someone finds a flaw in the logic. Valkyria has a lot of logic about what self-ataris should be allowed or not, and the size of group is part of that. I see two possible flaws in playing the remaining moves self ataris with low probability. a) In some cases the group under attack will appear as alive because the nakade is always always captured in a way that creates a second eye. Just playing all moves with low probability does not mean that the right move is played. Also correct nakade handling means that some moves has to be played immediately as response to a liberty filling move from the other player. b) You also have the problem of seki. Many nakade problems includes seki as a possibility in the search tree. And there are some common seki patterns involving just a few stones, so in some cases the probability of playing a move should be zero even with few stones. I think the program need to either: 1) Implement proper logic for picking the correct moves 2) Learn from its mistakes, maybe hash every suicidal situation in the playouts played and store statistics. But of course there are always room for any quick and dirty heuristics which actually improves the playing strength. It does not have to be perfect to work well. -Magnus ___ 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] solving the nakade problem
Hello, I think there is a very easy and straigthforward solution to the "nakade/seki" problem, here it is : For moves that are self-atari on a group that contains MORE than 5 stones : Both in the tree and the playouts, strictly forbid them (exactly like you forbid filling an eye). (This is to handle seki and have efficient playouts). For moves that are self-atari on a group that contains LESS than 5 stones : Allow them both in the tree and the playouts. In the playouts, they should be played with a low probability. But they should be played when there is no other move left. (This is to ensure groups with are dead with nakade are eventualy captured in "some" playouts). What do you think about this solution ? I will probably implement it in Zoe to see if it efficient, unless someone finds a flaw in the logic. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
Ok, I think I see what you mean, but I am not sure I really agree. As you say, this is related to horizon effect. I think current MC programs can play ko quite well because they are trying do delay the outcome of losing the ko, therefore they tend to play threats do gain time, just like human players do. I dont think it is essential that the ko be resolved inside the tree part. And I dont believe there exist efficient way to handle ko in the playout other than just fordiding simple ko recapture. Ivan - Message d'origine De : Jonas Kahn <[EMAIL PROTECTED]> À : computer-go Envoyé le : Dimanche, 2 Mars 2008, 21h32mn 43s Objet : Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?]) > But correct ko threats playing has nothing to do with the playout part : > Since it is a strategic concept that involves global understanting, It is > handled by the UCT tree part. Yes and no. Theoretically, that's the work of the UCT part. But, as Steve pointed out, kos can go on for long. I don't know what depth is attained in the tree (by the way, I would really like to know), but I doubt it is that long. Moreover, some kos must be kept for later. Hence, some basic understanding of kos in the playouts might be useful. That's merely a variation of the horizon effect. We could even imagine a situation where the UCT makes a threat that loses points in the only aim of having the ko past the horizon, where it would be 50-50 (for example) in the playout. Jonas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Tactical information within simulations
I think it is a very good and natural idea. I guess in the future, all MC programs will have some kind of dynamic playout policies. - Message d'origine De : Jonas Kahn <[EMAIL PROTECTED]> À : computer-go Envoyé le : Dimanche, 2 Mars 2008, 19h43mn 29s Objet : [computer-go] Tactical information within simulations There is much high-level data to be found within the MC runs, such as whether a group is alive or not, etc. Now, I don't know if it is easy to inject it back within the simulations. Another approach (not excluding the first one) would be to gather much lower-level data. It's especially sad that the playouts have to discover over and over again that particular sequences are good or bad; we certainly could incorporate this knowledge in the following playouts. To know a sequence, it is sufficient to know which move follows each move. We could store that in a way similar to ``All moves as first'' (even if I thought about that before knowing AMAF). We could record the answers to each move on the board, with the results, in the simulations. Exemple: on 1 simulations, Black plays B2 6000 times. White answers A2 2000 times (1500 wins, 500 losses) C2 3000 times (500 wins, 2500 losses) B3 1000 times (500 wins, 500 losses) Now, there could be many variants. The easiest way, and one of the least memory-hungry (already very bad from that point of view, though), would be to keep after each move how many times each possible following move has been played, and with what overall overall result. We could also keep tables of the previous move by the same player. A combination of black's previous move + (white's) last move should be enough to distinguish many situations. A more ambitious variant would be to build a tree from each possible move, similarly to the main tree. In such a case, I gather that nodes should be expanded after being OFTEN visited. In both cases, we could/should keep the information from the previous moves, while letting it dim out slowly. A simple idea would be to multiply by say .9 or .95 the number of games each move has been recorded as playing at each stage (or if storage is wins-losses, multiply this number of losses and wins). There are many difficulties, especially since we must not use too much computing power. Notably: - Globally how to blend this with the choice of moves ? It depends on the implementation. - All moves are not simultaneously available: some might already have been played. I don't know if this would really be a handicap. - A move could be an only move in one situation, while another is the only move in another situation, with the same previous moves. I gather this should not be important. This rule would encourage using the move corresponding to the more frequent situation, but the winning rate would decrease because of the other situation, and encouragement should be kept at a reasonable level. - In the case of trees, how do we take into account the sequences in the other trees leading to the same place. I mean, suppose we have a tree N4-M2-O5-M6 and a tree M2-O5-M6. It might be heavy to update everything and keep coherence. - It's probably much too heavy to check whether a win or a loss occured when the move had low or high probability to be chosen. - We have frequencies and winning rates associated to moves. Either we can compute a probabiliy distribution from this data, and blend it in some way with the existing one, or we can compute bonus/malus to each of the moves appearing, and add that to log_prob of the original distribution. The problem of the former is: how do we deal with moves that seldom/never appear after the previous moves ? We cannot really get useful information on them. The problem with the latter is that we might end up giving a bonus to already much favoured moves. I think the way we use this information should satisfy to the following properties: - If there is an only move, the recommendation should be strong enough to mainly overcome all other suggestions. Say chosen 90% of the time. - Symmetrically, a move that always loses should be banned. - If a move gets a new victory, it should get slightly more probable. Mutatis mutandis, the same for loss. - Quick to compute ! Ideally using a Bradley-Terry model or something like that would be a good idea, but unusable during a game. In any case, the ``coefficients'' we use should not be updated often. Maybe once in 1000/1 simulations if it's quick enough, otherwise once at the beginning of each move. If anyone is interested, I can try to go down to specifics, matching as best I can the existing implementation. As finding a good mathematical procedure is not easy, I shall not work on that if it does not interest anyone. Jonas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])
Mogo is already very strong at endgame and certainly plays perfectly near the end of the game. The more advanced the program, the sooner it can play perfect endgame. But correct ko threats playing has nothing to do with the playout part : Since it is a strategic concept that involves global understanting, It is handled by the UCT tree part. - Message d'origine De : steve uurtamo <[EMAIL PROTECTED]> À : computer-go Envoyé le : Dimanche, 2 Mars 2008, 20h25mn 33s Objet : Re: [computer-go] Re: Should 9x9 komi be 8.0 ?] a few subtleties -- it's possible for a machine to play a perfect endgame, and my guess is that machines will play perfect endgames before people do, although most pros are excellent at the endgame. counting ko threats and utilizing kos effectively is tricky in playouts -- kos can naturally extend a playout very, very far beyond where the actual advantage would be taken in a non-ko situation, and the likelihood of getting this far often enough in playouts to see the advantage is going to be difficult for machines without a lot of domain-specific knowledge. different humans are often good at different stages of the game, and making up a few points in the endgame, or getting a massive lead in the beginning of the game may be possible, convincing a computer player of something that isn't true -- either that it's nearly guaranteed to win, or nearly guaranteed to lose. all that having been said, i'm quite impressed with how well these programs are doing. s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Transpositions in UCT
Hello, I would like to add transposition handling to my UCT engine (it is currently 2050 elo on CGOS). I thought a little about how to do it, and realized it is not obvious at all. So I thought I may ask to people on this list what they think. My first idea was to back-up the result of each simulation to all the parents of the leaf it was played at, and then recursively up to the root. But I think it is not correct, because it will interfere with the uct selection algorithm for the transposed parents. Maybe it is not really a problem though, I dont know. So I would like to ask what you are doing to handle transpositions ? Also, how much improvement do you think godd transposition handling can give ? Thanks Ivan _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] How to use CGOS ?
It does use GTP. - Message d'origine De : Raymond Wold <[EMAIL PROTECTED]> À : computer-go Envoyé le : Dimanche, 24 Février 2008, 1h54mn 18s Objet : Re: [computer-go] How to use CGOS ? Once we're on the topic, is there a good reason why CGOS does not use GTP? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] How to use CGOS ?
I found an older version of cgos and did what you say and it seems to work now, thanks. I think the new script uses a different syntax. - Message d'origine De : Magnus Persson <[EMAIL PROTECTED]> À : computer-go@computer-go.org Envoyé le : Samedi, 23 Février 2008, 16h01mn 08s Objet : Re: [computer-go] How to use CGOS ? I use a line similar to the following. (Cgos3.exe is an older version of client but it should work the same. If not then that explains why I never switched to the newer clients) cgos3.exe MyUserName MYPWD "MYPROG.exe" quit.txt > log.txt 1) Surround the path to your program with "" 2) You also have to provide the password and username 3) The "quit.txt" means that you logoff the program by creating a file with this name 4) "> log.txt" creates a log so you can look to see what went wrong if it does not connect Quoting ivan dubois <[EMAIL PROTECTED]>: > Hello, > > I downloaded the file "cgosGtp-win.zip" from > http://cgos.boardspace.net/ but I cant make it work. I am on windows. > > I tried this command : cgosgtp.exe -name MyProgram.bat > But it doesnt work. > > What am I doing wrong ? > > Could someone provide an example of a correct invocation of cgosgtp.exe ? > > Thanks a lot. > > Ivan > > > > _ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers > Yahoo! Mail http://mail.yahoo.fr > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] How to use CGOS ?
Hello Don, I folowed your instructions but it still doesnt work. When I run cgosGtp.exe with no argument it does nothing. When I do "cgosGtp.exe -help" it opens a window titled : "Error in TclKit" with a list of command inside, but I dont understand it. When I do what you explained in your message, ie : cgosgtp -c config.txt -k fill_file Then it opens a window in wich is written : "This isn't a Tk applicationbad window path name "config.txt" I am confused. - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Samedi, 23 Février 2008, 15h54mn 27s Objet : Re: [computer-go] How to use CGOS ? Ivan, If you run the script without any arguments it displays a usage message. It require a configuration file - one of the command line arguments will display a sample configuration file - here is a linux example: [EMAIL PROTECTED]:~/tmp$ ./cgosGtp-linux-x86_32 cgosGtp 0.98 alpha - engine client for CGOS Linux-x86 by Don Dailey Usage: /home/drd/tmp/cgosGtp-linux-x86_32/main.tcl -c CONFIG_FILE -k KILL_FILE -p PLAYER_FIRST -s -c specified name of config file - this is MANDATORY -k sepcifies a file to create which will stop client after current game -p specifies which player plays first game -s display a sample configuration file to stdout and exit [EMAIL PROTECTED]:~/tmp$ ./cgosGtp-linux-x86_32 -s # config file for testing various version of MyBot # %section server server cgos.boardspace.net port 6867 %section player name MyBot-1.0 password abcxyz invoke./mybot-1.0 --gtp --log mybot.log priority 7 %section player name MyBot-2.0 password abcxyz invoke./mybot-2.0 --gtp --log mybot.log priority 3 - Don ivan dubois wrote: > Hello, > > I downloaded the file "cgosGtp-win.zip" from http://cgos.boardspace.net/ but > I cant make it work. I am on windows. > > I tried this command : cgosgtp.exe -name MyProgram.bat > But it doesnt work. > > What am I doing wrong ? > > Could someone provide an example of a correct invocation of cgosgtp.exe ? > > Thanks a lot. > > Ivan > > > > _ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail > http://mail.yahoo.fr > ___ > 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/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] How to use CGOS ?
Hello, I downloaded the file "cgosGtp-win.zip" from http://cgos.boardspace.net/ but I cant make it work. I am on windows. I tried this command : cgosgtp.exe -name MyProgram.bat But it doesnt work. What am I doing wrong ? Could someone provide an example of a correct invocation of cgosgtp.exe ? Thanks a lot. Ivan _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Re: 19x19 Study. Nakade is difficult
In the tree search part, there is generaly no restriction to the moves that can be played. So a UCT program should have no problem seeing that A1 is the best move localy. However, A1 will be considered a 50% killing move, not 100%. This is because UCT will have trouble looking ahead the forced sequence that makes the white group 100 % dead. I explained in a previous post why. - Message d'origine De : Jacques Basaldúa <[EMAIL PROTECTED]> À : computer-go@computer-go.org Envoyé le : Jeudi, 31 Janvier 2008, 20h39mn 58s Objet : [computer-go] Re: 19x19 Study. Nakade is difficult I mentioned nakade in a list including "not filling own eyes". Perhaps, not "filling own eyes" is a simpler example: | . . . . . . . | . # # . # . . | . O # . # . . | O O O . # # . | # # O O O # . | . # # . . . . --- (Unless I made a mistake: Black to play and a1 is the only move killing white.) All MC programs avoid eye filling. I am not claiming that this is a wrong decision. It has been tested, it is the correct decision. It is not a bug that can't be fixed, either. If white is blind to the a1 move, then it is happy with this position because it thinks it is unconditionally alive. Therefore, it should not be impossible to force white to make this shape because white likes it. If no program understands this, white is alive and the game continues as if a1 was illegal. A program that finds a1 changes all. It is not a question of limiting the move in the playouts or in the tree. The playouts make an evaluation function, if they are systematically wrong the tree won't expand in that direction in advance. Playing go is about reading the problems before they happen. A program that does the playouts systematically wrong and the tree right, may be a good tsumego solver, but not necessarily a good player, because it won't see it coming. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
I gave you a proof of what I am claiming, I really dont see what I can do more. Anyway we all now all this is just a waste of time for pleasure. People who are really working on a UCT engine (I dont anymore) will find solutions to these problems as soon as they become relevant to playing strength. > You speak to imprecisely for me, sorry. When questioned, you reverse > position. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
By the way, my argument still applies when there are no outside liberties, because the eye filing itself is a long enough UCT "trap" (a sequence of moves that appears to be just like null moves). I gave a theoretical argument, but actualy it is not very surprising. Did you ever wonder why Mogo, being now so strong, could still exhibit so basic and stupid blind spots ? The explanation is very simple : Those blind spots reveal the fact that some aspects of its understanding do not scale as fast as the other aspects. Actualy for some aspects, it does not scale at all, from a practical point of view. Ivan - Message d'origine De : Michael Williams <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 20h38mn 32s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies ivan dubois wrote: > I agree that the current implementation of Mogo (from what I know about > it) will not know for sure that the D17 black group is 100% dead. > It will think that it is X% dead and stick to that estimation, whatever > thinking time you give it. X is a constant that does not depend of > thinking time (no scalability). How are you arriving at this conclusion? It makes no sense to me. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
Hello, - Message d'origine De : Michael Williams <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 20h38mn 32s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies ivan dubois wrote: > I agree that the current implementation of Mogo (from what I know about > it) will not know for sure that the D17 black group is 100% dead. > It will think that it is X% dead and stick to that estimation, whatever > thinking time you give it. X is a constant that does not depend of > thinking time (no scalability). >How are you arriving at this conclusion? It makes no sense to me. Actually this is not true for this exact situation, but I think it is true if the black group has enough external liberties. Suppose it has 10 outside liberties, to make things very clear. For the simplicity of my argument, suppose also that the big eye is almost entirely filled with white stones (minus 1 liberty) Here is my reasoning : Starting from the root, there are some playouts where the black group dies, and other where it lives. Let us note X the proportion of playouts that end with the black group having been captured. Now is there any move A, starting from the root, that will change this ratio if you start the random playouts just after A ? I think clearly, the answer is no, do you agree with that ? The only relevant possible move would be to fill a liberty, but since all liberties will be filled anyway during the playouts, this will not change anything to the scenario. The only thing that matters is wether or not white plays first at the vital point every time the eye is reduced during the playouts. Using the same argument, there exists no sequence of less than 8 moves that can change the value of X. This means all these sequences of liberty filling will be considered to have exactly the same value than playing a null move. I think it implies that uct will "never" (of course in theory it will at some point but I say it would require absurd computing time) find the sequence that captures the group with 100% confidence, because this sequence begins with 8 apparently useless moves. Ivan _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable ... is a troll
Thanks. - Message d'origine De : Russell Wallace <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 18h07mn 27s Objet : Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll On Jan 23, 2008 3:44 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > This is still nonsense. UCT in actual real world "PRACTICE" responds > dramatically to more hardware, how can you say it's not clear whether > it's scalable in practice? In fairness, he didn't say that. What he said was that our belief regarding whether or not UCT scales in practice, should be based on tests on real hardware (which appear to give an answer in the affirmative), rather than on a mathematical proof of what happens in the limit as computer time tends to infinity (because what happens in the limit as time tends to infinity, doesn't necessarily have much bearing on what happens on real hardware; so tests are more informative). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
Hi, This is correct. Do you think there will be no playouts where the group dies ? I think there will be around 50% where the group dies. If you think this is not the case, please explain to me. Ivan - Message d'origine De : steve uurtamo <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 17h22mn 35s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies it will only assign it a positive probability of being dead if there are playouts where the group dies, right? s. - Original Message ---- From: ivan dubois <[EMAIL PROTECTED]> To: computer-go Sent: Wednesday, January 23, 2008 10:51:52 AM Subject: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Hello, I agree that the current implementation of Mogo (from what I know about it) will not know for sure that the D17 black group is 100% dead. It will think that it is X% dead and stick to that estimation, whatever thinking time you give it. X is a constant that does not depend of thinking time (no scalability). However, and this can be surprising, I am not sure wether it is really a scalability killer for whole board play, because after all, it doesnt have to know with 100 % confidence the status of one group to play perfectly. - Message d'origine De : terry mcintyre <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 16h24mn 53s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Feed any MC-UCT program the position after White B1, at move 195, and ask the probability of a black win. Repeat until the program corrects its estimate. It would be interesting to determine just how many simulations are needed to solve this problem - which is obvious to double-digit kyu players. Terry McIntyre <[EMAIL PROTECTED]> - Original Message From: ivan dubois <[EMAIL PROTECTED]> To: computer-go Sent: Wednesday, January 23, 2008 7:17:17 AM Subject: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Hello, After thinking a bit more about it, I came to the conclusion that the so called "Bent four in the corner" shape, is not such a serious scalability killer (I like this term). Nor is the situation that appears in your game. Let me explain why : It would indeed be a scalability killer if Mogo was 100 % sure that some group is dead, when it is actually alive. However what happens is that it has some doubts about the situation. It may think for example it is 60 % alive and 40 % dead. Of course it would be better for him to know the reality, but having some persistent doubt on it is not that much detrimental. For example if he has perfect information about the rest of the board, he will play perfectly on the rest of the board. I propose a chalenge to this list : Find a real scalability issue with Mogo or any other actual UCT program. (And prove it) Ivan - Message d'origine De : Harald Korneliussen <[EMAIL PROTECTED]> À : computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 15h31mn 20s Objet : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Ivan Dubois mentioned the bent four in the corner shape as a scalability killer, a situation where more playouts doesn't help (much), because playouts systematically misevaluate it. As I understand it, it could be corrected in the tree, but this is very unlikely to happen until the very end of a game, by which time it may be too late (Mogo having worked the entire game for that solid 0.5 win, which turns out to be a solid loss instead because of the life-and-death misevaluation) I recalled a KGS game of Mogo I'd looked at, where something very similar happened, and with a little digging I found it again: http://files.gokgs.com/games/2007/12/1/Ardalan-MoGoBot3.sgf It turns out it's not the "bent four" shape, but I suspect it's another such shape, where more playouts only confirm that "these moves aren't worth including into the tree", so that UCT catches them very late, if ever. If these situations can be reliably created by a human, then indeed they put an upper limit on the "real world" scalability of a program. If I should propose a hackish heuristic to deal with such situations, this is it: At one point, when the problematic shape appeared, the human must have done a move that to the computer seemed horribly bad. "Why did he do that? Doesn't he see that my shape is alive?". When such situations occur, there are two possibilities: 1. The bot is playing a weaker human player, and the move is indeed bad. 2. The bot is playing a stronger human, and the move is actu
Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
Hello, I agree that the current implementation of Mogo (from what I know about it) will not know for sure that the D17 black group is 100% dead. It will think that it is X% dead and stick to that estimation, whatever thinking time you give it. X is a constant that does not depend of thinking time (no scalability). However, and this can be surprising, I am not sure wether it is really a scalability killer for whole board play, because after all, it doesnt have to know with 100 % confidence the status of one group to play perfectly. - Message d'origine De : terry mcintyre <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 16h24mn 53s Objet : Re: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Feed any MC-UCT program the position after White B1, at move 195, and ask the probability of a black win. Repeat until the program corrects its estimate. It would be interesting to determine just how many simulations are needed to solve this problem - which is obvious to double-digit kyu players. Terry McIntyre <[EMAIL PROTECTED]> - Original Message From: ivan dubois <[EMAIL PROTECTED]> To: computer-go Sent: Wednesday, January 23, 2008 7:17:17 AM Subject: Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Hello, After thinking a bit more about it, I came to the conclusion that the so called "Bent four in the corner" shape, is not such a serious scalability killer (I like this term). Nor is the situation that appears in your game. Let me explain why : It would indeed be a scalability killer if Mogo was 100 % sure that some group is dead, when it is actually alive. However what happens is that it has some doubts about the situation. It may think for example it is 60 % alive and 40 % dead. Of course it would be better for him to know the reality, but having some persistent doubt on it is not that much detrimental. For example if he has perfect information about the rest of the board, he will play perfectly on the rest of the board. I propose a chalenge to this list : Find a real scalability issue with Mogo or any other actual UCT program. (And prove it) Ivan - Message d'origine De : Harald Korneliussen <[EMAIL PROTECTED]> À : computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 15h31mn 20s Objet : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Ivan Dubois mentioned the bent four in the corner shape as a scalability killer, a situation where more playouts doesn't help (much), because playouts systematically misevaluate it. As I understand it, it could be corrected in the tree, but this is very unlikely to happen until the very end of a game, by which time it may be too late (Mogo having worked the entire game for that solid 0.5 win, which turns out to be a solid loss instead because of the life-and-death misevaluation) I recalled a KGS game of Mogo I'd looked at, where something very similar happened, and with a little digging I found it again: http://files.gokgs.com/games/2007/12/1/Ardalan-MoGoBot3.sgf It turns out it's not the "bent four" shape, but I suspect it's another such shape, where more playouts only confirm that "these moves aren't worth including into the tree", so that UCT catches them very late, if ever. If these situations can be reliably created by a human, then indeed they put an upper limit on the "real world" scalability of a program. If I should propose a hackish heuristic to deal with such situations, this is it: At one point, when the problematic shape appeared, the human must have done a move that to the computer seemed horribly bad. "Why did he do that? Doesn't he see that my shape is alive?". When such situations occur, there are two possibilities: 1. The bot is playing a weaker human player, and the move is indeed bad. 2. The bot is playing a stronger human, and the move is actually good. I think it may be a good idea to do something with the weighting in these situations, so that the relevant moves are added to the tree. In worst case, a lot of effort is wasted in proving a bad move bad - but this should not be so serious, as the bad move will likely mean the opponent has poor chances of winning anyway. In the best case, the program's blunder is revealed after the fact. This may still leave little chance of winning, (if the l&d error was severe) but at least the program's counting won't be off for the rest of the game. Since today's programs don't care for winning margins, counting errors by even a single point will spell disaster. I believe this heurtistic would be cheap in terms of computational cost, but hard to evaluate/tune. Self-play would not be very effective... _
Re : [computer-go] Bent four in the corner was:Scalability problem of play-out policies
Hello, After thinking a bit more about it, I came to the conclusion that the so called "Bent four in the corner" shape, is not such a serious scalability killer (I like this term). Nor is the situation that appears in your game. Let me explain why : It would indeed be a scalability killer if Mogo was 100 % sure that some group is dead, when it is actually alive. However what happens is that it has some doubts about the situation. It may think for example it is 60 % alive and 40 % dead. Of course it would be better for him to know the reality, but having some persistent doubt on it is not that much detrimental. For example if he has perfect information about the rest of the board, he will play perfectly on the rest of the board. I propose a chalenge to this list : Find a real scalability issue with Mogo or any other actual UCT program. (And prove it) Ivan - Message d'origine De : Harald Korneliussen <[EMAIL PROTECTED]> À : computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 15h31mn 20s Objet : [computer-go] Bent four in the corner was:Scalability problem of play-out policies Ivan Dubois mentioned the bent four in the corner shape as a scalability killer, a situation where more playouts doesn't help (much), because playouts systematically misevaluate it. As I understand it, it could be corrected in the tree, but this is very unlikely to happen until the very end of a game, by which time it may be too late (Mogo having worked the entire game for that solid 0.5 win, which turns out to be a solid loss instead because of the life-and-death misevaluation) I recalled a KGS game of Mogo I'd looked at, where something very similar happened, and with a little digging I found it again: http://files.gokgs.com/games/2007/12/1/Ardalan-MoGoBot3.sgf It turns out it's not the "bent four" shape, but I suspect it's another such shape, where more playouts only confirm that "these moves aren't worth including into the tree", so that UCT catches them very late, if ever. If these situations can be reliably created by a human, then indeed they put an upper limit on the "real world" scalability of a program. If I should propose a hackish heuristic to deal with such situations, this is it: At one point, when the problematic shape appeared, the human must have done a move that to the computer seemed horribly bad. "Why did he do that? Doesn't he see that my shape is alive?". When such situations occur, there are two possibilities: 1. The bot is playing a weaker human player, and the move is indeed bad. 2. The bot is playing a stronger human, and the move is actually good. I think it may be a good idea to do something with the weighting in these situations, so that the relevant moves are added to the tree. In worst case, a lot of effort is wasted in proving a bad move bad - but this should not be so serious, as the bad move will likely mean the opponent has poor chances of winning anyway. In the best case, the program's blunder is revealed after the fact. This may still leave little chance of winning, (if the l&d error was severe) but at least the program's counting won't be off for the rest of the game. Since today's programs don't care for winning margins, counting errors by even a single point will spell disaster. I believe this heurtistic would be cheap in terms of computational cost, but hard to evaluate/tune. Self-play would not be very effective... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Ok, this is a "special" minimax solver. Call it the "Ivan Dubois stupid minimax solver" if you like. Anyway, its only purpose is to show that : "Returns the best move when given enough time" does NOT implie "Is scalable in practice". I am very sad that this simple logic has no appeal to most people on this list. - Message d'origine De : Erik van der Werf <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 15h21mn 37s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll On Jan 23, 2008 2:45 PM, ivan dubois <[EMAIL PROTECTED]> wrote: > When I say a minimax solver, I mean a program witch returns a random move > UNTIL it has completed its search, as I explained in a previous post. A plain minimax solver (without enhancements like iterative deepening) doesn't return anything until it has completed its search. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable ... is a troll
Duhhh ! When I say a minimax solver, I mean a program witch returns a random move UNTIL it has completed its search, as I explained in a previous post. You all agreed this program didnt scale, so why are you saying, all of a sudden, that it DOES scale now !? Anyway I'm fed up with this discussion now, this is so too much pain and way too frustrating. - Message d'origine De : Alain Baeckeroot <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 9h15mn 41s Objet : Re: [computer-go] Is MC-UCT really scalable ... is a troll Le mercredi 23 janvier 2008, ivan dubois a écrit : > Hi Alain, > Sorry for being so insistant : You should browse the archive of the list, nearly the same discussion about infinite and scalability happenned in 2007. > > >No i just said that, unless i really understood nothing, i read here from > >well > >known competent persons that MC+UCT scales infinitely , and would reach > >perfect > >play with infinite computational resources, and this is theoretically proven > >(which is not the case for classical program like our beloved GNU Go). > > This is absolutely true. Now this can also be said for a mini-max solver (my > point). Don Dailey answered better than i could do, yes minimax also scales. > > >So MC+UCT scales. (even against humans, martians, trolls, computers, gods > >... :) > The conclusion does not follow. Ah ? Why not ? what is wrong in the reasonning ? Should i think : " It scales in theory so it does NOT scale in practice " ? > The fact that it eventualy reaches perfect play with enough computing power > does NOT mean that it scales well. > Proof : A mini-max solver does reach perfect play with enough computing > power BUT does not scale. we don"t have the same informations. For Minimax scales too, maybe the improvement curve has a smaller slope than MC+UCT curve, but > > Actualy, this theoritical property is a NESCESSARY condition for UCT > to scale, but it is not a SUFFICIANT condition. The scalability of > UCT has been "proven" by its outstanding results From a pure logical point of vue - Positive experiment are never a valid proof. They are only examples that makes one feel his theory is right. - Only counter example are proof that the theory is wrong. > and Don's experiments, not by mathematics. Are you a troll ? Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Scalability problem of play-out policies
Sorry, this may very well be nitpicking, but it is not nonsense. I just dont like when people are making illegitimate deductions, using the fact that the same word can have two distinct meanings. Anyway all this is just nitpicking from my part, I have to admit. What is not nitpicking however, is wether some play-out policy (wich might appear to be working well) can compromise the scalability of UCT at some point. I read that there seemed to be a problem with Fatman's scalability. I dont know what are the latest news about this, but I think you should at least consider the possibility that it may come from some persistent missconception from the play-out policy. After all, I may very well be right. After thinking a little about it, I came to the conclusion that there can be a scalability problem when : There is a bias in the MC evaluation AND there is no move to be made in the UCT part that can partialy correct the missconception of the MC evaluation. This happens each time there is a situation that just cannot be settled immediatly, but has to wait the end of the game. Now I think I can give you a clean example : The bent four in the corner shape : http://senseis.xmp.net/?BentFourInTheCornerIsDead Tell me if I am wrong, but I bet nor your program nor Mogo does scale at all on this situation. That means whatever computing power you can give to it, If i can create such a situation in my game against him, I will probably win. And notice that more computing power will not help Mogo to avoid this situation because it doesnt know it to be a problem. Tell me if I am wrong, but I think it is a scalability problem that puts a real limit to the strength it can reach in theory. But please, do not miss understand me, I am NOT saying that this is a crucial problem to MC that cannot be fixed. I am sure it CAN be fixed. I am just saying that currently MC programs do not scale infinitely, but I have no doubt that these problems will be corrected as soon as they become crucial to the playing strength. Ivan Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 4h44mn 17s Objet : Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll ivan dubois wrote: > Thanks ! > I think I agree with everything you said. > After some reasoning, I changed my opinion about the practical scalability of > Mogo. It does have some missconceptions about eyes, but as you said, it can > be corrected by the UCT part. I tried to find a situation where the UCT part > does not help until the situation comes to a conclusion, with no success. So > you are probably right, maybe I will give some more thought about it, or not > :) > > But I stay on my position that the theoritical "infinite scalability of UCT" > doesnt give any hint about whether or not it is scalable in practice. I think > you made my point clear : From a pure theoritical point of view, it has no > advantage over a simple mini-max solver. Given that a mini-max solver is NOT > considered scalable in practice, I see no reason why people would see this > property of UCT as an indication of its scalability. > This is still nonsense. UCT in actual real world "PRACTICE" responds dramatically to more hardware, how can you say it's not clear whether it's scalable in practice?What is practice to you? As far as mini-max, that is also scalable in the real world that I live in. Aya is an example of a reasonably good mini-max player that scales.The theoretical properties of scalability hold in actual practice. If you mean that we will never see in our lifetimes real world hardware fast enough to see it play perfectly, everyone already knows this, it's not any kind of revelation. (However I'm surprised at how many people get hung up on this point - thinking it is somehow relevant as a proof that the idea of search is totally useless.) The property we are interested in is that we can always expect an increase of playing strength by doing one or more of the following things: 1. let it think longer. 2. let it think faster in the same amount of time. 3. continue to improve the knowledge. 4. continue to improve the efficiency of the whole system "infinitely scalable" is a poor term since there is a finite limit. The finite limit is perfect play and as I said, we don't actually expect to achieve that. - Don > Ivan > > > - Message d'origine > De : Weston Markham <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Mercredi, 23 Janvier 2008, 0h41mn 08s > Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll > > (I typed the following up earlier today, before other people cast some > doubts about what "infinite scalability" means. Perhaps it is
Re : [computer-go] Is MC-UCT really scalable ... is a troll
Hi Alain, Sorry for being so insistant : >No i just said that, unless i really understood nothing, i read here from well >known competent persons that MC+UCT scales infinitely , and would reach perfect >play with infinite computational resources, and this is theoretically proven >(which is not the case for classical program like our beloved GNU Go). This is absolutely true. Now this can also be said for a mini-max solver (my point). >So MC+UCT scales. (even against humans, martians, trolls, computers, gods ... >:) The conclusion does not follow. The fact that it eventualy reaches perfect play with enough computing power does NOT mean that it scales well. Proof : A mini-max solver does reach perfect play with enough computing power BUT does not scale. Actualy, this theoritical property is a NESCESSARY condition for UCT to scale, but it is not a SUFFICIANT condition. The scalability of UCT has been "proven" by its outstanding results and Don's experiments, not by mathematics. Ivan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Thanks ! I think I agree with everything you said. After some reasoning, I changed my opinion about the practical scalability of Mogo. It does have some missconceptions about eyes, but as you said, it can be corrected by the UCT part. I tried to find a situation where the UCT part does not help until the situation comes to a conclusion, with no success. So you are probably right, maybe I will give some more thought about it, or not :) But I stay on my position that the theoritical "infinite scalability of UCT" doesnt give any hint about whether or not it is scalable in practice. I think you made my point clear : From a pure theoritical point of view, it has no advantage over a simple mini-max solver. Given that a mini-max solver is NOT considered scalable in practice, I see no reason why people would see this property of UCT as an indication of its scalability. Ivan - Message d'origine De : Weston Markham <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mercredi, 23 Janvier 2008, 0h41mn 08s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll (I typed the following up earlier today, before other people cast some doubts about what "infinite scalability" means. Perhaps it is helpful.) I think that Alain was specifically referring to a property of UCT, whereby given that a winning line of play exists, the probability that the algorithm has discovered one such line & settled upon it approaches 1 as time approaches infinity. I believe that this has been proven. And no, this theoretical result does not represent any intrinsic advantage over a calculation of the minimax value. (Someone should feel free to correct me if there is a stronger theoretical result that I am not aware of, though.) I think it is important to understand that unless you restrict UCT from exploring some correct lines of play, this "infinite scalability" will still be true. And, it is true regardless of what moves have been preferred/pruned/whatever within the MC playouts. (Or whatever one does at the leaf nodes; it need not be MC at all, as long as the UCT tree eventually gets expanded as the node is revisited.) This is not to say that this particular property of UCT is sufficient in order for us to claim that UCT is scalable in practice. My point is rather that noone is claiming "infinite scalability of MC", but rather scalability of UCT. When you combine that with the fact that UCT has been very successful at 9x9 go, (and scalable across a wide range of time limits) it seems to be reasonable to expect more of the same in 19x19. (Which is what concerned the original poster.) Also, one should expect that the UCT portion of MC-UCT will tend to eventually "fix up" any systematic errors that are made by the MC playouts. I have one other point I'd like to make, in regard to "light" versus "heavy" playouts: Even "light" playouts do not actually use a uniform distribution, due to the quasi-eye rule that is generally used. I think that there is every reason to expect that other "nonuniform" playout policies further outperform "light" playouts in every practical way. Granted, it is possible to introduce "severe misconceptions" when one incorporates knowledge into one's playouts. But even in that case, one can still fall back on the fact that UCT is cleaning up after one's mistakes: the eventual behavior, given enough time, is still perfect play. (And of course it is not as if people blindly adjust the monte carlo policies without checking the revised versions for "severe misconceptions".) Weston On 1/22/08, ivan dubois <[EMAIL PROTECTED]> wrote: > I think there is some missconception about this "infinite scalability of MC" > stuff. > Theory is only usefull when the model it is based on shares important aspects > with reality. > In theory, 19*19 Go is a finite game, wich can be analysed in a finite amount > of time. So ANY algorithm that solves the game at some point is, in theory, > infinitely scalable. For example, the folowing algorithm is infinitely > scalable : >Analyse the complete mini-max tree of the game. If enough time to finish, > returns the correct move, if not, return a random move. > > Now, is this algorithm really scalable, in practive ? Of course not. > > I support the idea that MC is infinitely scalable (in the reality) ONLY if > the play-out part does not have severe misconceptions. So i think that > currently, only MC based on uniform playouts is infinitely scalable. > It is well know that even Mogo has troubles with big eyes (he thinks a big > eye gives life, wich is false). This problem can not be solved with more > computing power (excep absurdly big, of course you can always mini-max to the > end). > > - Message
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Don, I was referring to this exact sentence from Alain : "Infinite scalability is a theoricaly proved property, so please don't feed the troll :-)" Do you agree with me that such a claim requires a mathematical definition of what "A scalable algorithm" is ? If this definition is not the one I used, could you please tell me what it is ? Now about the PRACTICAL scalability of MC, this is a completetly different matter : Thats my point. Ivan - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 22 Janvier 2008, 23h28mn 09s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll ivan dubois wrote: > I think there is some missconception about this "infinite scalability of MC" > stuff. > There is no misconception. This is clearly a PRACTICAL concept. > Theory is only usefull when the model it is based on shares important aspects > with reality. > Which it does clearly. > In theory, 19*19 Go is a finite game, wich can be analysed in a finite amount > of time. So ANY algorithm that solves the game at some point is, in theory, > infinitely scalable. For example, the folowing algorithm is infinitely > scalable : >Analyse the complete mini-max tree of the game. If enough time to finish, > returns the correct move, if not, return a random move. > > Now, is this algorithm really scalable, in practive ? Of course not. > This is not a scalable algorithm, it only solves the game and it takes too long for that.Put an evaluation function and iterative deepening and it's an example of an algorithm that scales, but very poorly. (Unless it's really implemented well with alpha/beta, progressive selectivity, excellent evaluation, etc.) > I support the idea that MC is infinitely scalable (in the reality) ONLY if > the play-out part does not have severe misconceptions. That's not the definition of infinite scalability.You seem to believe that infinite scalability is suppose to mean that it plays perfectly with a few seconds of thinking time.Infinite scalability simply means you can add a modest amount of time and expect to see a tangible (we are talking reality here) improvement.Nobody seriously expects perfect play with a few minutes of thinking and you are way off base if you thought that. > So i think that currently, only MC based on uniform playouts is infinitely > scalable. > I don't know what you mean by that, but heavy play-outs will ALWAYS outperform uniform random play-outs and any number of play-outs. Unless the heavy play-outs are actually horrible wrong, but I'm talking about anything proven to be superior at low levels such as the heavy play-outs of every MC program today. > It is well know that even Mogo has troubles with big eyes (he thinks a big > eye gives life, wich is false). This problem can not be solved with more > computing power (excep absurdly big, of course you can always mini-max to the > end). > > - Message d'origine > De : Alain Baeckeroot <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Mardi, 22 Janvier 2008, 22h13mn 26s > Objet : Re: [computer-go] Is MC-UCT really scalable ... is a troll > > Le mardi 22 janvier 2008, David Fotland a écrit : > >> The UCT-MC programs do particularly well against traditional programs >> because they expose the brittleness inherent in the pattern databases they >> use. Strong humans are not so easily beaten by playing unconventional and >> somewhat inferior moves. >> >> > I think Remi posted a game of CrazyStone on 19x19 commented by one pro > who said "this move is 2 dan level". > So far no go program got such analyse, and the also the huge novelty > provided by MC/UCT programs is they have a _real_ strenght with their > own style, like humans: > play solid when winning, and play hamete (tricky moves) when losing. > > On kgs MC programs played hundreds (if not thousands) games against humans, > and no doubt they fully merit their rank, and no doubt they are improving. > > Infinite scalability is a theoricaly proved property, so please > don't feed the troll :-) > > Alain > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > _ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail > http://mail.yahoo.fr > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > >
Re : Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Could you please tell me what definition they use ? Dont forget, i am talking about a theoritical definition, wich can support mathematical analysis. Ivan - Message d'origine De : Christoph Birk <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 22 Janvier 2008, 23h38mn 30s Objet : Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll On Tue, 22 Jan 2008, ivan dubois wrote: > When people say that MC infinite scalability is mathematicaly proven, > they do not refer to the definition you give, they refer to the > definition I used. No, they don't. At least not most people on this list. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Hello Christoph, I agree with you that this algorithm is not scalable if you use this definition, but : When people say that MC infinite scalability is mathematicaly proven, they do not refer to the definition you give, they refer to the definition I used. If you want to do a theoretical analysis of MC scalability with your definition, you will first have to define exactly what you call "a better move". This might be tough. Even if you managed to do that, you would see that MC is not scalable with this definition, because obviously, more computing power can, in some occasions, provide a worse move (what ever you call a worse move). Ivan - Message d'origine De : Christoph Birk <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 22 Janvier 2008, 22h50mn 29s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll On Tue, 22 Jan 2008, ivan dubois wrote: > in theory, infinitely scalable. For example, the folowing algorithm is > infinitely scalable : >Analyse the complete mini-max tree of the game. If enough time to > finish, returns the correct move, if not, return a random move. > Now, is this algorithm really scalable, in practive ? Of course not. I have to disagree. The above algorithm is not scalable in a sense that more time leads to better moves. Ie. It returns a random move given 1 minute, 1 hour or 1 day of (current) CPU time, while a scalable algorithm should return a better move the longer it runs. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable against humans?
Hi Don, I agree that the very best players can know, if they are given enough time, whether they are winning or not. But here we are talking about professionnal players. But you know, even a 9d Pro, probably cannot be certain of the outcome at the yose stage, if he plays a blitz game. Still, if he thinks he is leading, he will always play "normal" moves, defending his territories instead of playing strange and apparently useless consoliding moves like a MC player would do. Yet if he thinks he is losing, he will probably try unsound invasions and try hopeless things exactly like a MC would do, when the outcome of the game matters for him. For example, i am 4d on KGS, and when there is some trade to be made beetwen points and safety, this is always a tough decision for me. Because i dont know how many points i can concede exactly, and i dont know how risky some line of play realy is. I have lost a lot of games because i made the wrong choice in such situations. So i think you are over estimating the "evaluation" ability of human players. This is the reason why human generaly dont play like MC, because they do not have the same informations. MC are good at knowing what the situation is, humans are good at playing moves that tend to maximise territory most of the time. Humans and MC just do not have the same strengh. Somehow, i would say that MC is more intelligent, because it relies on understanding the situation rather than patterns and reflexes. - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 22 Janvier 2008, 22h22mn 42s Objet : Re: Re : [computer-go] Is MC-UCT really scalable against humans? I agree that probably most players play as you say.But it's difficult for me to believe that the very best players don't know if the are wining or not. I think if I had the skill of a professional, I would make it my business to know, ESPECIALLY if it were really close. I'm talking about the cases where a UCT player thinks it's winning with high probability. If a UCT player knows this, I'm sure a really strong professional knows. It's a different story when several groups are in question and a UCT players is "skillfully" assessing the odds.But I don't think we are talking about that case.UCT doesn't start playing too bizarre until a win is in the bag for one of the players. I've seen this for myself.The score gets about 95% but there are still many ways to lose if you play stupid, but the MC player knows carefully takes care of business - sealing this and that off so that there is no chance. Many times I've seen it throw away 1 or 2 points by not claiming an extra point right next to the point that it does claim.In some of those cases I counted it off myself and to my amazement it just didn't need that point and it was probably a random choice. But in those cases there was no chance of tricking a human. Nevertheless, the human sometimes is under the impression the program made a series of "really bad" moves and STILL WON, making the human feel frustrated.But really it was not like that at all. - Don ivan dubois wrote: > Hello Don, > > I think you are mostly right, but there is something you seem not to realise. > MC players are very good at "scoring". They know when they will win for sure > by 0.5. However, human players, even strong players, generaly never have such > accurate counting skills. So if they are ahead by 0.5, there is no way they > can anticipate it at as a sure win, because it would require amazing couting > skills. Actually, a lot of strong players never count during the course of a > game, especialy during fast games. > So often, the most rational way of playing is to be conservative with the > points you have, and just always play the natural, conservative defending > moves. It may be too hard for human to reason about "probability of winning", > it is easier to reason about points you have or not. > Of course, i think the ultra rational way based on accurate couting by MC > programs is a great strength they have. Its a specific strength of MC that > human, unfortunately for them, do not have. > _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable ... is a troll
I think there is some missconception about this "infinite scalability of MC" stuff. Theory is only usefull when the model it is based on shares important aspects with reality. In theory, 19*19 Go is a finite game, wich can be analysed in a finite amount of time. So ANY algorithm that solves the game at some point is, in theory, infinitely scalable. For example, the folowing algorithm is infinitely scalable : Analyse the complete mini-max tree of the game. If enough time to finish, returns the correct move, if not, return a random move. Now, is this algorithm really scalable, in practive ? Of course not. I support the idea that MC is infinitely scalable (in the reality) ONLY if the play-out part does not have severe misconceptions. So i think that currently, only MC based on uniform playouts is infinitely scalable. It is well know that even Mogo has troubles with big eyes (he thinks a big eye gives life, wich is false). This problem can not be solved with more computing power (excep absurdly big, of course you can always mini-max to the end). - Message d'origine De : Alain Baeckeroot <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 22 Janvier 2008, 22h13mn 26s Objet : Re: [computer-go] Is MC-UCT really scalable ... is a troll Le mardi 22 janvier 2008, David Fotland a écrit : > > The UCT-MC programs do particularly well against traditional programs > because they expose the brittleness inherent in the pattern databases they > use. Strong humans are not so easily beaten by playing unconventional and > somewhat inferior moves. > I think Remi posted a game of CrazyStone on 19x19 commented by one pro who said "this move is 2 dan level". So far no go program got such analyse, and the also the huge novelty provided by MC/UCT programs is they have a _real_ strenght with their own style, like humans: play solid when winning, and play hamete (tricky moves) when losing. On kgs MC programs played hundreds (if not thousands) games against humans, and no doubt they fully merit their rank, and no doubt they are improving. Infinite scalability is a theoricaly proved property, so please don't feed the troll :-) Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable against humans?
Hello Don, I think you are mostly right, but there is something you seem not to realise. MC players are very good at "scoring". They know when they will win for sure by 0.5. However, human players, even strong players, generaly never have such accurate counting skills. So if they are ahead by 0.5, there is no way they can anticipate it at as a sure win, because it would require amazing couting skills. Actually, a lot of strong players never count during the course of a game, especialy during fast games. So often, the most rational way of playing is to be conservative with the points you have, and just always play the natural, conservative defending moves. It may be too hard for human to reason about "probability of winning", it is easier to reason about points you have or not. Of course, i think the ultra rational way based on accurate couting by MC programs is a great strength they have. Its a specific strength of MC that human, unfortunately for them, do not have. - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 22 Janvier 2008, 21h47mn 39s Objet : Re: [computer-go] Is MC-UCT really scalable against humans? David Fotland wrote: > I didn't say that :) Please read what I wrote. > No, I was thinking ahead, not quoting you. I was just covering my bases, anticipating what I thought my be a likely response (and not necessarily from you.) > The UCT programs often find moves that are unconventional. This makes > patterns that aren't in the database, so the traditional programs can't > cope. People are a little more flexible, especially strong players, and can > still find good responses to unconventional moves. > > I don't know what you mean by "unsound". That's chess terminology and I > think it refers to a trick move that should lead to a loss against good > play. Unsound just means a move that is really wrong. It could be tricky to find the right move or might just be an outright bad move. > In go we talk instead about moves that lose points. UCT programs > often play moves that clearly lose points in an attempt to maximize the > probability of winning. These moves are unconventional because people learn > the optimal moves in standard situations. Weaker players and traditional > programs can have trouble finding the best response to these non-optimal > moves. There is an isssue whether these are really non-optimal or not. To me an optimal move preserves the win if a win is possible and nothing else matters.I think it's elegant to not play greedy when another moves is better in the game-theoretic sense. > So the UCT programs gain strength for two reasons, first, because > the maximize the probability of winning rather than maximize the score. And > second because this causes them to play unconventional moves, which make the > game more difficult for their opponent. They don't do this.By the time they start playing unconventional moves they have already won or lost the game.I think this is a huge misconception.It's true that they may fail to defend a big group and attack a small group because it is slightly more likely to win - but that's a pretty rational thing to do - going for the big group may be more human-like but less logical so I don't care if that confuses a weaker opponent.(I suppose the blunder the weaker player would make is to defend the big group and not give due resistance to defending the small group - but for sure there is no good reason to program a program to make the irrational decision because it makes weak players more comfortable.) > There is nothing inherently wrong > with playing unconventional moves that are still good. Strong players do it > whenever they can to make the game more difficult. > I would imagine that the stronger you are, the more you would be concerned with playing for the win instead of points. > David > > >> Please don't say the style is to "find an unsound move that >> is >> difficult to defend", that's not what it's trying to do, it's just >> trying to find a move that it is IMPOSSIBLE to defend, and if it >> >> - Don >> >> >> >> David Fotland wrote: >> >>> I share this opinion. 9x9 was a good simple test to get things >>> >> started, but >> >>> go is a 19x19 game. 9x9 has limited interest. An analogy for chess >>> programmers would be if a group of people worked on programs to solve >>> >> rook >> >>> and pawn endgames. This kind of chess endgame is a good test to try >>> >> out >> >>> algorithms, but if they claim to be making strong chess programs, at >>> >> some >> >>> point they have to implement the full game. In go it turned out that >>> >> to be >> >>> good at 19x19, some new algorithms were needed (patterns and heavy >>> playouts). I think that to take the next step in 19x19 strength the >>> programs will need to be stronger at life and death. >>> >>> >>> >>> The UCT-MC program
[computer-go] Bradley-Terry Model
Hello all, Does someone know about an implementation and/or an algorithmic description of the Bradley-Terry model ? Thanks and happy new year ! _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] time_left command on CGOS
I found the problem. My response to "list_commands" was wrong, the commands were separated by spaces, instead of line feed. It is working now, thank you very much for your help :) - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Jeudi, 20 Septembre 2007, 22h42mn 29s Objet : Re: Re : [computer-go] time_left command on CGOS -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 You are right, It's the list_commands I use. I think GTP shouldn't have both because it's extra work for nothing and has confused me before. Do you implement time_settings? If you don't have that or respond wrongly to it, the server (or perhaps it's the client) will not send the time_left command. - - Don ivan dubois wrote: > Thanks, but i dont receive the "known_command" either :( > I added "known_command" to the list "list_commands" also, because i thought > it could be the problem, but it is still not working. > > > > - Message d'origine > De : Don Dailey <[EMAIL PROTECTED]> > À : computer-go > Envoyé le : Jeudi, 20 Septembre 2007, 21h37mn 18s > Objet : Re: [computer-go] time_left command on CGOS > > > CGOS does not send that command unless you tell it that it knows the > command using the "known_commands" > > ivan dubois wrote: >> Hello to all. >> I have put my program on cgos, but i never receive the "time_left" command. >> Is it normal, or am i doing something wrong ? > > >> >> _ >> >> Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail >> ___ >> 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/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG8ts0DsOllbwnSikRAqtQAKCTtqirDxpeTeAK5Dc7r9r1I1OudQCfbqOU cZOu+emQkdF4e4K7AFWggaA= =foHI -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] time_left command on CGOS
Thanks, but i dont receive the "known_command" either :( I added "known_command" to the list "list_commands" also, because i thought it could be the problem, but it is still not working. - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Jeudi, 20 Septembre 2007, 21h37mn 18s Objet : Re: [computer-go] time_left command on CGOS -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 CGOS does not send that command unless you tell it that it knows the command using the "known_commands" ivan dubois wrote: > Hello to all. > I have put my program on cgos, but i never receive the "time_left" command. > Is it normal, or am i doing something wrong ? > > > > _ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFG8svuDsOllbwnSikRAu0xAKDzYQDU3+8p5LkfgAQgWA4Sh0hw2QCgzED4 IJejdXhKjIa8qZNYBLtVcnQ= =V1ig -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] time_left command on CGOS
Hello to all. I have put my program on cgos, but i never receive the "time_left" command. Is it normal, or am i doing something wrong ? _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)
I dont understand how you can reduce the variance of monte-carlo sampling, given a simulation can return either 0(loss) or 1(win). Maybe it means trying to have mean values that are closer to 0 or 1 ? - Message d'origine De : Matt Gokey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Mardi, 6 Février 2007, 14h33mn 09s Objet : [computer-go] Monte Carlo (MC) vs Quasi-Monte Carlo (QMC) Upon continuing to learn about the general Monte Carlo field, I've found it seems there is a general consensus in this community about a distinction between Monte Carlo (MC) and what appears to be commonly called Quasi Monte Carlo (QMC). MC is defined as using random/pseudo-random distributions and QMC using more deterministic or designed distributions that fit the problem better. Just do search on google web or scholar and you'll get a wealth of hits. But here are a few links to documents or pages that specifically address this terminology: http://www.arts.cornell.edu/econ/CAE/final.pdf http://www.mas.ncl.ac.uk/~ngl9/docs/MCQMC.pdf http://www.math.hkbu.edu.hk/~gwei/sci3510/ch1.pdf http://mathworld.wolfram.com/MonteCarloMethod.html http://mathworld.wolfram.com/Quasi-MonteCarloIntegration.html It also seems that today quite often "Monte Carlo" generally is used to describe any kind of statistical sampling using random or other distributions to approximate solutions to problems like David Doshay pointed out. So would it be helpful to distinguish between MC go and QMC go programs - maybe a little. Since I'm just learning about this I might be misunderstanding some concepts. But besides doing obvious things like minimizing memory usage and optimizing code so that you can increase the sample size, there are many well known strategies to decrease the variability of the simulation. These are called variance reduction techniques. Generally Monte Carlo standard error decreases based on the square root of the sample size (quadrupling the sample size cuts the the standard error in half). I would think in part this would depend on the problem, so not sure if this applies to MC go or how to measure. Variance reduction methods are used to improve the distribution improving the results (error) without increasing the simulation size as much. Here is a list of some of them without any explanation (searching on any of these terms with monte carlo should turn up lots of hits): -Common Random Numbers -Antithetic Variates -Control Variates -Importance Sampling -Stratified Sampling -Conditional Sampling -Systematic Sampling Most of the research using MC methods seems to be for numerical integration, finance applications, and physics applications; not applied to game theory. It may be be challenging to understand how to translate these ideas to MC go or whether they would be helpful. -Matt ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.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
Isn't UCT equivalent to Alpha-beta with some cleaver pruning rules ? - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Vendredi, 26 Janvier 2007, 19h51mn 10s Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time >Part of my procrastination is that I'm not sure how to make UCT >scale to a large number of CPU's.I am an expert in scaling >alpha/beta to a large numbers of processors (I did this with Socrates >on 1836 processors a few years ago) but it's different with UCT >which is inherently serial. - Don ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] an idea... computer go program's rank vs time
You missunderstood my point. However, I admit it was not clear. What i wanted to say is this : Given a fixed amount of time, strength of monte-carlo algorithm will decrease exponentialy when boardsize increases. It does not mean that monte-carlo does not scale well with time on 19*19. Of course, it all depends on the referential you use to measure strength. By the way, it is not a critisism towards UCT : actualy I do think monte-carlo is the key to build realy strong programs. I just wanted to state that scaling with computation-time is not the only thing that matters. Scaling with board size matters too. It was not another criticism towards you opinion either. - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : computer-go Envoyé le : Vendredi, 26 Janvier 2007, 19h05mn 40s Objet : Re: Re : [computer-go] an idea... computer go program's rank vs time On Fri, 2007-01-26 at 13:38 +0000, ivan dubois wrote: > However, if you take for example a computer programm that does > straight UCT (global UCT, with no sub-areas), then i believe it can > not scale well when board size increases. Because the branching would > factor increase proportinaly to the size of the board, and therefore > the computation time for an equivalent search deapth will increase > exponentialy. > Any thoughts ? This can be tested directly. In my own experiments 19x19 improves very rapidly in UCT with each doubling of the number of play-outs. Of course someone will say, "yes, but that won't continue" and I will have no way to refute their intuition. I am presenting real evidence that it scales at least as far as I can test, and nobody has presented any evidence whatsoever to the contrary other than gut feelings. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.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
Hello. Just my grain of salt : I think it is relevant to consider strength as a a function of time AND board size. I have the feeling that, for humans, board size doesnt matter very much, whereas for computers, depending on the algorithm they use, it can be an extremely important factor. The reason would be that human are very good at breaking the board, mentaly, into mostly unrelated areas. However, if you take for example a computer programm that does straight UCT (global UCT, with no sub-areas), then i believe it can not scale well when board size increases. Because the branching would factor increase proportinaly to the size of the board, and therefore the computation time for an equivalent search deapth will increase exponentialy. Any thoughts ? - Message d'origine De : Don Dailey <[EMAIL PROTECTED]> À : Nick Apperson <[EMAIL PROTECTED]> Cc : computer-go Envoyé le : Vendredi, 26 Janvier 2007, 14h10mn 08s Objet : Re: [computer-go] an idea... computer go program's rank vs time On Fri, 2007-01-26 at 02:41 -0600, Nick Apperson wrote: > I am not trying to say that you don't know what you are talking about, > but how are you so sure that we must be on the linear part of the > curve? Based on what you said, I estimate your ideal (non empirical) > formula to be something like the following: > > S = P * (1 - e^-kt) > > where S is skill level and P is perfect play and k is some constant > specific to the game. In fact this is an ideal formula that should > apply given the reasonable assumption that the chance of reading one > unit of skill is proportional to the amount of time taken and the > amount left to be seen. This makes sense assuming a very specific > distribution of the difficulties of different items that can be seen. > That distrobution would have to have all units capable of being seen > as equally likely to be seen. I think this could be a good > theoretical model. > > > Anyway, I would like to see you make more specific claims with formula > and justifications for them. Vague statements about linear > relationships that taper off and how we are clearly not anywhere near > the top help nobody. You seem to know a lot about this. I would > appreciate it if you would share your reasoning. You seem pretty > skeptical of intuition. So, what is the reason you believe these > things about go? Here is why I feel as I do and where I think the burden of proof is: All computer games of perfect information that I am aware of follow this curve. Chess, checkers, Armimaa, Othello, Go and others. So it seems to have nothing to do with the branching factor of the game. This curve is shown to also be true (even more-so) in HUMAN play, at least in Chess and anywhere from a fraction of a second per move to postal chess. >From a perfectly logical point of view, what is the most reasonable conclusion to come to about this? Furthermore, I have anecdotal evidence (which you should always be skeptical of but I present nonetheless) that strong human players are not good judges in these matters because their ego's are involved. In Chess, there were some more humble players who understood the curve right away but they were the minority. In short, strong players will generally take the point of view that their game is not subject to mere computation, but to skill which only they possess. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
