[computer-go] Re: Open source real time Go server
Petr Baudis wrote: This seems like not very productive line of argumentation unless preceded with more exact definitions of strong. My only claim is that it is a hard problem. That is unobjectionable no matter how you define strong (obviously: random strong perfect) I can't understand why you object on this. Actually, there is a thread about exactly this on fuego-devel In fact it is not exactly this it is a different approach. The post in fuego-devel tries to determine the status of each point of the board. That is not a good idea with or without MCTS because go is about trading. (Furikawari) My different approach is determining by how many points the simulated games are won. Only in yose the IQR becomes narrow enough to see how much territory is still in dispute. Stefan Kaitschick wrote: If resources were no problem, the best way to estimate the score would probably be to have an MC program find the komi that results in a 50% winrate. Yes! That is my proposal. Saying an MCTS program is happy (60%) or unhappy (32%) does not inform too much to non-computer-go observers. If you talk about winning rate they understand the probability that the program wins which is not the case. Telling them the program is happy, but would end being happy if it had to win by 20 additional points is crystal clear. The correct way to determine the komi shift would be to try all possible values. Since that is expensive, my proposal estimates the komi shift from one single 20K run by studying the distribution. Of course, it is only an estimation and the other method would be more accurate. Additionally, the estimator gives a confidence interval or remembers the observer that score estimation in move 60 is a fallacy. We have to live with the two facts: * Each board position has a value. (The game satisfies the conditions of the minimax theorem.) * Pretty much every position has a value that is computationally untreatable. And this applies to human estimators as well. They only score according to established practice, which is something that is revised as new empirical evidence shows up. Scoring at move 60 is just an educated guess. (Of course people will more likely accept the guess of a 9d than the guess of a 15k.) The cool part is the estimator can tell you the difference when it is just making an educated guess and when most of the territory is already sold out with few points in dispute. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Open source real time Go server
Hi 1. Just a small precision first: Ingo Althöfer wrote: Terry McIntyre wrote: ... My pet peeve is the KGS score estimator, which is often wildly wrong As explained by others a strong SE for ALL positions is equivalent to a strong program. This is only true if you replace the word “strong” by “perfect”. It is trivial, that a perfect evaluation function gives a perfect player using a 1-ply search, but that is not true for strong evaluation functions. Converting a strong evaluation function into a strong program is still a hard problem. “Almost” good moves are frequently worse than random moves. (E.g. a move that “almost saves” a group that cannot be saved or “almost kills” a group that cannot be killed gives one prisoner to the opponent and wastes one turn. This is worse than pass while random moves are with a high probability better than pass.) 2. Now my proposal: An MC based SE (Score Estimator). Use a strong MCTS program unmodified, except in a small detail to collect data about by how many points each simulation is won. Play a feasible number of simulations like 20K. Build the distribution of the result (= The histogram counting how many wins were found by each result). Otherwise, let the program follow the tree as it does unmodified. In this distribution find the 3 quartiles (the komi shift that produces Q1 25%-75%, Q2 50%-50% and Q3 75%-25% wins for each). If IQR (Interquartile range) = Q3-Q1 some threshold (say 25 points) output: Q2 as “B+3.5 with large error margin” else output: Q2 + IQR as “B+3.5 IQR(W+1.5, B+11.5)” This would be a state of the art SE and the number of simulations could also be a parameter controlled by the user to adapt the precision to his hardware and patience. After all, it is easier to get a SE from a strong program than the other way round ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Fuego 04 native Windows
Michael Williams It has been some time since you made this. It was last summer (2009). I needed a strong program to test an idea on it that worked well on a weaker program. I haven't shared this with the list yet, because I am now modifying it and cannot spend as much time as I would like. What I need to prove is that Fuego + mod wins against Fuego without mod. I do not plan to continue using Fuego after that since I have my own platform. Did you have to make changes to any of the original Fuego files? Yes. You can sort the files by date to see which have been. I think all modifications have the remark // WinFuego04 (At least it should be so.) Most of the modifications are: 1. Adding an explicit (type) to make the compiler accept a flexible use of different types. Of course, I assume the original programmer did that on purpose and the program is debugged, so I is just telling the compiler to ignore it. 2. Adding a #pragma to ignore a warning for the same reason. 3. Includes to WinFuego_linux2win because the time library used is not the same a the libraries available in MS c++ This translates some functions I couldn't find directly to their Windows API equivalent. I don't remember if there are more, but none is functional. I mean I did not change the behavior of the program in any way. (I did so later after studying what the program did when I could run it.) I'm asking because I'm trying to figure out what would go wrong if I dumped current Fuego files into the Windows-buildable source that you provided. If the new Fuego does not use more boost functions, the subset of boost libraries included should be enough. Otherwise you should find the missing boost files from the same version of boost. If you try to compile the new files, assuming the architecture of the program did not change, you will get the same (or similar) errors and warnings I got and you have my files to see how I corrected it. It is a tedious work but it can be done since I did that already. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Biasing nodes according to pattern gammas
Petr Baudis wrote: I wonder now, do you use separate set of gammas for simulations and node biasing? Since I've found that the performance seems very bad if I don't include some time-expensive features, since the gammas are then very off; I will probably simply generate two gamma sets, but perhaps it's enough to do some trick like merging features by computing weighted (geometric?) averages? Rémi Coulom answered: I learn two sets of gammas separately for the two sets of features. I don't get it. Why do you need two sets one for the tree and one for the playouts? To learn gammas, I use a database of games. The patterns compete, some of them win. This is computed using a Bradley-Terry model. At that time moves are just moves, not tree moves or simulation moves. When that offline learned model 'best' fits the moves played (55000 games x 100 moves each in my case) I am done, I have a set of gamma values. I use these for playouts and biasing the tree. What else are you doing? How do you compute a set for the playouts and a set for the tree? Do you adjust gamma values one by one playing games? Of course, I guess this is not very useful for 9x9 that's why I took the (probably wrong) decision to work in 19x19 only. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Fuego parameter question
To run Fuego in Windows, there the build I posted in: http://www.mail-archive.com/computer-go@computer-go.org/msg12208.html There is both source and binary. It is 40% faster than the cygwin version and more efficient in all senses, just because it is a native build. cygwin has serious limitations. When I did a lot of evaluation using Mogo as an oracle I finally had to use a Linux box, because cygwin is not able to run more than 15M sims (from Mogo) reliably. (If you run less than 15M kill the process and run it again you can use it without limits.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Kinds of Zobrist hashes
1. The 3 hashes: As Eric Boesch and Álvaro said, you can get the same codes as in the Black[], White[], Empty[] scenario using only 2 BlackXorEmpty[] and WhiteXorEmpty[] 2. What does make sense is making a difference between a POSITIONAL hash and a SITUATIONAL hash. The positional hash is the typical Zobrist hash of just the stones. The situational hash is the XOR of the positional hash and all moves forbidden by ko or superko (if any). I use another table of 361 64 bit codes for each forbidden move. At least, the tree search must have this in consideration, because the same stones but different legal moves, it is not the same position. I guess most programs do this one way or another. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Kinds of Zobrist hashes
Álvaro Begué wrote: The legal moves might be the same now, but they might be different after I perform a particular move. You are right. Looks like my solution is not perfect, but it works good enough. I have seen trouble, before I implemented it, because the transposition table identified the same position in different situations. My solution worked, but, as you say it may not be perfect. Anyway, it is good enough for ko and my version of superko is a simplification restricted to the last 8 moves. Basically, triple ko and double ko of a group with one eye are the only superko sequences I have seen in serious games. I though it was good, now I have added a remark to the source code just in case some weird behavior appears. Thanks. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] still an outstanding command
I think it is OK to lose the one game where it crashes, but it should be able to restart for new games at least. Martin You can restart everything Ok, but you have to kill the process java.exe and then run kgsgtp again. When the program crashes, the clock is still running, I think. If it is so, I think it is correct to be able to continue the game. You lose the time involved and any online learned info. Looks fair to me. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] [Fwd: Announcement ICGA Events 2010]
Is it possible to participate in these tournaments remotely? I think I would like to start participating in these, but I certainly have no budget (or time) to travel outside of Europe. :-( Petr Pasky Baudis For the ICGA Computer Olympiad, there should be no problem. This year all participants except myself used remote computers. I carried my i7 to the competition facilities. (I do live in Spain, but over 2000 Km away from Pamplona in the Canary Islands, so it was complicated to fly with the computer 3 times.) Hideki Kato operated his computer in Japan remotely and was also operator for Zen in communication with Yamato who was in Japan. Fuego used a computer in New York (maybe not for all the games), Mogo used the Huygens cluster and Professor Chen had his students operating in the US. Neither will I be able to travel to Japan (unless I find a sponsor ;-)) and I also expect to participate again with better results, of course. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Fuego 04 native Windows
I have made a native Windows Fuego build compiled with MS Visual Studio 2008. Thanks to the Fuego team for making such a nice program free software !! I will use it to measure some tree metrics to tune my own program and for a validation experiment for an evaluation function I have developed. I will post results when I have any. To test the binary I made it play on todays KGS tournament and won 1 game of 3 against MFOG and 1 game of 3 against Aya + all the other games. It was running on an overclocked (3.6 GHz) i7. The settings were: uct_param_search max_nodes 1250 uct_param_player reuse_subtree 1 uct_param_player ponder 1 go_rules kgs sg_param time_mode real uct_param_search number_threads 8 uct_param_search lock_free 1 uct_param_search virtual_loss 1 uct_param_search number_playouts 2 The binary does around 36k games/sec in the opening rising to 50-60k later. Which is a lot more than the 23.5K of the cygwin version. AFAIK it works Ok with multithreading with and without locking. It is also much smaller and has no .dll dependencies. If someone wants to test it more, it is here: http://www.dybot.com/fuego04nw/fuego.zip And the source code Windows developers always dreamt of but were too shy to ask ;-) (All relevant parts of boost included, 0 static lib dependencies, 0 dynamic lib dependencies, compiles with MS Visual Studio 2008 0 errors 0 warnings.) http://www.dybot.com/fuego04nw/fuego.7z (Compressed with 7z. 7z is free software available at: http://www.7-zip.org/ The command line version is the best option if you don't like programs integrating in Explorer.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Rules for remote play at the Computer Olympiad
About the thinking process log. Enabling debugging options can result in serious performance loss. In my system only the admin thread can do such things as tree dumps and that makes all other pawn threads idle. I don't think such preventive measures are justified. In case of doubt, it should be enough if the author can show that the program can repeat any suspectful move (even if it does not always play the same move, the played move should at least be among the best). If the program is local that should be enough. Remote programs cannot be controlled anyway. I think adding constraints to local programs makes the unfairness vs remote programs even worse. In case something has to be implemented it must be announced in advance. Questions: 1. What are the time settings for 19x19? 2. What are the days for 19x19? 3. Is hardware available from the organizers? At least, monitors and keyboards to avoid flying with non-critical and voluminous equipment. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] [Fwd: ICGA Events 2009 in Pamplona]
Good news! I am very happy the ICGA has chosen Pamplona. Other destinations (e.g. Beijing) are more attractive, but way out of my reach. I can travel to Pamplona easily, but cannot find the details. The website at http://www.icga.org/ is not updated and the attached .eml file contains 2 .pdf files coded by some mail protocol, but no mail program (Mozilla, Outlook) I have tried is able to extract them to .pdf files. Can someone place the .pdfs somewhere for download? Thanks. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] MoGo v.s. Kim rematch (Jason House's paper)
The approach of this paper is to treat all win rate estimations as independent estimators with additive white Gaussian noise. Have you tried if that works? (As Łukasz Lew wrote experimental setup would be useful) I guess there may be a flaw in your idea, but I am not a specialist. I will try to explain it. If it wasn't for the fact that the tree is learning, the probability of a playout through a node to win would be constant each time the node is visited. This is, of course, a simplification because the tree does learn, but, at least between playouts that are not very distant in time, it is true. So my argument holds to some (I guess, much) extent. The same applies to the RAVE estimator which is also the result of counting wins (assume P(win|that move) = constant) and dividing by some appropriate sample size. Therefore, these estimators follow a binomial distribution. It does converge to the normal, but with some fundamental caveat: Unlike the normal in which mean an variance are independent, in this case the variance is a function of p. The variance of the binomial = n·p·(1-p) is a _function of p_. Therefore, the variance of the normal that best approximates the distribution of both RAVE and wins/(wins + losses) is the same n·p·(1-p) If this is true, the variance you are measuring from the samples does not contain any information about the precision of the estimators. If someone understands this better, please explain it to the list. Jacques.* * ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Counting the final score with seki
Hi all, When you detect self atari in the playouts (something I haven't tried yet, but from recent posts in this group I am convinced that it is an important issue) a new problem arises: How can you score the board _fast_ at the end? My previous version killed all groups in seki and scanned starting from a stone in zig-zag: ^ ---(X)··· and (X)-- | | If the stone is black/white, it starts counting for +1 or -1 and changes the sign when the stone color changes. (Starting from a stone is easy because I keep lists of chains, while starting from a corner would require to find out who it belongs first.) This way of counting does not require looking for any neighbors and is really fast. But when self atari is avoided in the playouts, groups live in seki and counting dame points really fast is required. Of course, I can imagine how to do it using floodfill, what I want to know is if someone wants to share some better approach if there is one. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
Don Dailey wrote: [EMAIL PROTECTED] wrote: For those currently coding this up, I think the most important thing about this playout algorithm is that it is *temporary*. You will almost certainly be?replacing it with something different and better just a little bit down the road. So you probably don't want to worry about hair-splitting tweaks except as an academic exercise. Yes, I agree. Also my hair brained scheme of pre-generated tables of list traversal orderings was just an academic exercise as you say. But the problem is that when you do heavy playouts you have the same problem except that the probabilities of the legal moves are no longer equal. Unless, of course, the board system keeps a list of legal moves, not just empty points and own eyes in playout mode have zero score which is the same as if they were illegal moves. Am I the only one doing this? I don't know if the impact is measurable in strength or not. But as the game advances, the own eyes are found in the root position. When that happens, the bias applies to the same move in all the playouts. In this case the program is favoring systematically the exploration of a move for no reason at all and it is always the same move. Since the number of simulations is limited, that pays less attention to other moves. I don't know if it is bad, but at least it is ugly. ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper for AAAI (David Silver) PDF problem
Thanks, Hideki I have the same problem with version 7.0.7 of Adobe Reader but version 8.1.2 works fine. That was the problem. I used the automatic upgrade feature, but that only upgrades to the latest 7.xx version not to version 8.xx. Don Dailey wrote: ... this general distaste of feeling like a sucker for Microsoft. That's the real problem with Windows. I need a double boot, place the OS on a FAT32 partition and have a copy of every file + an image of the installed partition. Every day I fight against the operating system I have paid for and if the OS doesn't let me change it the nice way I have to do it the hard way. If I was starting now, I would be a Linux user. Unfortunately, there is not much I can do with incompatible systems. From time to time I install wine to see how far they are. If it can be used or not. Windows 95 could be purchased in floppy disk and that was 30 floppies the operating system of my dreams is Windows 95 bug free in 20 floppies ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper for AAAI (David Silver) PDF problem
Hi David http://www.cs.ualberta.ca/~silver/research/publications/files/MoGoNectar.pdf Your paper has a PDF problem concerning embedded font BXGQFO+CMR12. I have used different versions of Adobe Reader. I even updated one of the computers to the latest version and I still cannot read any mathematical expressions. I guess this applies to all Windows users. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
Jonas Kahn wrote: I guess you have checked that with your rules for getting probability distributions out of gammas, the mean of the probability of your move 1 was that that you observed (about 40 %) ? If I understand your post, there may be a misunderstanding by my fault. Here gamma is not a gamma function nor a gamma distribution but a constant. It is just the same Greek letter. I don't remember if it was in Crazystone's description or in some other paper I read to understand what Bradley Terry models are, I just got used to that notation. The best thing of BT models (for me) is the extreme simplicity at runtime (calibration may have more black magic) so: prob of move i = gamma[i] / SUMj gamma[j] where gamma[·] is a constant each pattern has. Setting those constants is the learning process. The 40% is obtained between move 20 and 119 of over 55K games. That is more than 5 M competitions. The patterns are learned for other move numbers as well. It considers the urgency modified by the first time the pattern appears. Also ko, but ko is learned to (hopefully) find ko threats, its impact on guessing is less important. It counts the number of times the first move was the right move, then the first + second, etc. The reason why two different ways of measuring the same: a. Probability expected for each move. b. Number of guesses of the best move, 2nd best, 3rd best, etc. don't match is mainly academic, because form a practical point of view, the important is to have a good move generator and (even more important) to understand its limitations. It cannot be considered as the only source of moves, but the first moves in terms of urgency are moves that should be paid attention. I admit, that what I call a probability distribution over the legal moves, is not really balanced I don't understand why, but, nevertheless, in terms of urgency, better moves get higher urgency. This is all I really need. Of course, I would welcome an explanation on why the 2 things don't match or if someone else can verify if his patterns give correct values. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
Hi Lukasz In Rémi's paper about Bradly Terry models he found a way to give a comparable gamma score to things that were different, for instance: capturing a stone v.s. a given 3x3 pattern. His model is much more general, but has less patterns (not at all around 200K patterns of my system). Additionally, my mask pattern only system has a reasonable a priori value: times_played / (times_played + times_postponed). But there is an additional issue handled by Rémi's system that is ignored by the naif system: The fact that some competitions are much harder than others. If the sum of concurrent scores to the average competition is, say 100, the value of winning a competition of sum 40 is obviously much less than winning one of sum 300. That is not included in the simple formula. Therefore, a simple intuitive idea if adding more for a the hard competition 300/100 and less for the easy one 40/100. Because there is a feedback as when you change the scores you are also changing the sums of concurrent scores, there are so many variables to adjust ~200K and the a priori values are already reasonable, I prefer to adjust doing small steps since this is an offline process and speed is irrelevant. The hits of each move don't change that much. At the beginning of the adjustment: Hits of move 1 = 0.382405 acc = 0.382405 Hits of move 2 = 0.113530 acc = 0.495935 Hits of move 3 = 0.067430 acc = 0.563365 Hits of move 4 = 0.048055 acc = 0.611420 Hits of move 5 = 0.036304 acc = 0.647725 Hits of move 6 = 0.028978 acc = 0.676703 Hits of move 7 = 0.023769 acc = 0.700472 Hits of move 8 = 0.019793 acc = 0.720264 Hits of move 9 = 0.016693 acc = 0.736957 Hits of move 10 = 0.014164 acc = 0.751121 At the end of the adjustment: (Additional steps don't improve further, some value may even decrease.) Hits of move 1 = 0.409278 acc = 0.409278 Hits of move 2 = 0.115598 acc = 0.524877 Hits of move 3 = 0.062659 acc = 0.587536 Hits of move 4 = 0.044014 acc = 0.631550 Hits of move 5 = 0.033681 acc = 0.665230 Hits of move 6 = 0.027696 acc = 0.692926 Hits of move 7 = 0.022885 acc = 0.715811 Hits of move 8 = 0.019029 acc = 0.734840 Hits of move 9 = 0.015758 acc = 0.750598 Hits of move 10 = 0.012886 acc = 0.763484 What I call the distribution is this: The gamma value of each legal move defines a probability distribution function over the legal moves. If we had no information (uniform random distribution) we would expect that with 20% of the legal moves we hint 20% of the times, etc. So for 0.1, 0.2 .. 0.9 of the legal moves we hit around 0.1, 0.2 .. 0.9. Now, what happens when we use our pdf over the legal moves? We can get 10%, 20% 30%, etc with very few move candidates. But, if the first move has say 0.17 and the 1+2 = 0.21 and I want to get 0.2 If the first is a match, count 1, if the second is a match count 3/4 = (0.2 - 0.17)/(0.21 - 0.17) if any other move is a match count 0. Do I really get 0.1, 0.2, .. 0.9, of course, with much less moves ? No. for a reason I don't understand, I get something like: Distribution fit expected 0.1 found 0.153164 Distribution fit expected 0.2 found 0.298602 Distribution fit expected 0.3 found 0.433074 Distribution fit expected 0.4 found 0.551575 Distribution fit expected 0.5 found 0.651135 Distribution fit expected 0.6 found 0.727419 Distribution fit expected 0.7 found 0.776876 Distribution fit expected 0.8 found 0.804008 Distribution fit expected 0.9 found 0.823292 So my distribution is distorted, when I try to get 30% of the guessing chance I get 43.3%, but when I try to get 90% I get 82.3%. I don't know why. Jacques. Łukasz Lew wrote: On Sat, Mar 29, 2008 at 3:47 PM, Jacques Basaldúa [EMAIL PROTECTED] wrote: Mark Boon wrote: I suppose there's no reason why it has to be assembler, you could just as well generate C-code. I don't think so. But I don't write that much asm as it may appear. I see what the compiler writes when I debug and write critical parts only. And automatically generated code. I don't see yet how you go from there to finding patterns. Depending on the mode, it computes either the hash or the mask. That mask has to be translated into urgency by a table search. (Btw. urgency is not just: times_played / (times_played + times_postponed) but that value is used as an a priori value for Bradley Terry models as Rémi introduced. My adjustment is not as advanced as what Rémi describes. I just give a weight to a competition based on the sum of the competing gamma values, and that gives me another point: SUM weights_of_played / SUM weights_of_played + weights_of_postponed Can you tell how you came with such an equation? Does it improves much? Thanks Lukasz And I advance a step (like 1/4 of the distance) in that direction and use the new point as the current value. Iterating this way improves the wins of the best move but distorts the distribution (I extract lots of statistics at each step) so I stop rather early.) The macro for searching in an ordered list
Re: [computer-go] State of the art of pattern matching
Mark Boon wrote: There are 16 4-distance points, so if you spill ino that by one point you get 315 or a little over 14 million patterns. Multiplied by 3 for every don't-care point within less than 4 distance. Ouch. True, but the number of patterns is learned automatically. When I first learn the 55K+ games, there are so many patterns that I can only create a pattern file of less than 2000 games. I create 32 such files an call importance the number of files in which each pattern is found. (a value from 1 to 32). The number of patterns are: # of imp = 32 97132 (97132) # of imp = 31 26493 (123625) # of imp = 30 21460 (145085) # of imp = 29 19335 (164420) # of imp = 28 18415 (182835) # of imp = 27 18703 (201538) # of imp = 26 18619 (220157) # of imp = 25 19345 (239502) # of imp = 24 20390 (259892) # of imp = 23 21611 (281503) # of imp = 22 22959 (304462) # of imp = 21 24675 (329137) # of imp = 20 26808 (355945) # of imp = 19 29081 (385026) # of imp = 18 31938 (416964) # of imp = 17 35319 (452283) # of imp = 16 39188 (491471) # of imp = 15 43899 (535370) # of imp = 14 50391 (585761) # of imp = 13 57259 (643020) # of imp = 12 67062 (710082) # of imp = 11 79013 (789095) # of imp = 10 95292 (884387) # of imp = 9 117109 (1001496) # of imp = 8 147810 (1149306) Depending on the threshold value used (and also the number of times the pattern is seen) I can create databases from about 100K patterns to 1M patterns, more than that means including patterns that are too seldom, their urgency information won't be very accurate either due to the small sample size. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
Mark Boon wrote: I suppose there's no reason why it has to be assembler, you could just as well generate C-code. I don't think so. But I don't write that much asm as it may appear. I see what the compiler writes when I debug and write critical parts only. And automatically generated code. I don't see yet how you go from there to finding patterns. Depending on the mode, it computes either the hash or the mask. That mask has to be translated into urgency by a table search. (Btw. urgency is not just: times_played / (times_played + times_postponed) but that value is used as an a priori value for Bradley Terry models as Rémi introduced. My adjustment is not as advanced as what Rémi describes. I just give a weight to a competition based on the sum of the competing gamma values, and that gives me another point: SUM weights_of_played / SUM weights_of_played + weights_of_postponed And I advance a step (like 1/4 of the distance) in that direction and use the new point as the current value. Iterating this way improves the wins of the best move but distorts the distribution (I extract lots of statistics at each step) so I stop rather early.) The macro for searching in an ordered list is an efficient implementation of the canonical method. Copy/paste from Numerical Recipes in C ISBN 0-521-43 108-5 (c) Cambridge University Press 1988-1992 void locate(float xx[], unsigned long n, float x, unsigned long *j) { unsigned long ju,jm,jl; int ascnd; jl=0; //Initialize lower ju=n+1; //and upper limits. ascnd=(xx[n] = xx[1]); while (ju-jl 1) { // If we are not yet done, jm=(ju+jl) 1; //compute a midpoint, if (x = xx[jm] == ascnd) jl=jm; // and replace either the lower limit else ju=jm; // or the upper limit, as appropriate. } // Repeat until the test condition is satisfied. if (x == xx[1]) *j=1; // Then set the output else if(x == xx[n]) *j=n-1; else *j=jl; } // and return. /Copy/paste Improvement 1: Instead of if/else, use conditional moves. Improvement 2. Since when the value is not found, the while loop has a fixed number of iterations for a fixed table size, unroll the loop as a sequence of iterations. As mentioned, an iteration has only 8 instructions. Improvement 3: When the value is found, break. (That wouldn't come for free in C it would require a additional if (x = xx[jm] ) ) moveax, ebx addeax, ecx shreax, 1 andal, 0fch ;; Align to a valid pointer cmpedx, [eax] jznameout cmovc ecx, eax;; This is true if [eax] value cmovnc ebx, eax;; This is true if the previous is false Here ecx is a pointer to xx[jl], ebx is a pointer to xx[ju], edx is x and eax is a pointer to xx[jm]. I assume you allow some of the points to be undefined (also called 'don't care points') but I don't see how. And if you allow undefined points, why would you need masks of smaller manhatten distances? I don't use don't care. I mask code in 2 bits: void, own, opponent, out_of_board. This produces bigger database size, because the only way to introduce don't care is to repeat the pattern. Since my patterns are learned automatically and database size is not a problem at all, I didn't see the need of don't care. The bigger patterns have the disadvantage that around move 150 2/3 of the legal moves have unknown patterns. The smaller distances improve this. I don't know yet if that is required, because patterns are mainly intended to break the ice, when complex shapes emerge, the moves suggested by the search may be much better candidates. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
Mark Boon wrote: Sorry, without a bit more explanation, the assembler code is very hard to understand. What exactly does it do? The first source code was just an example to see what kind of code is generated. The second is useful, if you understand asm you should understand it. The board has 4 modes, as far as patterns are concerned. So the following applies for each mode and for each possible mapping scheme. When 40 neighbors are used, (i.e. Manhattan distance 4) there are 81 possible situations (all the cells of a 9x9 board are different as far as board limits are concerned). On bigger boards, each cell maps one of the 81 possible 9x9 cells. The board system cannot play on less than 9x9. And for each of these 4x(maximum)81 (some board modes have smaller distance) the generator writes 2 functions: one for creating the mask/hash from scratch and an other to update all masks/hashes in the neighborhood of a new stone. Does it relate to a pattern? Yes the complete pattern is: +---+ | 4 | +---+---+---+ | 4 | 3 | 4 | +---+---+---+---+---+ | 4 | 3 | 2 | 3 | 4 | +---+---+---+---+---+---+---+ | 4 | 3 | 2 | 1 | 2 | 3 | 4 | +---+---+---+---+---+---+---+---+---+ | 4 | 3 | 2 | 1 | · | 1 | 2 | 3 | 4 | +---+---+---+---+---+---+---+---+---+ | 4 | 3 | 2 | 1 | 2 | 3 | 4 | +---+---+---+---+---+---+---+ | 4 | 3 | 2 | 3 | 4 | +---+---+---+---+---+ | 4 | 3 | 4 | +---+---+---+ | 4 | +---+ Justification of this shape: 1. It includes all standard nobi, iken tobi, niken tobi, kosumi, keima ogeima relations (+ double iken tobi + double kosumi) 2. It detects if a pattern is at the 4-th line or the 4x4 corner (and below obviously). Less than that is too small. The 4-th line is too different from the center. 3. It is a nested structure, {dist12, dist12 + dist3} are both usable. 4. It has reasonable size for the information it contains. 5. The bit arrangement is optimized for 90 deg rotation. Additionally, I keep urgency information for: normal, the pattern shows up for the first time and urgency in a ko. Did you write a paper or post explaining this in more detail? Not yet. Do I understand correctly that you generate this code automatically? Yes. It would be a nightmare to write about 70K lines by hand and debugging would be hard as well. Although what the functions do is simple enough to create a test that verifies 100% of the cases. You are talking about updating 40 hashes. Does it mean your patterns have fixed size? Yes. 3 sizes: Manhattan distance 2, 3 and 4 In the 500 nanoseconds, how many patterns do you compare? That was updating (max) 40 hashes in the neighborhood of a newly placed stone. The precise number of hashes depends on the board coordinate and the surrounding stones although that is achieved without a single conditional jump. (It is a very conservative estimation for approx 140 instructions in a jump free sequence. The typical case is probably more like half of that.) But, as mentioned, it does not include neither the board logic nor the search that translates hash - urgency. How about rotations and color inversions? In the slowest mode the pattern is rotated using macros like this one (that rotates a 40 neighbor pattern) asm mov edx, eax// @jm mov eax, [edx + 8] // jm.mask4 rol eax, 8 mov [edx + 8], eax // jm.mask4 mov eax, [edx + 4] // jm.mask3 shl eax, 6 mov ecx, eax and eax, 0ffh rol ecx, 8 or al, cl mov [edx + 4], eax // jm.mask3 mov eax, [edx] // jm.msk12 mov ecx, eax shl eax, 4 rol cl, 2 mov al, cl mov ecx, eax shr ecx, 16 and eax, 0ffF0FFh and ecx, F00h or eax, ecx mov [edx], eax // jm.msk12 end and converted to canonical. Color inversion is automatic because the pattern is own/opponent instead of black/white. In the fastest mode, the hash table has x8 size and includes the hashes of the rotated patterns. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching
terry mcintyre wrote: It is possible to get some remarkably high correlation between the moves played by pros and a predictor - yet still not have a good program. Why? We have a random variable, the place at which a player plays, and some variables that we can compute. The distribution of the random variable, depends on this variables. Our variables are shape urgency and life. Of course, I agree that it would be great to include life in our statistical model. It would be a much better model. The problem is we can compute shape in few clockcycles but we cannot compute life/death. (The revised Benson methods are of no use in real games because they detect life/death when it way too late.) All the pattern logic is not intended to determine what move has to be played, but only to select candidates for later methods. Also, it is not about what a player did once, but what is statistically sound in over 10 M positions. We ignored life/death when learning and we ignore it when we just suggest the best moves in terms of shape. That is fair, but, of course, the interaction between shape an life would change things for better. UCT methods are (among other reasons) strong in 9x9 because a random move (not in the first 2 lines in the beginning) is a reasonable move, and then the stochastic parts of the search finds good candidates (RAVE and similar). But in real go, there are 361 legal moves for move 1! And CrazyStone (as far as I know still the strongest 19x19 program) is still 2 kyu. That is the state of computer go in 2008, not the remark made by a pro about how hard it was to beat mogo by 9 stones. Most people in this list seem to be against human learned shape, but the truth is that we don't know if it is useful or not. That depends on the price we pay for urgency. In terms of RAM it is a couple of tenths Mb, that's nothing today, it was a lot years ago. Some people assume that you can predict what airplane society would be without building an airplane. Just move people in a bus, the airplane is the same only faster. That's not how things work. Unfortunately, you have to build an airplane to see what it can or cannot do. Some call it overengineering, but if it is not fast, then I agree it will be useless almost for sure. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] State of the art of pattern matching (Oops)
Santiago wrote: ... Oops, wrong name ... (Santiago is my official name, because I was born in a dictatorship that did not allow foreign names. After that, I was too lazy to change it. Jacques, like my French grandfather, is my real name.) Jacques. ___ 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 ?])
Petr Baudis wrote: MoGo can indeed play out some rather spectacular ko fights; unfortunately, I couldn't find any quickly, so here is at least an example of a shorter one. I see you made the following comment in that game record, which seems relevant to recent discussions here. | mogo excels at reducing clear winning positions to close games they | lose because of botched up tsumego Is it mogo botching up the tsumego or its opponents? Do you have any example game records for this? You won't find that in computer vs computer games, because tricking the strong programs requires some go skill and it only works if you wait long enough before you solve the position. But if you search KGS (LeelaBot, CrazyStone, CzechBot) for even games where the bot lost against a kyu players you will find many. All go more or less like that: A 4-6 kyu human is behind by 10-15 points in the midgame (at that stage the probability of winning is correlated with territory, so the MC bot is building fine.) He creates a 12-16 point worth nakade trick in a corner and does not solve it.The bot is happy, it thinks a bulk five is alive or something like that. Perhaps the human sacrificed another 15 points somewhere to create the trick so he should be dead lost. But, he only has to play on, reduce, etc. As the endgame approaches, the MC bot allows the reduction only until the territorial balance would change the winner. The player is happy, he turned a 25 points loss into a 1.5 point loss (assumed by the program) and has a 12 point surprise. At the end, when the whole board is decided, the player kills the bot's group and the bot turns a sure win into a sure loss and resigns. Because the trick can only be played by similar strength players (much weaker players can't build something like that, much stronger don't need it) it affects the rating of the bots. I guess CrazyStone could be near KGS 1dan with that solved. It is 2k now. But, of course, the solution may not come at the price of making the program weaker. That is the difficult part. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Way MC plays
Don Dailey wrote: I personally have serious doubts about knowledge extraction from human games, but I hope you have success.I think you can get more from computer games of strong players even though the level is weaker. Here is why I say that: 1. A strong computer still plays a lot of good moves - so the delta between human and computer games is not as high as you think. 2. A certain consistency in computer games that humans don't possess. 3. You have access to the internals, such as a score that quantifies moves. My idea combines offline knowledge with MC methods. So there is a lot of online computer generated knowledge. I don't pretend to make a dumb savant program, just playing the only move it finds in a joseki database. But if the program considers the joseki stored in (state, action[i-1]) - action[i] records. It will immediately start searching a tree whose first move at all depths is the joseki sequence. If the joseki depends on a ladder, it will find that ladder much earlier and if it is not good it will hopefully play something else. At blitz time settings, playing the wrong joseki is bad but not terrible. That would be about the level of a human dan making a mistake in a blitz game, still better than current programs. In this context, human knowledge produces a priori values for UCT. (The exact formula of the MC tree search is not yet decided.) There is enough computer generated knowledge in the search. When the end of the game is still 200+ moves ahead, the search alone does not find enough difference between good and not so good moves. The knowledge, I think, makes sense to extract is: 1. (state, last move) - (next moves list) records (joseki or places to play when the last move is somewhere else.) 2. urgency of shapes 3. distribution of statistics (e.g. proportion of times tenuki is played at move n) that helps making playouts more humanlike while still fast. I finally abandoned full board Bradley-Terry scored random playouts. I draw a random number to decide if tenuki should be played, if true I invent a random move and use it as if it was the previous move. Else, I play a Bradley-Terry scored random move in the 40 neighbors of the last move. That is almost immediate in my hologram board system because I store the mask. On other implementations it may not be so good. About urgency of shapes: The urgency of a BT adjusted 40 neighbors shape hits 40% in a 10 M+ sample with about 160 K patterns. (Overlearning should not be very important given the lack of degrees of liberty.) It hits 66% with the first 5 moves. Hits of move 1 = 0.402048 acc = 0.402048 Hits of move 2 = 0.117102 acc = 0.519151 Hits of move 3 = 0.065450 acc = 0.584600 Hits of move 4 = 0.045592 acc = 0.630193 Hits of move 5 = 0.035190 acc = 0.665382 That sounds great news. But there is bad news of course. That doesn't go any further. To reach 80% it needs 14 moves Hits of move 14 = 0.006206 acc = 0.801095 And to reach 90% it needs 96 moves! Hits of move 96 = 0.001323 acc = 0.900994 Shape is a factor that explains, perhaps 2/3 of the moves (shape alone about 40%, but shape in the right place a little more than 66%). Not less and _not more_ than that. It is naive to think that the 12th move in terms of shape is better than the 50th. But, imagine there are 250 legal moves, the 248th is a really bad move. Can shape make a difference? I don't know. If its slow, surely not. If it is almost free in terms of performance as in my board system, I hope it does. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Way MC plays
Jonas Kahn wrote: I mean, if Crazy Stone played against himself from the position where Katsunari was thought to be ahead, would he win with its original color, or with Katsunari's ? That is a very big question. I hope it would win with Katsunari's stones *if* Katsunari was really ahead. I have been now working for some months in knowledge extracted from over 50K games played by pros and high dan players (both players), enough time, no handicap. I don't know for sure if that was not in vane yet, that's why I write I hope. I certainly don't have a high opinion on any of the strong program's fuseki. These programs are not strong for their fuseki, I think, they are strong for many reasons and their fuseki is not really as bad as it looks. But I guess there is a lot of margin for improvement there. After the success of MC based programs some people argue that computers should play intrinsically different from humans and that computer play is superior. I don't share that opinion. I think that all what humans have elaborated on fuseki makes a lot of sense, when you apply it, you improve a lot. I don't see a reason why that would not apply to computers. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[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/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
Dave Hillis wrote: I've noticed this in games on KGS; a lot of people lose games with generous time limits because they, rashly, try to keep up with my dumb but very fast bot and make blunders. What Don says about humans scaling applies to humans making an effort to use the time they have, but when we play on KGS after a hard work day, we (I guess a lot of people like myself, including my opponents and the players I watch) play for pleasure. We avoid too fast settings, because it introduces unnecessary pressure, and we hate too slow because it makes the game endless. We play _independently of the remaining time_. Most moves fast, and from time to time we ponder 10 to 20 seconds. That's why KGS time settings for humans have to be taken with a grain of salt. About Don's arguments on self testing: I would agree at 100% if it wasn't for the known limitations: Nakade, not filling own eyes, etc. Because the program is blind to them it is blind in both senses: it does not consider those moves when defending, but it does not consider them when attacking either. Your programs behave as if they were converging to perfect play in a game whose rules forbid those moves. But these moves are perfectly legal! At weak levels, there are more important things to care about, but as the level rises there is a point at which understanding or not understanding these situations makes the difference. A program that understood these situations, but had some other small weakness could have strong impact in the ratings. Perhaps, Mogo12 and Mogo16 would not be so different in their chances of beating that program as they are in beating each other. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study : show uncertainty ?
I don't think only uniformly random playouts will scale to perfection because what we need for playouts is not just a simple average of final scores but a maximum (in negmax sense) score. It should be the perfect evaluation function. In other words, as MC simulation is a way to get an average of a value, when applying it to optimization problems we need some way to focus the simulations to the _peak_ in a state space. It may be obvious when one consideres LD problems where the best move that leads to the maximum score (live) is only one and all other moves are bad. At such positions it's almost no sense to simulate all legal moves with same probability. So, IMHO, biasing simulations is not just a speed-up technique but is essentially important. I agree, but what I meant about uniformly random playouts is the following: What makes a move outstanding is being unpredictable. For a total novice, playing at the key point of a bulky five may look like a touch of genius, but when you learn a little, its an obvious move. The difference between a 5p and a 9p may be one or two moves nobody can predict (except a 9p). When we add knowledge we find the _ordinary_ good moves faster, we make weaker moves less probable, but that comes at a price, the price of making outstanding unpredictable moves less probable also. Perhaps that introduces a ceiling. I thought that was what you were also pointing. Of course, I don't claim uniformly random playouts are good, I just claim that they should (just as an infeasible theoretic argument) scale to perfection, of course that scaling doesn't have to be linear. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study : show uncertainty ?
Hideki Kato wrote: It's rather odd. I'm checking the log file and then I will check the source code to see if I have some artificial limits in there. Why odd? It all depends on the bias or policy of simulations. If there is a flaw in the policy, the score will converses to the score with some error, which will introduce some limit of scalability, isn't it? That is a very good point. Perhaps it is not the case with FatMan, but that may surely happen. In this study no program is playing with uniformly random playouts and perhaps only uniformly random playouts will scale to perfection. Of course, I can imagine that reaching the strength of Mogo_13 with uniformly random playouts can require a number of simulations that is not feasible. So I don't have any idea about how to improve the study, but this is a serious limitation that has to be considered: If you find some ceiling, the ceiling may be attributed to the playout policy, not to UCT. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 cgos ranking page
Olivier Teytaud wrote: the 19x19 CGOS ranking page is back (but might be still unstable) and Leela seemingly performs quite well. The crosstables will come back soon also. The crosstables are back, but the sgf archives ar not. I get: Forbidden You don't have permission to access /~teytaud/SGF/2008/01/19/12664.sgf on this server. Apache/2.2.3 (Debian) mod_python/3.2.10 Python/2.4.4 PHP/5.2.0-8+etch9 Server at persowww.lri.fr Port 80 When fixed, please keep last week's games for a while. I was looking for game 12338 (I am not sure if that number is correct) and don't know the day it was played either. Jacques ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Hi Michael Another cost is undo. Superko requires undo, unless you want store a hash value with each chain of stones. I am not sure exactly what undo costs, but lets say 5% to 10%. Well, every implementation is different. In its slowest mode, my board stores information about neighbor stones in each cell. It has a stack of boards and each board has a pointer to its parent. In that mode superko can be detected. There is also a faster mode for MC playouts that does not support superko. But it could also be possible to maintain a stack of previous hashes i.o. complete boards, that would not be very expensive. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Michael Wing wrote: In my program (which implements undo), the cost of for suicide detection is around 1%, which means it would lose 1.5 ELO points. In programs that somehow maintain lists of legal moves or even probability distribution functions over the legal moves, avoiding suicide is free. I fact, adding the suicide move to the list would cost. On the other hand detecting superko costs more like 6% or so, which costs 9 or more ELO. So a benefit of 1 ELO for doing superko right may not be worth the cost. I guess you mean a bullet proof test from the beginning of the game. I only test the last 7 moves (if enabled, it can also be disabled) and that does not cost much. The reasons why I use 7 moves are 2: * I have never found among strong players a need for repetition other that triple ko and double ko on a group with no eyes. (Both are 6 moves long.) My point is: If the program is so weak that it does silly repetitions, improve something else. If it is so strong that it has the same problems as strong humans, detect superko. * My hash system can use only half of the hash (32 bits) and detect the collision with probability 1. (Because of the properties of the keys, you need at least 8 keys for a combination of keys giving zero.) A reason I can figure for ignoring repetition in the playouts is: If the playouts are random, it won't happen much anyway. The probability of a repetition of 6 random moves is too small to care about. But in real play it is frequently a fight for the game. The player forced to avoid the repetition will resign if it is about the life of a big group. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Suicide question
Gian-Carlo Pascutto wrote: Multi-stone suicide is allowed, single stone not. I hadn't even considered suicide.(It would be a major change for me, as neither my Gui nor my board system allow such moves.) The question is Why do you do it? a. Just in case you wanted the entire program to support suicide go or b. Because that has some advantage as a random playout. If it was b, can anyone explain why suicide is a better evaluation for a normal (non suicide) game. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is CGOS sending TIME_LEFT?
Hi Don I noticed that your list is upper-case. This might be the problem. I don't remember if GTP is case sensitive or not, but I'm pretty sure cgos requires lower case in these commands. Thank you. That was the problem. It was uppercase. To make it case insensitive, I convert all input to uppercase when I preprocess. So my names are declared uppercase. A stupid example of trying to amend something and actually breaking it. It works fine now. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to get more participation in 19x19 CGOS?
Don Dailey wrote: My suggest to Olivier is to compromise and set time control 20 minutes per side and give 1 second gift. That's good for me. Until now, I have been running tests and gnugo clones just to support the server, but I will start serious work soon. I have some time for computer go at last! I cannot use the 9x9 server, because my approach is very knowledge oriented. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgos from windows
I think you are right about the tclkit exe. I used the one that the instruction page linked, which does throw up a GUI if you run it with no args. I wonder if it even works. It appears to be a way to cripple the server. It does work. I have played over 600 games with it. It does not write any log files. If your gtp interface can do it, that's not a major problem. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is CGOS sending TIME_LEFT?
Hi Don The client does not sent time_left unless time_settings is also implemented.So your engine must also implement time_settings which is needed to inform your program of the level it will be playing at. I do implement time_settings. The server only sends a list_commands at the beginning and sends no time_settings either. What you can see in the logs is all I get, except the first list_commands. That is called only once, when the tcl interpreter loads the gtp end. I do not implement any KGS specific extensions, no undo, no handicap, no debugging functions (the gui already has debugging utilities). Is any of that required? Jacques. This is my complete list of commands: list_commands = BLACK BOARDSIZE CAPTURES CLEAR_BOARD ECHO ESTIMATE_SCORE FINAL_SCORE FINAL_STATUS_LIST GENMOVE GENMOVE_BLACK GENMOVE_WHITE GET_KOMI KNOWN_COMMAND KOMI LIST_COMMANDS NAME PLAY PROTOCOL_VERSION QUERY_BOARDSIZE QUIT TIME_LEFT TIME_SETTINGS VERSION WHITE ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Is CGOS sending TIME_LEFT?
Hi.. My gtp program does not receive any time_left commands. I have checked that the command is listed without mistakes in list_commands. I even tried CGOS 9x9 and I get the same sequence. Jacques. -- This is a 19x19 game start (after the first list_commands) Ignore the lines containing GoKnot, that is the communication between the gtp end and the gui. 42.842 |- server - boardsize 19\cr\lf 43.152 # - GoKnot8 [13 00 00 00 00 00 02 00] 43.242 # GoKnot -- 4 [ff 00 00 00] 43.242 |- gkGTP -- = 43.242 |- gkGTP -- \cr\lf\cr\lf 43.312 |- server - clear_board\cr\lf 43.332 # - GoKnot8 [13 00 00 00 00 00 02 00] 43.443 # GoKnot -- 4 [ff 00 00 00] 43.443 |- gkGTP -- = 43.443 |- gkGTP -- \cr\lf\cr\lf 43.533 |- server - komi 7.5\cr\lf 43.563 # - GoKnot8 [00 00 f0 40 00 00 03 00] 43.623 # GoKnot -- 4 [ff 00 00 00] 43.623 |- gkGTP -- = 43.623 |- gkGTP -- \cr\lf\cr\lf 45.836 |- server - genmove b\cr\lf 45.896 # - GoKnot8 [ff ff ff ff 00 00 0c 00] 45.976 # GoKnot -- 4 [ff ff 00 00] 45.976 # - GoKnot8 [03 00 00 00 00 00 0e 00] 46.036 # GoKnot -- 4 [ff ff 00 00] 46.086 # - GoKnot8 [03 00 00 00 00 00 0e 00] 46.126 # GoKnot -- 7 [ff 00 03 00 72 31 36] 46.126 |- gkGTP -- = 46.126 |- gkGTP -- r16\cr\lf\cr\lf 46.968 |- server - play w D17\cr\lf 47.018 # - GoKnot8 [00 00 03 10 00 00 06 00] 47.038 # GoKnot -- 4 [ff 00 00 00] 47.038 |- gkGTP -- = 47.038 |- gkGTP -- \cr\lf\cr\lf 47.228 |- server - genmove b\cr\lf 47.338 # - GoKnot8 [ff ff ff ff 00 00 0c 00] 47.468 # GoKnot -- 4 [ff ff 00 00] 47.468 # - GoKnot8 [03 00 00 00 00 00 0e 00] 47.538 # GoKnot -- 4 [ff ff 00 00] 47.589 # - GoKnot8 [03 00 00 00 00 00 0e 00] 47.629 # GoKnot -- 6 [ff 00 02 00 64 34] 47.629 |- gkGTP -- = 47.629 |- gkGTP -- d4\cr\lf\cr\lf 48.620 |- server - play w Q3\cr\lf 48.660 # - GoKnot8 [00 00 0f 02 00 00 06 00] 48.740 # GoKnot -- 4 [ff 00 00 00] 48.740 |- gkGTP -- = 48.740 |- gkGTP -- \cr\lf\cr\lf -- This is a 9x9 game start (after the first list_commands) 14.331 |- server - boardsize 9\cr\lf 14.371 # - GoKnot8 [09 00 00 00 00 00 02 00] 14.471 # GoKnot -- 4 [ff 00 00 00] 14.471 |- gkGTP -- = 14.471 |- gkGTP -- \cr\lf\cr\lf 14.551 |- server - clear_board\cr\lf 14.581 # - GoKnot8 [09 00 00 00 00 00 02 00] 14.671 # GoKnot -- 4 [ff 00 00 00] 14.671 |- gkGTP -- = 14.671 |- gkGTP -- \cr\lf\cr\lf 14.751 |- server - komi 7.5\cr\lf 14.771 # - GoKnot8 [00 00 f0 40 00 00 03 00] 14.852 # GoKnot -- 4 [ff 00 00 00] 14.852 |- gkGTP -- = 14.852 |- gkGTP -- \cr\lf\cr\lf 20.640 |- server - genmove b\cr\lf 20.680 # - GoKnot8 [ff ff ff ff 00 00 0c 00] 20.780 # GoKnot -- 4 [ff ff 00 00] 20.780 # - GoKnot8 [03 00 00 00 00 00 0e 00] 20.870 # GoKnot -- 4 [ff ff 00 00] 20.920 # - GoKnot8 [03 00 00 00 00 00 0e 00] 20.960 # GoKnot -- 6 [ff 00 02 00 66 36] 20.960 |- gkGTP -- = 20.960 |- gkGTP -- f6\cr\lf\cr\lf 22.843 |- server - play w C6\cr\lf 22.883 # - GoKnot8 [00 00 02 05 00 00 06 00] 22.973 # GoKnot -- 4 [ff 00 00 00] 22.973 |- gkGTP -- = 22.973 |- gkGTP -- \cr\lf\cr\lf 23.194 |- server - genmove b\cr\lf 23.234 # - GoKnot8 [ff ff ff ff 00 00 0c 00] 23.264 # GoKnot -- 4 [ff ff 00 00] 23.264 # - GoKnot8 [03 00 00 00 00 00 0e 00] 23.384 # GoKnot -- 4 [ff ff 00 00] 23.524 # - GoKnot8 [03 00 00 00 00 00 0e 00] 24.165 # GoKnot -- 4 [ff ff 00 00] 24.215 # - GoKnot8 [03 00 00 00 00 00 0e 00] 24.275 # GoKnot -- 4 [ff ff 00 00] 24.325 # - GoKnot8 [03 00 00 00 00 00 0e 00] 24.365 # GoKnot -- 6 [ff 00 02 00 66 34] 24.365 |- gkGTP -- = 24.365 |- gkGTP -- f4\cr\lf\cr\lf 36.563 |- server - play w E5\cr\lf 36.583 # - GoKnot8 [00 00 04 04 00 00 06 00] 36.693 # GoKnot -- 4 [ff 00 00 00] 36.693 |- gkGTP -- = 36.693 |- gkGTP -- \cr\lf\cr\lf ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Please have your bot resign, for your own good
The problem is avoiding that an inferior program wins a lost position on time extending the number of moves. If you could choose, what side would you prefer to be? As a human, there is no doubt. But as a program it is even better: the strongest program. Because computers can play faster than humans. It is so much easier to make a strong program manage its time better than to make a weak and fast program stronger. Therefore, I propose a silly idea: Introduce a bot (I suggest the name mosquito) *intentionally* that tries to exploit time weakness. Just an ultra blitz player that plays some good looking move at 1 ply without search and never resigns. If your program loses games against mosquito you have to improve your time management. If there is a mosquito (annoying but otherwise harmless insect) always present in the system, serious programs will have extra motivation to care about time management. Of course, its only a half serious proposal. And the problem with the Philippines won't be solved, perhaps it just a mater of increasing the 1/4 sec extra time to 1/3 or something like that. Of course that is not fair, because it is an advantage for those with better connections, but that cannot be avoided. Working with 16 cores is a much bigger advantage and is not avoided either. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] misconception about game(?)
Forrest Curo wrote (quoting David Fotland): for example, go books make a big deal about where to extend along the side, or when to play in one corner or another, but the difference between these various moves is usually only a few points. The difference between similar-appearing various moves may well be one of efficiency--and that translates into sente or control of the game. A typical technique of human analysis is to consider the shape of a position: If the same moves had been made in a different order, would all of them be necessary or even justifiable? Good shape normally gives you a stable, highly defensible position with the minimal number of moves and hence the best chance of keeping-or-recovering sente. I think David means in the fuseki. And that sounds right to me, because fuseki moves can be used for so many different purposes that they are seldom really bad. When a move is bad according to tewari analysis it sometimes happens that ten moves later another move makes the bad move very good. This is related with the remarks 9 dan Tei Meikou commented on final Katsunari vs. Crazy Stone (see Hiroshi Yamashita's recent post). He states White first 3 moves are 10kyu player's move. According to orthodox fuseki theory we must agree. MC programs show no respect for the rule: First the corners, then the sides and only then, the center. But the truth is they play the strongest computer go nowadays. Many human players also start at tengen at high dan level and win their games. Really bad fuseki moves do exist. There are: too low, too concentrated, creating weak groups for no reason at all, reinforcing the opponent. (This list probably represents a high percentage of really bad fuseki moves.) But MC programs don't play any of these really bad moves. The other moves are not really bad and they serve some purposes that may not be as obvious as: First the corners, then the sides and only then, the center. but they are justifiable and later, they may even become good moves. Of course, I would welcome the opinion of stronger players on this. But the impression I have after replaying Katsunari vs. Crazy Stone is: Neither Crazy Stone weak moves are so weak, nor its pro moves are a surprise. I guess a pro would have found a *moment* to play that sequence that does not turn it into a compensation for ignoring a reduction threat at D11, but makes both objectives compatible: defending against D11 and killing at bottom right. I know Crazy Stone doesn't care about winning big, but I like it. ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Don Dailey wrote: You can use Zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. Yes. Don is right. Of course that is not part of the real program, but of a program that searches the book. In my case (19x19 only) I play a maximum of 20 moves (10 per player) from the book and then switch to the real program. I never shared the naif idea that some openings (played by high dan) are better than others and that finding a correlation between a given move and the result of the game was meaningful. I consider all popular openings equally balanced and playable. Finding a move in the book just saves you the time of 4-5 moves (10 if you are really lucky), gives you a straightforward way to randomize the opening (drawing between all moves in the book uniformly) and makes the board contain some information when the real thing starts. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Ben Lambrechts wrote: Now I got the following problem: how to rotate/mirror the board for a unique representation. Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Compute the the min(8 Zobrist hashes for all mirror/rot combinations) (x, y), (inv Y, x), (inv X, inv Y), (y, inv X), (inv X, y), (inv Y, inv X), (x, inv Y), (y, x). Call the smallest of the 8 hashes the canonical hash. Make a database of canonical hashes. Since Zobrist hashes can be updated incrementally, checking over the legal moves is just xoring the 8 hashes of the each legal move (with a given mirror/rot) to the hashes of the current position in that same mirror/rot. You store 8 hashes for the current position (=without the move) and compute the 8 hashes of the next position. The smallest of these is the canonical of the next position. This is repeated for each legal move. Its simple, but perhaps my explanation makes it sound more complicated than it is ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A thought about Bot-server communications
Nick Wedd wrote: In one of the British Championship Match games, a bit over ten years ago, Zhang Shutai made an illegal ko move against Matthew Macfadyen, and immediately conceded that he had lost the game. Is the game record available? I am interested because I have only found 2 situations in real games: a. Triple ko b. Double ko when the group sharing the kos has nothing better than life in seki. Both have cycles smaller than 8 ply and my software doesn't check longer cycles. I guess any human player would recognize these situations. So if a strong player didn't it must be something more complicated. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Microsoft Research Lectures: Akihiro Kishimoto
Thank you, Harri. It sounds promising. I will have a look at that. Jacques. I coded algorithm based for that representation, it really looks another awesome thing worth of investigating. Planning to use that for at least small board search investigations as it has quite much power. That is included lates version pf http://sourceforge.net/projects/narugo I am happy to hear some feedback if that TsumeGoMoveGenerator has some bugs by the way. It is first version of that, so propably it has some bugs left. But first impression about algorithm wou, impressed as it answered easy tsumego problem immediately, it has much potential to extend other kind of problems, not only life-and dead problems. t. hArri ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Microsoft Research Lectures: Akihiro Kishimoto
David Stern wrote: Akihiro's talk has finally been put online at: http://content.digitalwell.washington.edu/msr/external_release_talks_12_05_2005/15004/lecture.htm Good lecture. Is there a link to a binary (or source code) somewhere ? I can't find any TsumeGo Explorer website. At least, not in English. Jacques. * * ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] ELO Ratings of move pattern
Lars wrote: Anyone of you have similar or other experiences with the algorithm? I use at runtime the same Bradley-Terry formulas Remí introduces in his paper. That is a huge advance compared to naif urgency scores because it gives a measure of how hard it was to win for a move candidate. But I use a much simpler offline learning algorithm: Compute the naif score just as standard: sc[0] = (times played)/(times played + times postponed) Use this as an a priori value of the score. Then, iterating through all the games many times, create a compensation weight CW rewarding scores winning positions with high total of concurrent scores and diminishing those won too easily. Since the efficiency of the offline part of the program is not an issue, I make these in small steps iterating many times until they do almost nothing. Each time, I compare observed versus expected number of right guesses to see if it improves or not. sc[i] = CW*sc[i - 1] // * is elem by elem mul of a vector I guess it gets to more or less the same. Sure Remí's solution is more efficient and elegant. 2 more issues I am concerned about patterns: MIAI URGENCY: When two (or maybe more) moves are extremely urgent, but it is not important which of the two because they are equivalent. In this case the high urgency is masked by the fact that it is divided between two moves. IMPLICITLY CHECKED URGENCY: When an urgent pattern was already on the board and was not played its score is overestimated. Imagine threatening a bamboo joint, preserving the connection may be a huge point when it saves a big group without eyespace. But it may also be worth nothing when both groups are dead. When it first appears, there is a high probability that it is big and, therefore, its urgency should be high. But, if it wasn't played, then it is probably not big. The next times it has to be considered much less urgent than the first time. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Redirecting i/o in the Windows version of Mogo (Was in Re: Update of MoGo binary ..)
Edward de Grijs wrote: Can someone help me with this problem, for which I cannot find a solution: I am trying to run MoGo in an automatic way, using the cygwin toolkit. I guess you are trying to do this in Windows and using the Windows binary. If this is the case, you don't need any library. I did it and it works. Now, Linux supporters will enjoy this ;-), even as a Windows programmer I must admit that redirecting console i/o is one of the weirdest Windows features. The official Win32 reference example explaining how to do this has 245 lines of code!! (although many are remarks) If you have the Win32 reference in .hlp format search an article titled Creating a Child Process with Redirected Input and Output. If you don't, it must be public at MSDN. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: The global search myth
Dave Dyer wrote: In cases where the good moves are the obvious ones, you've found them anyway. Ok. Here I agree. In other cases, you prune them away. You are not really pruning, just postponing. Of course you may overlook moves of genius, who doesn't? But if your probabilities are correct you may be emulating what a human does. You DO get wrong answers much faster this way though. Why? I don't see why. I see this order as the most human like way of searching. As any incomplete search, it can blunder, but why more than any other incomplete search? Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New engine? From a Chess programmer perspective.
Christoph Birk wrote: I don't think 2200 ELO on the 9x9 CGOS is equivalent to 'high dan-level' play. Neither do I. In fact the whole kyu/dan rating system applies only to 19x19. 9x9 is not deep enough to have have so many ranks. On a 9x9 board an average amateur beats a pro with handicap 3. That amateur would be crushed by the pro with handicap 9 in 19x19. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
Raymond Wold wrote: Do you have anything to back this up? I was under the impression that most decent assembly programmers agreed that they can't compete with the best C compilers. Absolutely NOT. Only the typical, perhaps 99.9% of the programs, made of: transfers, conditionals, integer arithmetic and _non-parallelizable_ floating point arithmetic are efficient when compiled in C (or Pascal which compiles to the same binary and creates the same compatible .obj as C). In these cases, writing in assembly is both less efficient (because the compiler finds optimizations the programmer won't find) and harder to maintain. BUT Programs with bitmaps, bit manipulation, masks, etc. Which are really useful in go, are (sometimes x4) more efficient written in assembly. The same was the case when Chen Zhixing wrote Handtalk in assembly. The same happens in any cryptographic, binary image compression/decompression, application today and forever etc. Compilers optimize vulgar programs, because that is what most programs are. Please, understand vulgar as defined above, we all write lots of vulgar programs, it is not an insult. Programmers should view the code they are generating and _only_ that should tell them what is worth writing in assembly and what isn't. The best programming language is the language that lets you write assembly language hacks clean and easily using the high level symbols. It is fine to use cool feature languages on the base that your priorities are different and you don't care about the binary, but you shouldn't claim that you can have both coolfeatureness and efficiency, because that is simply not true. Of course, what is cool is very subjective debate: Some people find it cool to depend on runtimes that increase at mega/month rate, do what the API already does only much worse, gift the user with the gray rectangle experience even on a quad-core. After two seconds of gray rectangle they paint something that does not properly support clipboard operation, replaces the system's file dialogs for dialogs in which you have to manually type: *.sgf, *.SGF, *.Sgf, .. (to see all your .sgf files), that never remember last folders, etc. All this annoyance just because someone bought the platform independence fallacy from a company (Sun microsystems) that never cared a bit about compatibility. I am still waiting to meet the first person who answers affirmatively to the question: Have you ever paid for a program written in Java? Simple question, everybody I ever met answers no. Guess why. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] CGOS 19X19 is down
Hello I was waiting till someone restarts, but nobody seemed to notice. CGOS was hanging yesterday morning (European time) with 3 games 4849..4851 where no black engine placed any stone. If black restarted (one of the black bots was mine) it lost on time because the 30 minutes had been used. Black lost on time without even getting a gen_move command. For about 36 hours now, game 4851 is still waiting for black to start. Jacques. PD I don't know who is in charge of CGOS, Don, Olivier or Jason. If this is not the right place to post CGOS incidents, tell us where. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
Don Dailey wrote: My Go program doesn't use any libraries except the standard C libraries. I agree at 99.9% !! The only exception in my case is SFMT. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html SFMT is 100% clean C software, easy to compile, easy to use and free. A good RNG makes a huge difference. We all called his software buzzword compliant because he admitted that he wanted to try out several new technologies. Ha, ha. These guys exist in all latitudes. I've met a few ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Connecting a gtp engine to CGOS 19
Solved! It is working now. The problem was the tcl script does not pass all remaining parameters to the called application (gnugo in the example). To solve this, the command line should be delimited with a quote char. tcl cgos3.tcl testingTCL password E:\\GO\\PROGRAMS\\GnuGo\\gnugo37 --mode gtp --chinese-rules --capture-all-dead instead of: tcl cgos3.tcl testingTCL password E:\\GO\\PROGRAMS\\GnuGo\\gnugo37 --mode gtp --chinese-rules --capture-all-dead I repeat the corrected post: 1. Get TCL. There are many flavors with GUI, debugger etc. The simplest, when you just need to run a Tk application is something like: http://www.equi4.com/pub/tk/tclkit-win32.upx.exe This .exe is all you need, about 1M and without any annoyances, installation, registry etc. For simplicity: Rename tclkit-win32.upx.exe as tcl.exe 2. Get the .tcl client from CGOS. http://cgos.boardspace.net/public/cgos3.zip 3. Modify the .tcl script to use the 19x19 server # ... set server cgos.boardspace.net set server cgos.lri.fr # ... set port 6867 set port 6919 No other modification is necessary. 4. Create an account in CGOS. I remember having read that when you use one for the first time, any name and password are valid and then, you have to use the same password to continue using it. So, for testing purposes, I use the account: name: testingTCL pass: password 5. Using gnugo for the sake of simplicity (just for the test), gnugo37 --mode gtp --chinese-rules --capture-all-dead should be a valid setting to play on CGOS. Remember that you will loose lots of won games if your program does not capture all the opponent's dead stones. Chinese rules is mandatory as well. 6. Create a .bat file with: tcl cgos3.tcl testingTCL password E:\\GO\\PROGRAMS\\GnuGo\\gnugo37 --mode gtp --chinese-rules --capture-all-dead 7. Run the .bat file wait for the next round. Your program should be playing. 8. To supervise your program: Download cgosview.exe from http://cgos.boardspace.net/public/cgosview-windows.zip Call it with these args: cgosview.exe cgos.lri.fr 6919 Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
Don Dailey wrote: Of course that's better, but I'm talking about a quick and dirty solution. I may never implement handicap games since it's tricky with ELO ratings. This can also be done by the programmers. E.g. If CrazyStone is too strong, Rèmi can introduce a CrazyStoneH3 which passes 3 times at the beginning. But not at the first move, to avoid smart tricks. If CrazyStoneH3 is given white and plays: 2. whatever 4. pass 6. pass 8. pass. Black cannot pass and win the game because of komi. This way you are not forcing programs to accept handicap (some may suffer more than others). It is just a program who always gets white and does not play against other handicap programs. Just an idea. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] XML alternatives to SGF
Bob Myers wrote: Many of those complaining about XML don't seem to really know too much about it. That is exactly my point. I don't know and I don't want to know! SGF is fine. It has been stable for years because there is no problem at all. Should we find a problem, there is a straightforward solution: a new SGF version. At the end, either creating your own XML parser (by experience, the best option) or entering the nightmare of depending on someone else's library, bugs, updates, limitations, etc. costs A LOT OF TIME. For what? For nothing. Again, sgf works fine. Nothing would be as stupid as having go games split in 2 incompatible formats. Two formats for the same thing is just a tax on go development: Its not enough with one effort for making your program compatible you have to do it twice. Who wins anything with that? I can't guess. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] XML alternatives to SGF
Heikki Levanto wrote: Even if a new proposed standard would have many benefits, obvious to everyone (which I have not yet seen), I would stuill urge people to consider those benefits carefully, and to weigh them against the problems that arise from having two incompatible standards. I agree 100%. Unfortunately we (all of us, I guess) all have few time for go programming. The most crazy idea to invest that time in is yet another file format. Personally, I won't do anything against sgf. I just expect that the XML idea fails. If it doesn't, that may be a problem in a few years. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Update of MoGo binary release, and windows version available!
Thank you Sylvain! It works fine for me. A very good sparring strong and so different in style! You mean that with the .dll in WINDOWS\system32 that goes further? I thought that the .dll in the same directory as the .exe was enough. Copy/pasting from Microsoft's API reference: The function searches for the file in the following sequence: 1. The directory from which the application loaded. 2. The current directory. 3. Windows 95: The Windows system directory. Use the GetSystemDirectory function to get the path of this directory. Windows NT: The 32-bit Windows system directory. Use the GetSystemDirectory function to get the path of this directory. The name of this directory is SYSTEM32. 4. Windows NT: The 16-bit Windows system directory. There is no Win32 function that obtains the path of this directory, but it is searched. The name of this directory is SYSTEM. 5. The Windows directory. Use the GetWindowsDirectory function to get the path of this directory. 6. The directories that are listed in the PATH environment variable. The priority is only important if there is more than one version of the file. Placing the file that works ok in the same path as the application is good practice. This makes the program work fine without modifying the system anyhow. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Most common 3x3 patterns
Cenny Wenner wrote: Care to elaborate on what you mean by scores here and how they are similar to the 9x9 equivalence? I guess Dave is using Bradley Terry scores. This idea was introduced by Rémi Coulom in Computing Elo Ratings of Move Patterns in the Game of Go The paper is available on the web (finding link left to the reader ;-). This idea outperforms previous approaches. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] playing strength of programmers
I agree with all those who say it is important, but there is some precision to be made: As a player you are as strong as your weakest link because you are punished for your mistakes. As a programmer you are a strong as your strongest link. You know that mistakes are just mistakes, as long as you can identify them, your program won't do them. My advice is: Read about advanced strategical concepts (in books, not only sensei) and watch dan players until you understand what they do. Don't worry about your own level. It will increase anyway, but you will still be beaten by players who know less than you but are way more solid. Understanding dan level play is some orders of magnitude easier than playing dan level. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Why Poker-GMs don't win at poker.
Poker can be analyzed well by (even naif) Monte Carlo methods. How? Simulation! Whatever evaluation you need and don't know how to compute because it is too complex for easy formulas can be simulated. This applies to the probability of winning, but also on the betting decisions (call, raise, etc.) and the amount in the pots your own and your opponent's. Play it out randomly 10 times and see how many times you win/loose. Whatever estimator you get will be better than what a human can do just guessing. I call it naif because its the first idea, like basic MC. Then, knowing the problem better you can evolve to something like UCT that favors more promising lines, etc. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Go in hardware
Hi Chrilly: You have mentioned go in hardware twice recently and I have, knowing that you have experience in hardware development, some questions: 1. What should be implemented? In your Hydra cluster I have read you implemented mobility, and somewhere you proposed something like influence. Can you explain it? Here are questions for anyone how knows or has ideas: 2. My board system. I have Bradley Terry scores of patterns built of the neighbors of all empty cells that translate to the legal moves sorted by score. I can update the 40 neighbor masks without any conditional jumps in about 3 asm instructions per neighbor, say 2 ns at 3.4GHz. In hardware you could do in parallel what I do sequentially (the 40 neighbors). But few stones have 40 empty neighbors because they may be out of the board (I once explained how I do that) or not empty, so a guesstimate of the gain for doing that in hardware is x20 (i.e. x40). If your hardware technology runs at 3.4 GHz, that's great! But if it runs at 200 MHz it is even. Then, my software is multicore. I test it with 2 cores, but expect to run in on 256 cores machines in the future. Can the hardware support this? 3. My second problem. translating patterns to scores (database search). I call it a database, but it is a set of sorted 32 bit masks where I can find really fast without any conditional jumps using cmovc instructions. So it is very similar to the previous case. Hardware is better only if clock speed is high enough and it supports multiple cores. 4. My bottleneck: Sorting. Its not really a bottleneck because sorting few values is fast, but it is the slowest part of my m-search. (Sorting is not required for MC/UCT methods.) Is there hardware for sorting? In short: a) How fast can we expect hardware to be? b) Can you repeat the hardware kernel x times so that each thread own an independent kernel? c) Can you sort (in flash time) 19^2 integers? d) How many patterns could the hardware store? e) How much would it cost? Of course, implementing in software has a wider market and you should only implement something that proved to be valuable. I am not claiming that my board is, but it is an interesting subject. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Why Poker-GMs don't win at poker.
Chrilly Donninger wrote: I think poker is more difficult than Go and of course chess. Poker can be analyzed well by (even naif) Monte Carlo methods. Of course, the fact that you get a better estimate than any human could dream of, won't necessarily make you win. This common misconception can be found in many computer go papers. People who train patterns to predict moves tend to think the more they predict the better. Some even claim 60% prediction rates and higher. Of course, we all predict moves as a play when we watch pro games and feel good when our guess is right. Two reasons make it easy to have high prediction rate: a. forced moves b. local play is easier to analyze than the value of all possible tenukis. Usually, you don't do very wrong answering local and postponing other fights. My case: I have to give Bradley Terry scores to 1/3 M patterns: LoadJeitoLibRW_ByName() Importance of database loaded # of imp = 32 91986 (91986) # of imp = 31 25466 (117452) # of imp = 30 20263 (137715) # of imp = 29 18556 (156271) # of imp = 28 17592 (173863) # of imp = 27 17646 (191509) # of imp = 26 17722 (209231) # of imp = 25 18575 (227806) # of imp = 24 19283 (247089) # of imp = 23 20525 (267614) # of imp = 22 21695 (289309) # of imp = 21 23712 (313021) # of imp = 20 25434 (338455) Note: The importance of a pattern is the number of disjoint sets of games where the pattern is found if you divide the whole database in 32 disjoint sets. E.g. A pattern of importance 28 is a pattern found in 28 sets of about 1500 games but not found in 4 sets of the same size. I don't collect data on the number of games in which each pattern is found. Note: These are the real untricked patterns. Then, I generate a crunched version that behaves mostly like the big one. So I have 338455 patterns of importance 32 to 20 I could try to maximize the probability of a guess, but I don't! What I really am interested in is _a probability distribution over the legal moves_. I ask my HSB board to give me the _minimum number of moves_ that cover a 30%, 50%, 99% probability. (Note: This number is not an integer. Eg. If it is 3.17 - If the winning move is in the 3 first, you add 1, if it is the fourth move you add 0.17 and else you add 0.) The legal moves are sorted in descending score. For adjusting my Bradley Terry models I have a loss function and a very naif method that corrects in small steps. (The good thing of off-line learning is that you can implement junk because that does not go into the program. ;-) The program updates a pattern and finds its score in two digit nanosecond times ( 400 clock cycles) if it may have changed, and 0 if it may not.) My loss function evaluates (using a random sample from an independent test set) if: When I want 50% I really get 50% (and the same for other values, of course.) If I want 50%, getting 60% is as bad as getting 40%!! What I need is a reliable distribution not a thing that guesses many times. And also, that this distribution contains the maximum information (but that is another story). This explains why when you watch the European Poker Tour on TV and the journalist identifies half a dozen legends including previous year's world champ, US guest don't-know-what-champion Las Vegas, and all other celebrities, none of the legends wins except by a fluke just like anyone else. Statistics is not about winning the lottery, its about getting good estimators. And computer poker programs do better than humans but that does not make them win. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Intelligence
Hideki Kato wrote: Creativity here is, to generate a new method by combining methods the system already has, in order to solve a problem. That is creativity for the job of designing algorithms. Playing go, creativity is finding moves _that work_ that nobody would have thought of. I think there are two myths about creativity: 1. Creativity is always good. 2. Humans are more creative than computers. 1. Creativity has to do with exploring unexpected directions. When you are subject to restrictions and have some measurable goal, there is an optimal amount of creativity for a given problem. (Imagine creativity like a thermal energy in simulated Annealing.) Too few creativity restricts you to an local minimum from which you have not enough energy to escape. Too much creativity takes you outside the goal maximization paths. The most creative go player is the uniform random player, but that it uninteresting creativity the only interesting creativity is creativity that works. Vomiting on a canvas and pretending to be an artist for that is uninteresting creativity (aka stupidity). 2. For humans it is extremely difficult to simply create one hundred uniformly random digits. Either you bias or, trying to compensate the overall distribution, you fall into serial correlation. Computer creativity is way easier, faster, measurable and reliable than human creativity. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Slides for Villach-EC Lecture
The word in AI I don't feel conformable with is Artificial, not Intelligence. I use _Abstract_ Intelligence (also AI) as a replacement. Have you ever heard of artificial aerodynamics (applicable to planes but not to birds) or artificial thermodynamics (the same). I understand that AI is the science of thinking machines and that, of course, applies to biological ones. Aerodynamics was not developed by ornithologists and neither will the theory of thinking machines be developed by any frog-rippers. Electrical engineers laugh at a joke in which someone pretends to have found The Physical Location Of The Notepad (all capitalization is insufficient to reach the pompous statements frog-rippers use to make) in the floppy disk. After a conclusive experience placing electrodes on different parts of a computer, it has been proved that the floppy disk unit triggers each time the application Notepad is launched. Of course, the reason behind the floppy access is the last file opened was a:\readme.txt. All serious science is a part of Mathematics ( if not, Mathematics will absorb it ;-) ) and so is the science of thinking machines: AI. Jacques. PD. The only explanation I find to the need of the word artificial is the (for me totally unexplainable) respect educated Anglo-Saxons have for religion. This way, it looks compatible with religion, but of course it isn't. The soul of a thinking machine is an anti-scientific notion no matter what kind of thinking machine. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Why are different rule sets?
Jason House wrote: I run some really dumb bots online that play perfectly fine blitz games (10s/move) with Chinese rules and it still drives humans insane because the computer doesn't stop playing. People resign won games in endgame because they can't take it. There is some value in reducing the number of moves in a game. 10 seconds/moves is not really blitz. If the program plays stupid invasions (I don't know if its is the case of your program) that can be annoying if it goes up to 50 unnecessary moves or more. As a user, I like to count. I don't like computer resignation. It emulates human honor codes. For a human it is very humiliating to be forced to play a losing game for a long time, but computers have no honor, they should play _fast_ and without burning out ko threats just because there is nothing to lose. My favorite computer behavior as a user: gnugo with no resign at a fast level (max 2 sec/mov). Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT caveat (was in Explanation to MoGo paper wanted)
Brian Slesinsky wrote: And this would mean that a position where black is in trouble would look stronger than in a random playout (due to black playing well only for this kind of situation) which would make it harder to tell which positions are actually good. Or in general, an improvement in play that only works for some positions will tend to make those positions look good, and make it hard to tell which positions actually are good. That's what I mean. The defense favors one player (the one in danger) more than the other and these positions get a wrong evaluation. That is dangerous and, in general, will weaken the program. Maybe in a particular situation it is a good idea. Sometimes breaking the rules is a good idea. ;-) I like this example because it sounds very reasonable and it is not obvious that it is breaking the rules (the unbiasedness rule), but it is. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Explanation to MoGo paper wanted.
Hi, Don I can find arguments to disagree. I think what makes humans homo sapiens is reasoning, not the ability to compute numerical simulations. As a human (I am one) I feel disappointed when the explanation I get for a best move is after x millions of simulated matches it proved to be the best. If it is well done, I believe it, but I don't like it because I cannot verify it by myself. Such a program will not improve my play because it will not tell me what I do wrong or how I can improve. As a user, I would rather pay for a program that makes me improve my play than for the best program that only tells me moves are simulation gospel. On the other hand, I can imagine an old go sensei (I have never met one, I imagine him from Kawabata's novel) like a virtuous piano player, imagine Arturo Benedetti Michelangeli or Tete Montoliú (I met him). These men had their brains and even their bodies transformed by a whole life of study and improvement towards perfection. What they finally gained was _gesture_. The way they put their hands on a piano keyboard or the way they read a go board was the result of a lifetime of training. What you call a dirty hack, patterns deeply implemented in their brains. Gesture is what I expect from my programs. And a lifetime of training may be 100 hours of computing. I call it jeito. It sounds Japanese, that is appropriate for go. Here, in the Canary Islands, the word is used in the sense of a skillful trick and most people believe it is a Canarian word. The truth is it is a Portuguese word and it means gesture. Of course, this is just chatting. At the end the strongest program decides who is right and who is wrong. ;-) Jacques. Don Dailey wrote: What really irks me is that in most peoples minds, that is considered the elegant approach - hard coding tons of fixed knowledge into the program. Nothing could be farther from the truth, this is a dirty shortcut, a hack. There is nothing elegant whatsoever about having a huge database of patterns that tell the program what and what not to do - then calling it smart. The reason UCT/MC is elegant is that it has a built in mechanism to discover truth for itself. It may not be the best way and perhaps there is something better but at least it is a try.In a lot of ways it mimics the human thinking process. The MC play-outs is a crude substitute for human experience (the experience is gained on the fly) and UCT tree is a substitute for reasoning about characteristics of the position, what does and doesn't work. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT caveat (was in Explanation to MoGo paper wanted)
Brian Slesinsky wrote : When you favor defense (or attack) you may think: This is unbiased since some times it favors black and other times it favors white But the fact is when black is in danger at the root of the tree, it is in danger in most of the tree, therefore the trick gets the evaluation wrong. Well, this is subtle enough that I don't understand it. What are two positions that it would compare incorrectly? - Brian It is not two positions. What I say is the same applies _obviously_ if it is the other color who is in danger. I will try to explain it better: E.g. The game is in a position where black is in danger. That position is the root node. All stones in the root node are inherited in any node below, except when they are captured. Your trick pretends to favor defense. Therefore, black has higher probabilities of survival than with uniformly random playouts. Since all nodes in the tree have been inherited from root, they are mostly in the same situation. The simulation is a stochastical estimator of either the territorial value of the game or the percentage of win (which is determined by comparing the former with some threshold). Since you are favoring systematically one of the players (the one who is in danger at root is always the same player) you are biasing the estimation. Because the variance of a random playout is so big compared with the difference in conditional probability: P(win | a good move) - P(win | a bad move) is a very small number - the smallest bias is too much bias - the program gets weaker. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 games wanted and the next big challenge
Except for the relation between not finding 9x9 games which is *not* real go, you can find as many 19x19 games as you want, I agree with Chrilly. Let's accept it. We are amateurs, all except those who are paid by some University to research on go. And even some of them are, because a serious go project takes many years and some have one semester. We have other jobs and (at least myself) try to work less for the money and dedicate 20 hours per week to go programming. We would be very happy to work 60 hours a week on go programming if someone else paid the bills, but that's not the case. I my opinion, the most important software project of the decade, i.e. writing a non-Microsoft _compatible_ operating system, is called wine http://www.winehq.org/ and also looks amateurish. (I don't really know who works there.) 3D studio and other successful projects started as amateur job, so there is nothing wrong in being amateurs. There is no program today which is so much better than free programs that is worth paying for it, so we can't blame the users. We should blame ourselves for not being able to write a program that is worth its price. Also, I don't even doubt that the day computer go can challenge the strongest pro player, the media will understand the importance of the event. (In fact, computer go is already in the media: The Economist, The Times, Scientific American, Abcnews, Reuters, have all written articles in 2007.) And companies will understand that if they want their names related to a historical event like that with no possible repetition in the future, something like the first man on the moon, they will have to pay for it. The money payed for deep blue will be like comparing 1950s with 2007s football contracts. Go is played only by a small freak community. That's not true. Like chess players were admired in the previous century as superintelligent human beings and today no one is interested in chess except the chess community. Go still keeps the supreme form of intelligence myth. And after go, there is void. Of course, you can always invent new games, but you cannot invent millenary games with millions of players. Someone is going to make millions with this. Don't know when, don't know how. I wish I knew ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: computer-go Digest, Vol 36, Issue 6
terry mcintyre wrote: Lately, I've been studying joseki, and I find that it's hard to really know a joseki until you know why non-joseki moves are bad - and why moves which are locally joseki may be bad in relation to other stones on the board. No doubt. That is the most complicated part. I have found nothing effective for that, although I have some ideas. Anyway, a program that understands joseki well enough to play each corner correctly even if not in relation with the other corners, is playing better than a program which does not understand joseki at all. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: computer-go Digest, Vol 36, Issue 5
George Dahl wrote: Is it still cheating if the program learns and discover's the patterns itself? Then isn't it just precomputing a few things? I agree. Many chess and go grand masters, e.g. Capablanca are supposed to have learned the game as children by watching others play. I do intensive research on my 50K masters games and for me, mastering the game by learning from the masters is the supreme form of intelligence. Except copying a full board, of course. But full board databases also make sense because they save time and avoid the empty sheet syndrome (i don't know how that is called in English) writers suffer. There in not much to reason about an empty board. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Explanation to MoGo paper wanted.
Hi, Magnus Magnus Persson wrote: Weak tactics is a problem of the playouts in my opinion. UCT as a general search method has thus little to do with ladders and other game specific details. If there are no tactical mistakes in the playouts the problems disappear. Also tactics has a large impact on where territory appears in the playout, since much of the noise in the playouts come from tactical mistakes near the end of the game. I was meaning the specific problems already mentioned in this list where you should not start something (e.g. a ladder) unless you a sure to win. The more you play (if you don't win) the more you lose. The best move is hidden by the increasingly negative evaluation of continuing the ladder another step and losing it. In a 9x9 board, ladders may no be very long, but in 19x19 they can. Of course, in the case of ladders that has simple solutions as forcing the playout to follow the atari-lines, but in more complex situations there is no known (to me) solution. Of course, UCT would find the optimal solution with infinite time, but that is not the question. In fact, it is harder to find the solution with UCT than with non stochastic methods. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Explanation to MoGo paper wanted.
Don Dailey wrote: I have posted before about the evils of trying to extract knowledge from human games. I don't think it is very effective compared to generating that knowledge from computer games for several reasons. I would agree if we could have quality games played by computers. In 19x19, of course. But because computer moves are so vulgar when they are tesuji it is because a search has found a killer move, not because the program has good style. The killer moves only apply to that position exactly (or a local subgame whose limits are not trivial to determine). There is not much to learn from killer moves. What programs need to learn is style and from programs you only learn bad habits. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] How can one possibly design an optimal playout agent
Peter Drake wrote: 1) If the computation necessary to find better moves is too expensive, performing many dumb playouts may be a better investment. 2) If the playouts are too deterministic, and the moves are merely pretty good, the program may avoid an important move and thus misjudge the value of a position. Chris Fant wrote: IMO, this is the most interesting part of Computer Go today. How can one possibly design an optimal playout agent when making a playout agent that plays strong is not the solution? The only known method seems to be trial and error. That is the key question of UCT. I totally agree with Peter's conditions and add another two: 3) (should be 1) _Unbiased_ ! The smallest bias ruins everything. and 4) Low variance. Low variance is the clue for improvement. A random move is almost as bad as a pass move. E.g. you can win against a random player by passing your first 180 moves. (I did it with Idiotbot which is not exactly a random player.) As an approximation, if you consider a random move as bad as a pass move, the blunder per move ratio would be equal to the temperature of the game. You are evaluating the value of the game real by summing: v_eval = v_real + t1 - t2 + t3 - t4 + ... The condition of no bias is: E[v_eval] = E[v_real] = E[t1 - t2 + ...] = 0 If the playout was perfect, you would evaluate v_eval = v_real + 0 - 0 + 0 - 0 + ... and you would only need one playout. The variance of the estimator strongly depends on the variance of the Bernoulli process (= the blunder per move ratio if we put it that way) in a way that produces v_eval - 1/2 when |ti| grows or n grows. It is not true that improving the playout is unimportant. Syvain does not claim that neither. I have read him stating the it is important. But you have to follow the rules: minimize blunder per move ratio subject to: The game is unbiased, fast and random enough Some fast ideas could be favoring the moves near the precomputed border of the territory to be defended (ownership maps) or similar ideas that may be fast, unbiased and reduce blunder per move ratio Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] correspondence or turn-based servers
terry mcintyre wrote: Computer Go play in general is nowhere close to dan-level play, but a computer program can read out smaller tactical problems with a very high level of accuracy. That is true. Computers can analyze closed positions as Thomas Wolf's go tools at dan level, but .. .. If in a real game you reach such a position (certainly not before move 100) and the game is still so close that the analysis matters, then you are as strong as your opponent. You may win a game you wouldn't have won otherwise, but that gives you perhaps only 50 additional Elo points because it won't happen frequently enough. Also, testing against the computer will reveal some mistakes you may have overlooked and make your play a little stronger, but it is still = your level + something small. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to GNU and to MoGoBot19!
steve uurtamo wrote: true, and a good point. time management other than attempting to equally divide remaining time among the expected number of remaining moves (which itself isn't so easy to estimate) is complicated. But that is so much better than human time management! If the expected number of moves is based on applicable experience (including, maybe other games with the same opponent) and is updated as the move number increases, just the same as a 70 year old person has a longer life expectation than a 10 y.o. just for having survived 70 years, it will not experience serious problems. Humans, like myself, who do not take part in tournaments want to have at least 1/3 of our time unused to avoid time pressure. Competitors may feel confident with just 5% of their time remaining, but that forces errors that would not have been played otherwise. Humans spend time looking at a clock, and are distracted by doing so. If the remaining time is small, they reschedule looking at the clock again soon, which adds extra pressure. Computers feel comfortable with any time settings, and no matter how naif the scheduling algorithm is, it will always be far better than human scheduling. Computers can safely approach using 99.999% of their time (asymptotically) and there is no other reason why a computer should lose on time than net lag. The reason for extra time (of any kind) is that humans are lost when they run out of time. Therefore, it clearly favors humans, because they would have lost that game. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Opening
Heikki Levanto wrote: I am sure there is a mathematically sound way to measure how symmetric the evaluation is, but my math is a bit rusty, so I am asking if someone can come up with a good way. After that, I'm asking if various programmers would be willing to run this test, and publish the results? A simple idea: 1. Even if you have 3 different types of symmetry .. a. X symmetry (x,y) v.s. (bs+1-x, y) b. Y symmetry (x,y) v.s. (x, bs+1-y) c. Center symmetry (x,y) v.s. (bs+1-x, bs+1-y) (bs+1 = board size + 1 assuming 1-based indices for clarity.) .. it is clear from their expression that the third is implied by the first 2. 2. You could use a simple measure of skewness: http://www.itl.nist.gov/div898/handbook/eda/section3/eda35b.htm Note that skewness measures the *lack* of symmetry. Two measures: One for X and one for Y 3. Possible objections: Since these measures use the third moment of a distribution, they are very sensible to the deviation for the mean. In other words: skewness between the 2nd and 18th row of a 19x19 board weight much more than between the 9th and 11th. To compensate this, you can compute another estimator with the rows (same for the columns) inverted in each half board. Toggle columns: 1 - 9 and 11 - 19 2 - 8 and 12 - 18 ... so you would have 4 estimators: X-direct, X-inverted, Y-direct, Y-inverted. Use the highest, i.e., the worst. Jacques. Java is a religion. Asm hackers don't spend valuable picoseconds arguing with Believers. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] OSS or Free Engines
Hola, Eduardo Eduardo Sabbatella wrote: Take a look at: http://sourceforge.net/projects/javago I get a This project has not yet created any file release packages. message at the mentioned URL. In one of your recent posts you mentioned data mining and that is what I am interested to see how and what you had implemented. Will that be part of your package? Will it be documented? I also have many ideas from statistical analysis that I want to test. In fact I am reformulating all my ideas that worked well on selected endgame problems but could not handle real games to statistical form. I have finally convinced myself that in go when you have a certitude about whatever it is always too late ;-) (Exaggerating, of course.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Hola, Álvaro: Álvaro Begué wrote: Could not compile libego is not a very helpful error message. What exactly did the compiler complain about? My guess is that you don't have the required boost libraries installed. Yes. It must be that. I didn't know about boost libraries. Where can I find that? Actually, in order to get the content of a particular point, we ask its neighbor on the right :) . My biggest patterns are up to 40 neighbors (Manhattan distance = 4) because that includes all nobi, iken tobi, niken tobi, keima and ogeima relations (+ more) and because it makes a difference between the third and the fourth line and between the fourth line and above. But, as you do, I use the nearest neighbors in the lower bits as indices of many LUTs that give immediate answers to lots of questions. Oh, I would be curious to see how you remove a captured string with no loops. So would I. I did not say that the whole program is in assembly language. The assembly language parts are rather short and straightforward. I change conditional jumps by table xlat or by conditional moves. For instance, a function that computes a Zobrist hash of a mask, cmoves a zero and xors zero rather than jumping around the xor instruction if there is no stone. And of course, rather than writing something ridiculously academic, like: Function DoWhateverWith40neighbors(x, y : integer) for dx := -4 to 4 do begin for dy := -4 to 4 do begin if (x + dx = 0) and (x + dx 19) and (y + dy = 0) and (y + dy 19) and (ABS(dx - dy) = 4) do whatever end everything I keep 81 different asm functions for each possible mapping of the borders Instead of calling a function: MyFun(x, y, a, b, c) I call MyFun[wMv9x9](a, b, c) where MyFun[wMv9x9] is a array of pointers to functions and x, y are implicit in the function called. Example: UpNeib_NI[wMv9x9](byte(bijNP), longint(pS), CardinalsBPR); is compiled to: mov esi,[esi*4+UpNeib_NI] xor eax, eax mov al, bl mov ecx, [CardinalsBPR} mov edx, [ebp-$30] call esi (It wouldn't be better with a call to a fixed address.) And the function, instead of the ridiculous loops and conditions is, (say 150 lines) of: or [edi + 2], al shl al, 4 or [edi + 1 + 12], al mov al, [edx + ecx*2 - SizeOf_bccCell + 3] xlat shl al, 2 or [edi + 1 + 12], al shl al, 4 or [edi + 2], al mov al, [edx + ecx*4 + 3] xlat or [edi + 4], al or [edi + 4 + 12], al add edx, ecx mov al, [edx + ecx*2 + SizeOf_bccCell + 3] xlat shl al, 2 or [edi + 4], al shl al, 4 or [edi + 6 + 12], al mov al, [edx + ecx + 2*SizeOf_bccCell + 3] xlat shl al, 4 Now you understand why the board has over 80 000 lines of asm source. Typical 40 neighbor functions have 81 clones and 150 lines. It is only in these functions where there are no conditional jumps or loops, not in the program. But I keep trying ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] June KGS Computer Go tournament: 19x19, an hour each
We all think about UCT all day long, ;-) but universal time is called UTC. The acronym is far from obvious, because: The International Telecommunication Union http://en.wikipedia.org/wiki/International_Telecommunication_Union wanted Coordinated Universal Time to have a single abbreviation for all languages. English http://en.wikipedia.org/wiki/English_language speakers and French http://en.wikipedia.org/wiki/French_language speakers each wanted the initials of their respective languages' terms to be used internationally: CUT for coordinated universal time and TUC for temps universel coordonné. This resulted in the final compromise of using UTC. as I quoted from http://en.wikipedia.org/wiki/Coordinated_Universal_Time ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Lukasz Lew wrote: Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? I only wanted to compare performance ( and see what good ideas you had ;-) ) but could not compile libego. Neither with Microsoft Visual Studio nor with Borland Turbo C++. I am 100% Borland because of the ease of assembly language implementation. Borland passes parameters in CPU registers in a documented way and has an extremely straightforward use of local variables and record structure from asm source code to write things easily that work on the first run. At least for Windows programmers, providing a solution that compiles with major IDEs would help. I assume what you do is standard in Linux, but the things the compiler did not understand neither did I, and I could not find the time for googleing. Anyway, I think a go board system is way too important to be universal. I already have a board system in GoKnot that surely outperforms most of the current programs and my new board system I call HBS (Hologram Board System) does not copy a single line from the old one. I call it a hologram because, as in a hologram, each part contains information about the whole picture. In my board, each cell contains a mask of its nearest neighbors. When you place a stone, everything is updated by automatically written assembly language functions. These functions do not have variables except CPU registers and the board, do not have conditional jumps or loops, of course, no stack frames, of course support multi-threading, etc. The board is *never* rescanned whatever happens. Placing a stone on a 31x31 board is not a clockcycle slower than on a 9x9 board (these are my limits) assuming it finds the same chains. Every bit of info on the board is only updated if it may have changed and only once. With this board I will be able to try things that cannot be tried with libego, but as Don said, If you have a hammer, everything looks like a nail., for lots of methods not using shapes my board is way too heavy, (although possibly faster than most in small pattern modes) so I will write engines with shapes (and Statistics) for a while. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 vs 19x19 (was: computer-go Digest)
Heikki Levanto wrote: I think it is better to stick to 9x9 as the beginners tournament, where it is easy to test new ideas in quick games, and 19x19 as the serious tournament where we can see how good computers are at playing the game like we humans do. I agree 100%. Other board sizes are unnecessary, and if 19x19 makes the 9x9 server decrease in interest, that's the natural evolution of the game. The 19x19 will be the one people will use as a reference of the state of the art in computer go. I am not ready yet, but have worked a lot in computer go this year even if not full time. In July, I will work at least 3 months full time in my engine. The board system is done although not debugged. Debugging it is a software project by itself because it has over 90.000 lines of automatically generated assembly language source code. ( Not kidding. Of course, the board does more that just checking if a move is legal ;-) ) I am eager to join the 19x19 server a soon as I am ready! Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] analysis of UCT and other bandit algorithms for tree search
Remi Munos wrote: .. only when the tree is very smooth, ie. when the branches that appear good (from obtained rewards so far) are actually good and the branches that appear bad are truly bad. Go is a territorial game. I.e. an accumulative game, therefore when you loose territory you could have won, all your expectations are lower, but that has exceptions. I like your analysis until the Figure 1 in page 6. The figure makes an existing and very important UCT problem clear. I tried to make that problem clear in my posts about UCT and the ladder. After that, you give a solution that may be very good for other problems, but I think does not apply to go. Let me explain why. Go is naturally smooth, but with notable exceptions: The exceptions are (Those a human can understand because he may foresee 20 moves or more, there may be others much harder to analyze.) Continuous atari (particularly ladders and ignoring hane on the first row) and semeai fights. In these situations UCT follows like in your figure, very badly. The golden rule is: If you won't win it, don't start playing it. The more you play, if you abandon before you win, the more you loose. These situations have names and ways to be detected, already implemented in go software for years. Attacking them with go-specific enhancements is much more efficient than with a general purpose algorithm, that has side effects. The main side effect why we cannot solve the UCT problem making it less optimistic is that _we need that optimism_. The idea (before it was implemented) sound *too* optimistic, but it worked (to some extent), just because go is globally smooth due to its accumulative nature, even if sometime locally sharp. Without the optimism of UCT, the problem is way too hard to be solved by simulation and MC returns to its pre-2006 state. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Go, scalability with time vs handicap
Christoph Birk wrote: I am sure that Daniel is wrong here ... 2 kyu difference is more like 80% likelyhood of win. That depends on strength. Between a 20 and 22 kyu, it is even lower. But in professional play Daniel should be right. Note that 2 steps means 2 stones handicap. It is clear that in professional play 2 handicap stones is overwhelming. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Sylvain's results
Thanks Sylvain. Sylvain Gelly wrote: The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). In terms of board size (i.o. board area) that is: boardsize^5 Remember my post on the 8th Feb 2007: What I mean is complexity is not, as one could expect, about ~boardsize^4. (The square of legal moves times the square of simulation length.) But even more due to the increase in variance. As Sylvain verifies it is: bsize^5 bsize^4 just as I predicted. Does anyone have an explanation for that other than the increase of variance in the playouts due to their increased length? Note that the difference is _exactly the increase in standard deviation_. (proportional to sqrt(n) where n is proportional to bsize^2.) BTW. There is another stone in the way of 19x19 computer go. Knowledge. Humans play much stronger and do much stronger judgment than in 9x9. But that is is not as easy to predict. A factor of 42 (19/9)^5 in hardware power won't be enough. I hope. ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Simplified MC evaluator ?explained?
Weston Markham wrote: 1. Uniform playouts, as used in practice, are not really uniform over all legal go moves. Generally, pass moves are excluded until necessary, and moves that fill eyelike points are excluded. So, I assume that when you use the word legal, you mean admissible within this sort of playout. That shouldn't make a difference. If you count the pass as a legal move you should also count it as a legal moves in the subpaths. You would have W (subpaths without pass) and W' (subpaths with pass). Since it is only one of the 255 legal moves (counting the expected value of # legal moves as 19^2 - 212/2 where 212 = length of a pro game) it should not be very important even if miscounted. 2. That variance depends on the length of the playout. It is difficult for me to make sense of this statement, simply because not all playouts from a given position have the same length. Of course, but it is reasonable to expect 9x9 playout around 120, 19x19 around 400, etc. That has, at least, two consequences: 1. UCT is stronger for global search studying move 150 than move 5. 2. UCT can also be used for local search on 50-80 empty cells, something astronomically above what can be done with alfa-beta (assuming we want final evaluation, not evaluating nodes at some intermediate state.) Of course, UCT does not talk territory so adding the local subgames is far from trivial. The variance of the stochastic process is not to be mixed up with the distribution of the error of a repeated Bernoulli experiment! Perhaps I have mixed them up. Can you explain more clearly or precisely what the variance of the stochastic process is? Repeated Bernoulli experiments are studied as a stochastic process and, in our case, _the experiment is a stochastic process itself_. We have a nested process: A process whose steps are stochastic processes. Therefore we have the variance of the Bernoulli process which is in the binomial Bi(n, p) but that p is the result of a stochastic process whose variance biases p towards 1/2. I don't don't have a particular mathematical model for that process and model it as a noise. No matter how you distribute it, as long as the expected value is zero it and has the same consequences. This may be clearer: Count each move in the playout as adding a random territory difference in {-3, -2, -1, 0, 1, 2, 3} to the actual territorial value with any distribution whose expected value is 0. The probability of the result being 0 (a win) starting with a good move (initial value = +5) after 10 moves is significantly bigger than starting with a bad move (initial value = -3). But after a million moves the probability of a win is the same for both = 1/2. Because the variance of the experiment is somewhere in k·n the standard deviation is proportional to the sqrt of n = 1000. With a std deviation around 1000 the initial values 5 or -3 are way too small to make any difference. Does this game violate the condition that the number of legal moves for each side is balanced? I mean my argument in the big numbers. Of course, if you take it down to the detail you can find counterexamples. But these counterexamples should be balanced for black and white. In fact, that's what I pretended to say if everything is the same for black and white take the same in an informal sense, there is no reason one of the sides should be favored and p estimates W. What is more important is that it estimates W biased towards 1/2 because the playout is a stochastic process. Even if we can compute W exactly, do we have any reason to think that its value is a good estimate of the minimax value of the game? It is *not* a good estimate. I am not trying to advocate in favor of MC as a panacea. In the beginning I was among the critics and have done an effort to understand it better. Slowly I am becoming convinced of the possibilities specially in combination with other methods and now I have written a UCT engine, mainly for analysis. W fails to represent the minimax value of the game at least in two common situations: self-atari moves that would be a good idea if the opponent was kind enough as to forgive the capture and ladders. But _that is_ what uniformly random MC evaluates, not my fault ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Don Dailey wrote: I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. I thought about something similar but only for initializing the counters: introduce 10 fake playouts and estimate the number of wins by a function returning something in [0, 10]. After that, use UCT with real playouts. If your guess was right, that should improve performance, but if it was wrong you are doing nothing irreversible except loosing time. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo
Hello Sylvain Sylvain Gelly wrote: If the program blundered as you said and still wins, it means that the program already won much earlier in the game. You are totally right. I said that in my post already. But what the user thinks is: 1. He was behind, but not desperately behind. 2. The engine did a mistake and he should have been ahead, because he counts Japanese. It is not a matter of chinese or japanese rules. It is. With Chinese, playing in your own territory is worth 0, in Japanese it is worth -1. The difference is not important when there is territory in dispute because the move is bad in either case. But at the end it does. That's the good news for us: It does not make any diference as long as the program plays a friendly endgame. this behavior has been explained many times by developers I know, and so has general relativity. They still don't get it. Our point is: they are all wrong (Which can be proved.) Their point is this UCT behavior is unpleasant. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo
Hello Don Don Dailey wrote: Many people DO play chess after the game is over. They continue to play a game long after they could have resigned. My example wasn't very good but I meant over literally. = The king is captured (changing the rules a little). How does Japanese make any difference? I just answered this: It is the impression the user gets because an unnecessary self protecting move changes the score form -.5 to +.5 in his mind. I mostly agree with both of you. It is not a priority to change this behavior. But what surprises me is that you pretend that it has not to be done at all. For a commercial program to be friendly, it has. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] professional knowledge
Darren Cook wrote: All except joseki-knowledge is board-size independent. Maybe human player's adapt to different board sizes without even noticing. But if you try to model strategy with algorithms it is totally board size dependent. The extreme case is 5x5 where black 3,3 claims the four corners. The relative size of the corner, the sides and the center is crucial. Move timing, distances between stones, everything. I like use the two day argument because I believe a top level computer go program should have two phases (But the first, of course will be much longer than 50 moves.) 2nd. When all local fights can be searched. If is a matter of understanding their conditions and interactions. The program is an endgame solver. It plays kami no itte for the last ¿m? moves. Complexity increases with board size, but in a known way. 1st. All the rest of the game. In this part there is no certitude. The program uses stochastical evaluation (UCT) together with knowledge to navigate in the fog expecting to be ahead when the endgame solver finds the harbor. *All* the knowledge used in the 1st step is board size dependent. UCT is not, but UCT's efficiency (and variance) is. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re:[computer-go] MoGo
Sylvain Gelly wrote: You should also know that we never claimed that MoGo plays 9x9 go near the level of a professional go player, . . . Just curious: Do 9x9 professionals exist? When we say professional we mean 19x19 professional. Of course, there must be a correlation. One expects an Olympic final level 100 meter runner to run 400 meters much faster than any of us, but not faster than a 400 meter runner. Call me picky if you want, but I spend a lot of time processing go knowledge and none of it is board size independent. The relative value of the corners, the sides and the center are too different. Josekis do not work at different sizes either. I am repeating myself, but I constantly repeat the idea that in a two day professional game the first day must be dedicated to the first 50 moves. The precise value of these moves cannot be determined by search as in the end of the game. Professional players use study and experience. And that is board size dependent. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo
Don Dailey wrote (about big/small wins) It actually surprises me that go players care about this ... One difference with chess is that you don't play chess after the game is over. The comparison could be: the king is captured, the loser keeps playing and then the winner gives the queen for nothing. Bad moves hurt! And we get to the really important part of a any program: The user. Many users feel stolen by UCT programs. I have read that in the KGS chatrooms. Normal users do not count with +/- 0.5 point precision. They have the impression the program blundered and they caught up. But when the program counts, surprise!, it wins by 0.5 points Chinese. The users were thinking Japanese even if they accepted Chinese rules. In fact, they did not have the choice. They get the impression the game was stolen by technicalities after they saw the engine blunder many times. Of course, I know there is a good reason for how UCT works. And improving style is much less important than improving strength. But many players don't want to adapt to computer settings. They want computers to win the game as they have always played it. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Time Control for the new CGOS
Is 10 minutes a standard and if so it is standard for 19x19 or 9x9? For 19x19 I find it a little too fast. I would prefer fastest: 4 sec/move (x240 moves) = 16 min slowest: 30 sec/move (x240 moves) = 2 hours I would like to try both. Usually fast because, as you pointed, you get useful results earlier, but maybe one week each month, slow. 240 moves is above the average length of a 19x19 game. In my 50K games database it is 212 and games ending before move 100 were removed, but among weak programs it is low. Darren Cook wrote: That summarizes my main argument against short time controls: it limits the choices for experimentation so to meet time controls everyone will end up running very similar MC programs. With more time people have some breathing space to experiment with new ideas and intelligence. I agree even if MC can make very good usage of extra time, it is not the only approach that does. As said, doing *both* is also an option. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Help me test CGOS
Hellwig Geisse wrote: I just finished the translation of the old TCL script cgosGtp.tcl to plain C . . . Thanks Hellwig . I will try your program tomorrow. I prefer hacking C than tcl because its more transparent. I see what the tcl sends, but I don't know what details it may hide, and these things often result in a lot of wasted time. This is nothing against tcl, it is just that I don't like learning new languages I don't need ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Help me test CGOS
Hi Don Could you provide some minimum protocol documentation so that we do not have to use any scripting language? The tcl script seems very simple. Is it possible to just open greencheeks.homelinux.org:6867, send login and then read/write commands? This way everyone would be free to implement the connection its own way, handle reconnection automatically in case of power down, etc. In my case, using a scripting language not only requires to install unnecessary software for an otherwise trivial task, but writing a small bridge application that is called by the script and communicates with the GUI running the engine. The GUI could handle the connection much better. I am very interested in being an active member of the 19x19 server when its ready. (And I am ready myself, mid-July, I hope.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Grid Cosmos
Hi Yoshii I have some questions about your program. 1. Is this a complete go engine? I have renamed the gnugo.exe file in the /exe directory and the program no longer works. If it is not an engine, what is it? 2. The program has a 368 Mb file named Tree_Set in the /exe directory, the pattern library, I presume. The source code is 4 Mb resources included. I imagine that if that file has any sources, they are not included, or is that file the result of some computing? Are your patterns learned from games? 3. How strong is your program? 4. Why did you choose .net? (I don't expect an answer to this. I wouldn't understand anyway. I never understood the need of Java, much less that of an incompatible clone. I can only imagine reasons against. And sooo many!) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC - Estimating a moves true probability of winning
Hello, Just an explanation on something I may have explained badly. I see we agree in the fundamental. Correcting bias in that estimate should lead to better sampling. This is usually called continuity correction http://en.wikipedia.org/wiki/Continuity_correction. The estimator is not really biased, but because it is a quotient of integers it requires a continuity correction specially when the integers are small or zero is involved. That is included in the intervals I suggested. To use these results, you must make some assumption about the underlying distribution of a move's probability of winning. That's the good news. You don't. There is no need to understand what complex mechanism produces p. Only that: same position == same p. If you take a good look at your tests, they will make very specific null hypothesis which in effect make at least some assumption about the underlying distributions (or try to wash away all effects with the central limit theorem). Well, the assumption that p is estimated from the binomial because we are counting Bernoulli experiments of constant p is a mathematically sound method used universally. It does not require go knowledge, that's what i meant. When n is big enough, the binomial converges to the normal and that's what we use for inference. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Big board. Temperature
In CGT the temperature is the difference between the value if you play and the value if you pass. The name question should be answered by a native English speaker, but I guess it is an common use of the word hot. Let's call it hotness ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/