Re: [computer-go] U. of Alberta bots vs. the Poker pros
- Original Message - From: Tom Cooper [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Saturday, July 28, 2007 3:42 PM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros At 12:42 28/07/2007, you wrote: At 02:58 28/07/2007, Arend wrote: On 7/26/07, chrilly mailto:[EMAIL PROTECTED][EMAIL PROTECTED] wrote: This is a remarkable result. I think poker is more difficult than Go and of course chess. I am as surprised by this statement as everyone else. Of course you have to develop some mixed strategies, try go guess implied pot odds, folding equity etc. but assuming you have access to a large database of high level poker games to analyze, why should it be that hard, esp. in 2-person limit Hold'em? Arend Decision theory is trivial, apart from computational details (just like playing chess!). From David J.C. MaKay, Information Theory, Inference and Learning Algorithmus, Chap. 36, Decision Theory. Thats exactly what I wanted to say. There are some nasty computational details to solve, but it is conceptually clear. One can discuss, if the same holds for Go. For me the details are somewhat more nasty, but I can see no conceptuall difference to chess. The concept, that Go is sooo special and sooo different was one roadblock for progress. Suzie is on 9x9 clearly better than traditional programms and on 19x19 in the second-league. We would just have to wait for further hardware progress (or parallize it) that it catches up also on 19x19. UCT is even more successfull than Alpha-Beta. UCT is - apart from details - also trivial computation. But it is not clear what the best concept in Poker is. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] U. of Alberta bots vs. the Poker pros
- Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Friday, July 27, 2007 3:26 AM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros I don't understand this. For a given hand the odds of winning can be easily calculated for poker and the best play can be formulated accordingly. It's like to program a com[uter to win a coin toss. I would be surprised if any side win big. The only thing a computer can to is to model opponent's behavior, which may deviate from the best play. What did I miss? DL A lot. The chance alone is meaningless. It can be very profitable to play a hand with 20% chance of winning and it can be a desaster. If you have pot odds of 10:1 the 20% are a good deal, with pot-odds 1:1 its a desaster. The direct pot odds are easy. Whats in the pot and whats the money I put it. But the interesting figure are the implied-pot-odds. What money do I have to put in in all betting rounds and what's the pot at the end. This depends of course also on the actions of the opponents. Another point is: The winning-chance depends on the action of the opponents. If one raises and the opponent folds, one wins with every card. Chrilly -- AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] U. of Alberta bots vs. the Poker pros
This is a remarkable result. I think poker is more difficult than Go and of course chess. My hypothesis (its just a hypothesis) for the success is. There is someone - Dave Billings - who worked for many years very consequently on the topic. And he is able to motivate a lot of other good people to go along with him. And he gets probably also a lot of support from his boss, J.Schaeffer. And of course, there is some prospect to win fame and money. The conditions for solving a problem are always at least as important than the problem itself. Maybe are the conditions in Poker better than in Go. As said above, I think the problem is in Poker harder. They have of course not solved the whole problem. Heads-Up limit Hold'Em is the - for computers - easiest game. But its nevertheless remarkable that they are on-par with the Poker-GMs. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thursday, July 26, 2007 6:02 AM Subject: [computer-go] U. of Alberta bots vs. the Poker pros -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Humans beat poker bot ... barely: http://cosmiclog.msnbc.msn.com/archive/2007/07/25/289607.aspx - -- *** FULL-SPECTRUM DOMINANCE! *** * In advance of the Revolution: * Get facts get organized * * Fight the Man! * thru these sites movements * * Critical endorsement only Most sites need donations * * http://www.buynothingchristmas.org Buy Nothing Christmas * * http://www.aflcio.com/corporateamericaExecutive PayWatch * * [splitURL] /paywatch/ceou/database.cfm Database * * http://www.africaaction.orgAfrica Action * * http://www.msf.org Doctors Without Borders * * http://sweatshopwatch.orgSweatshop Watch * * http://www.maquilasolidarity.org Maquila Solidarity Network * ** Revealed Truth pales in comparison with the method of Science *** GPG fingerprint = 2E7F 2D69 4B0B C8D5 07E3 09C3 5E8D C4B4 461B B771 -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFGqBzQXo3EtEYbt3ERAhQzAJ9GxAD38q8K1pU8Qp7o5Ok6mi3k3wCdHwc4 8w17aqALXM/oib5umPdBDRo= =VmGC -END PGP SIGNATURE- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] U. of Alberta bots vs. the Poker pros
If one makes e.g. something like Hydra, one has already almost all at hand. There is the work of Ken Thompson, of the Deep Blue team, the work of Frans Morsch, Ed Schroeder... There is an industrial quality infrastructure, databases, interfaces, there are people who have already learned their lesson One is a dwarf standing on the shoulders of giants. The Polaris team had not such an infrastructure, but they build it over many years and with a lot of effort for themself. The effort is comparable to the big chess projects. Not in money terms, but from the man-power investments. In Go their is neither. There is no infrastructure, one is a dwarf standing on the shoulders of dwarfs and their is not such a team like the Polaris one so far. Maybe the INRA group succeeds to make something similar. I have no idea, but I can't see at the moment nobody who works like the Polaris or Deep Blue team. One can discuss, if Go or Poker is harder. Its definetly harder than chess. But I am also convinced, that Go is not that hard, its this poor state of the affairs which makes the problem that hard. Chrilly - Original Message - From: Harri Salakoski [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, July 26, 2007 11:44 AM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros think poker is more difficult than Go and of course chess. I have only studied poker AI basics and coded game rules, learned play slightly winning net poker. But however dare to say my opinion that I totally disagree. Sounds like somekind of poker hype that it is as tough problem than Go game AI 19*19 table. It is offcourse very complex interaction problem but my opinion is that it is still lot of easier problem. It is maybe even possible that it can't be proven and that theory you are right, because poker can be iterated forever and that in theory propably there is _no_ best strategy. I see it very same/similar thing than in super simple iterated prisoners dilemma problem. There just is no best strategy, any strategy has some other dominating strategy, so I have understanded it. But there is very good strategies, every bet when you but your money in table you play even stronger(bluff), play normally or slow play present weaker hand than you actually have. That thing iterated, remembering what opponents have done earlier (like in prisoners dilemma) it is tough problem, but saying it harder than go game is not true at least in practise. In practise I see it so that computers have advantage in poker other things than this complex interaction, where advantage is in humans. As computers can actually calculate odds and propabilities exactly, that advantage is maybe slight, but something which similar don't exist in go-game. But yep just started poker AI in my project http://sourceforge.net/projects/narugo, coded there SimpleActionGenerator, in estimated couple years work it is gonna plays better poker than starter player :| So imho if somebody states that poker is harder AI problem than go-game, it sounds poker hype. t. Harri - Original Message - From: chrilly [EMAIL PROTECTED] To: [EMAIL PROTECTED]; computer-go computer-go@computer-go.org Sent: Thursday, July 26, 2007 10:32 AM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros This is a remarkable result. I think poker is more difficult than Go and of course chess. My hypothesis (its just a hypothesis) for the success is. There is someone - Dave Billings - who worked for many years very consequently on the topic. And he is able to motivate a lot of other good people to go along with him. And he gets probably also a lot of support from his boss, J.Schaeffer. And of course, there is some prospect to win fame and money. The conditions for solving a problem are always at least as important than the problem itself. Maybe are the conditions in Poker better than in Go. As said above, I think the problem is in Poker harder. They have of course not solved the whole problem. Heads-Up limit Hold'Em is the - for computers - easiest game. But its nevertheless remarkable that they are on-par with the Poker-GMs. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thursday, July 26, 2007 6:02 AM Subject: [computer-go] U. of Alberta bots vs. the Poker pros -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Humans beat poker bot ... barely: http://cosmiclog.msnbc.msn.com/archive/2007/07/25/289607.aspx - -- *** FULL-SPECTRUM DOMINANCE! *** * In advance of the Revolution: * Get facts get organized * * Fight the Man! * thru these sites movements * * Critical endorsement only Most sites need donations * * http://www.buynothingchristmas.org Buy Nothing Christmas * * http://www.aflcio.com/corporateamericaExecutive PayWatch * * [splitURL
Re: [computer-go] U. of Alberta bots vs. the Poker pros
- Original Message - From: steve uurtamo [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, July 26, 2007 7:29 PM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros i think that you might be confusing two important things: i) the difficulty of a problem. ii) the amount and kind of effort that has gone toward solving a problem. No, not at all. But my point is: For progress in any field the difficulty of a problem is less important than the urgency/interest of society to solve it. Science and technology is not driven by the internal logic of the science, but by the interest of the society. Once there is a very high social demand, there is big progress in a field. There is the proverb war is the mother of all things. A lot of innovations are made related to war. In times of war the social urgency is highest and costs do not matter. E.g. the atomic bomb was build within a short time, jet-propulsion, computers were developed .. In medicine progress is made, if it is a rich-mans sickness, and almost no progress is made if its a poor-mans fate. E.g. There is considerable advancement in AIDS-medicine, because it was at least initially a rich-mans sickness, there is almost no progress in Lepra. This can not be explained by the intrinsic difficulties of the deseases. It is also quite a hard problem to generate realistic 3D effects in real-time. There is high social interest (the kids have enough money), so one develops special purpose massive parallel hardware like the latest graphics cards or the Cell processor. The action players and not anymore the D.O.D. are nowadays the driving force behind hardware-development. If there would be the same interest for Go, one could develop special purpose Go-Hardware with an impressive speedup. But Go is like Lepra. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] U. of Alberta bots vs. the Poker pros
- Original Message - From: steve uurtamo [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, July 26, 2007 5:17 PM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros There is certainly more money to be made in poker than in go. Yes, but its also more difficult. do you mean this in a casual, unsubstantiated way, or in an exact way? Both. Its probably not so difficult to make a simple bot. But it is also not difficult to make a simple UCT player. But I am sure, that reaching the level of Polaris is more difficult than writing the best Go-programm. I have the feeling, that Polaris is a very serious project. Its certainly not possible to beat it out from nothing like Crazy Stone and MoGo have beaten the Go programms. There is also a lot of work in these 2 programms too and it is not really out of nothing. But its nevertheless not comparable to the work the Billings-group has done. There is also a very large gap between Polaris and the rest. Without Polaris, everybody would say: Oh, its as difficult as Go, the programms are in relation to humans at about the same level. And now Polaris is strong and the argument is: This is because Poker is much easier. No, they have done a better job. In the exact way its comparing different things. The state space is in Go larger, but Go is from the mathematical point of view in the trivial class: Finite, Full-Information, 2 Players, Deterministic, Zero-Sum. Poker has a random-player and hidden information. In the general case its an N-player. Chess/Go... can be played in an autistic way. There is no need for an opponent model. Just play the best moves. In poker one needs an opponent model. The game-theoretic optimal strategy is only in special cases sufficient. The Polaris-Human match played also the most simple version. Heads-Up Limited. Non-Limited is already much more complicated, because the implied odds have a much greater variance. Or in other words: The opponent-model is much more important in non-limited. In the N-persons version, the state-space explodes too and in this case its not even clear, what a perfect strategy is. I assume Polaris would not be able to be top ranked in the Poker world-series. It would never come in the final round to play Heads-up. The humans would also form a coalition to kick it out at the beginning and real competition would start only afterwards. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] U. of Alberta bots vs. the Poker pros
Already invented. There is the Alberta Poker-Server. Chrilly - Original Message - From: Chris Fant [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, July 26, 2007 6:16 PM Subject: Re: [computer-go] U. of Alberta bots vs. the Poker pros Someone start a CGOS-like poker server for bots. ~10 person tables, No Limit Texas Hold-em. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] U. of Alberta bots vs. the Poker pros
I think you mean Darse Billings. Yes, sorry, I can not remember names. There is certainly more money to be made in poker than in go. Yes, but its also more difficult. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Hint for good Bayes book wanted
I have a Phd in statistics. But Bayesian methods were at that time a non-topic. I know the general principles, but I want to learn a little bit more about the latest developments in the field. Bayes is now chic, there are many books about it. I assume also a lot of bad ones. Can anyone recommend me a good state of the art book about Bayesian inference. Should be somewhat in the applied direction, but also with a sound mathematical background. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hint for good Bayes book wanted
Thanks, I did also a search on Amazon and these two looked the most interesting ones. I can order now with greater confidence. Chrilly You could try something like: Information Theory, Inference Learning Algorithms by David MacKay or maybe Data Analysis: A Bayesian Tutorial by Devinderjit Sivia John Skilling Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hint for good Bayes book wanted
I have the Neural Network Book from Bishop. It is also a good book. It puts Neural Nets into the proper statistical framework. Chrilly - Original Message - From: George Dahl To: computer-go Sent: Monday, July 23, 2007 6:37 PM Subject: Re: [computer-go] Hint for good Bayes book wanted I own that book and can also recommend it. - George On 7/23/07, Łukasz Lew [EMAIL PROTECTED] wrote: Absolutely the best book I've seen is: Christopher M. Bishop Pattern Recognition and Machine Learning It's totally awesome! Strong points: - It have both Bayesian and non Bayesian ways explained - the explanation is clear - figures are so helpful (and aesthetic) - it concentrates on prediction and classification and have algorithmic perspective (contrary to MacKay's book) There is a free chapter on graphical models: http://research.microsoft.com/~cmbishop/PRML/Bishop-PRML-sample.pdf Lukasz Lew On 7/23/07, chrilly [EMAIL PROTECTED] wrote: I have a Phd in statistics. But Bayesian methods were at that time a non-topic. I know the general principles, but I want to learn a little bit more about the latest developments in the field. Bayes is now chic, there are many books about it. I assume also a lot of bad ones. Can anyone recommend me a good state of the art book about Bayesian inference. Should be somewhat in the applied direction, but also with a sound mathematical background. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Slides for Villach-EC Lecture
However, I have to disagree with this statement: UCT: Complete Antithesis to AI-approach Martin Mueller quotes J.McCarthy in his thesis: The research of Go programs is still in its infancy, but we shall see that to bring Go programs to a level comparable with current Chess programs, investigations of a totally different kind than used in computer chess are needed. UCT is different to Alpha-Beta (not totally, because its some other form of search, but it is different). I am sure, McCarthy had not UCT in mind. It was always the goal of McCarthy and his followers to simulate and to surpass the human mind. HAL in Stanly Kubrics Odyssee in space 2001 is the dream-computer of this discipline. UCT has nothing to do with human Go. It has some similarity to the behaviour of ant-collonies (its not in the technical sense an ant-colony algo). It was never the goal of AI to explain ants. I really thing it is exactly a modern AI approach!! Also it is a general algorithm applied to many different domains (and many are not two player games, ie max-max problems and not min-max). I full aggree, it is a general and very interesting algorithm which can be applied to many domains. How would you define modern AI? Obviously it is not the classic approach to mimic humans anymore. But what is it? In my opinion is UCT a statistical estimation method. The armed-bandit is classical statistical problem. I think it is exactly the bad example for the anti-drosophila thesis... What do we learn about the human mind from UCT? Chrilly ___ 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
How would you define modern AI? Obviously it is not the classic approach to mimic humans anymore. But what is it? For me it is when we (I was not there :-)) become less philosophical and more precise about what we want. We want a system which use data to improve itself in order to adapt to unseen situations. In this sense the Elo-System is an AI algorithm. If you feed more data/games the quality of prediction increases. It is in fact a weakness of the Elo-Rating that this is not taken into account (newer systems like TrueScore do). Remi used an Elo-Rating (Bradley-Terry model) for his pattern classifier. In this broad sense UCT is AI, but I would classify it as a branch of applied statistics. Bradley-Terry was invented long before the name AI was coined. What do we learn about the human mind from UCT? Nothing and that's not the goal, I simply don't care. You are already fallen from grace :-) You just want to make a strong Go-programm and develop some good - general purpose - algorithms :-). (There is a famous article of DonskeyJ.Schaeffer with the title Falling from Grace in 1989). Chrilly P.S.: I am frustrated in the sense that you book for holiday a hotel and when you arrive, you see that it is - according your standard - only **. This has in my case a very positive and not at all frustrating background. I get in the moment a lot of interesting and well paid offers for contracts (its a little bit selling the Hydra-fame). Humans adapt quick to higher standards and I am therefore not satiesfied anymore with the Go-hotel I have booked last year. ___ 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
Below is my favorite one in the list. An example of this are neural-networks. Neural networks are just a parameter-free optimization/estimation method. No magic at all, just a boring and not very efficient estimator. Chrilly Warning: Cynical Definition... My definition of AI is any algorithm that is new in computer science. Once the algorithm becomes accepted then it's not AI, it's just a boring algorithm. At one time windows, mouse, menus, scroolbars etc. were considered an AI technique for makeing computers understand natural language. (The menus are a list of valid words the system understands) This is also why I study Cognition, not AI. R. Keene Chrilly, your definition of AI is too limited. See, for example, http://www.cse.buffalo.edu/~rapaport/definitions.of.ai.html. Regards, Hideki (gg) chrilly: [EMAIL PROTECTED]: However, I have to disagree with this statement: UCT: Complete Antithesis to AI-approach Martin Mueller quotes J.McCarthy in his thesis: The research of Go programs is still in its infancy, but we shall see that to bring Go programs to a level comparable with current Chess programs, investigations of a totally different kind than used in computer chess are needed. UCT is different to Alpha-Beta (not totally, because its some other form of search, but it is different). I am sure, McCarthy had not UCT in mind. It was always the goal of McCarthy and his followers to simulate and to surpass the human mind. HAL in Stanly Kubrics Odyssee in space 2001 is the dream-computer of this discipline. UCT has nothing to do with human Go. It has some similarity to the behaviour of ant-collonies (its not in the technical sense an ant-colony algo). It was never the goal of AI to explain ants. I really thing it is exactly a modern AI approach!! Also it is a general algorithm applied to many different domains (and many are not two player games, ie max-max problems and not min-max). I full aggree, it is a general and very interesting algorithm which can be applied to many domains. How would you define modern AI? Obviously it is not the classic approach to mimic humans anymore. But what is it? In my opinion is UCT a statistical estimation method. The armed-bandit is classical statistical problem. I think it is exactly the bad example for the anti-drosophila thesis... What do we learn about the human mind from UCT? Chrilly inline file ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Slides for Villach-EC Lecture
Sorry, it is TrueSkill and not TrueScore. http://research.microsoft.com/mlp/trueskill/ Chrilly - Original Message - From: Brian Slesinsky [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Saturday, July 21, 2007 9:10 PM Subject: Re: [computer-go] Slides for Villach-EC Lecture On 7/21/07, chrilly [EMAIL PROTECTED] wrote: If you feed more data/games the quality of prediction increases. It is in fact a weakness of the Elo-Rating that this is not taken into account (newer systems like TrueScore do). Can you provide a link to TrueScore? My searches are coming up empty. - Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Interesting Test Position (for UCT)
Why not put both version on CGOS and find out? - Don We have at the moment 3 GUIs and each of them does not support the protocoll. The main GUI is from GoAhead. Its written in old Atari-Basic and according to Peter Woitke its difficult to integrate it. ChessBase has promised a better GUI, but they are busy with other things and Go has obviously low priority on their list. But thats not their fault, because my input was even less. I have written a C# Prototype-GUI. But I have no time and also not much interest to develop this further. I have good jobs in industry. Working 2 weeks on an GUI costs me indirectly 5.000 Euro. CGOS is not worth this money. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Interesting Test Position (for UCT)
New lesson learned. It depends on the rule set if something is correct or a blunder. So far the Go-masters told me, it does not matter, its practically the same. Obviously its not. This is not some weired, constructed position, it really happened and it does not look strange at all. Chrilly - Original Message - From: Erik van der Werf [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, July 12, 2007 12:32 AM Subject: Re: [computer-go] Interesting Test Position (for UCT) On 7/11/07, chrilly [EMAIL PROTECTED] wrote: Attached is an interesting testposition which occured in UCT-Suzie against Peter-Woitke. If black plays 37 c4 the game is lost by 0.5 points. If Black passes, white gets a lot of threats. Black can choose between a safe loss, or some risk and a win. UCT-Suzie and the public domain version of Crazy-Stone played the save loss. Seems like you're mixing up Territory and Area scoring. Under area scoring rules the programs can strengthen their (final) position by playing in their own territory. (Crazystone as Black would win under Chinese rules) The example illustrates why Japanese rules provide a slightly more interesting endgame. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Why are different rule sets?
I am playing competitive tennis-table. There were for years a heated debatte if the ball-diamater should be increased from 38 to 40mm and if the set shall go to 11 instead of to 21. A few years ago, the decision was taken to play with the 40mm ball to make the game slower and in turn to reduce the set to 11. Since then Chinese, Japanese, Korean and the rest of the world play with 40mm and stop at 11. After a short transition time, there is no discussion at all about the new rules. Tennis, soccer, chess is played all over the world in the same way. Why is it not possible to establish uniform rules in Go? Is there not something like a FIDE or a FIFA ? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Why are different rule sets?
I think your table tennis analogy is not really applicable. The rule changes in table tennis were presumably motivated by the need to fix a real problem, and really changed the game. Yes, due to the advancements in rubber technology the game become too fast. Bumm-Bumm-Over. Furthermore the ball should be easier to spot on TV. Another way would be to limit the rubbers, but making the ball larger is easier to control and define. But it was a significant change. New ball technology had to be developed, old balls become absolete, the rule is a disadvantage for Bumm-Bumm players... On the other hand, all the rules arguments in Go are really only applicable to incredibly marginal, bordering on imaginary situations. There's no motivation to change the way the game is actually played. For computers special cases matter. Especially for a search based programm. A search based programm finds every possible special case and plays into this case, because the opponent does not prevent it. Are there something as Universal accepted computer-Go rules? There is - at least on paper - a computer FIDE. The IGGA. Is there something as the IGGA computer-Go ruleset? Are all tournaments played according a well defined and uniform rule set? Chrilly ___ 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?
Jesus, there are not just Japanese, Chinese rules, there are ING, AGA... I learned today, that suicide is allowed under some rules... I thought, Go is a well defined game with a very clear mathematical rule set. There are discussions in other sports too (e.g. in Table-Tennis), but nevertheless there is usually a reasonable compromise, everybody can live with. There is at the end some pragmatism. This pragmatism is also quite missing in chess and it seems to be absent in Go. The explanation I have for chess is: Chess players have a board infront of their head. The difference to Go seems to be: The Go-Board is even larger. Chrilly I think the - Original Message - From: Robert Jasiek [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, July 12, 2007 5:04 PM Subject: Re: [computer-go] Why are different rule sets? chrilly wrote: Why is it not possible to establish uniform rules in Go? As somebody having taken part in the International Go Rules Forum, which has been meant to unify the rules, I can tell you the reasons: The major split has - not surprisingly - occurred again between the Area Scoring (China, Ing, AGA, supported by the EGF delegates) and the Traditional Territory Scoring (Japan, Korean, supported by some IGF delegates) factions. The reasons are: - The territorialists (or their influential majority) don't want to compromise. They reject even compromises that are very close to their current rulesets. They want to keep at least 99.9% of their tradition. - The territorialists play on time for the purpose of leaving things as they are. - The majority of the Chinese (except Mr. Hua) has been too silent during the discussion because they have not educated themselves well about the theoretical background of rules discussion. - The Ing delegates played too much on aiming at Ing-specific aspects instead of going for compromise earlier and could bear too little factual criticism. After the territorialists had gone, the arealists solved every secondary issue quickly, all expressed a good will and time schedule for solving the major issues, and then (so far) have stopped further unifying at least the Area Scoring rules: - The Chinese and Ing delegates have been almost completely silent since the last meeting. - The AGA delegates slowed down discussion for some months. - The AGA delegates and every European delegate or expert (except myself) insisted on discussing and aiming at superko again while during the last meeting it had become pretty clear that the Chinese and Ing delegates would not accept superko at all. If you need to criticise also me, you might argue that I did most of the factual discussion instead of being simply silent and letting the Asians do whatever they might have liked (although IMO it did not seem that they would have advanced any sooner then and it would have meant for sure that the rules would have got significantly more flaws). Summarizing, the overall intention to compromise or at least to accelerate factual discussion is still by far too small. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Why are different rule sets?
Does Chrilly have anything to do with this project? -Josh No. Up to my knowledge a student makes his Diplomarbeit (masters-thesis) on this topic. But building such a machine is somewhat beyond a masters thesis. The problem is: There are no funds, no money available. Generally the Univ. Paderborn has relative a lot of money for hardware, but it is very difficult to get money for software development. Not just for Go, for any field. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Interesting Test Position (for UCT)
Attached is an interesting testposition which occured in UCT-Suzie against Peter-Woitke. If black plays 37 c4 the game is lost by 0.5 points. If Black passes, white gets a lot of threats. Black can choose between a safe loss, or some risk and a win. UCT-Suzie and the public domain version of Crazy-Stone played the save loss. See also comments in the sgf-Files by Peter Woitke. Alpha-Beta-Suzie plays the position right. If one replaces for such situations the Rollout by the AB-Eval also the UCT version plays correct. According our tests AB-Suzie is on 9x9 slightly stronger than UCT-Suzie. But UCT is plain-vannila, about 100h development time. AB-Suzie about 1500 h (mainly by Peter Woitke). The h/Elo ratio is much better for UCT-Suzie. Replacing always the Rollout by the AB-Eval is worse. With other words, UCT is not in generall the better tree-search. It is better for a Rollout-Eval. I think AB-Suzie is for humans more difficult, because it plays more aggressive. But sometimes too aggressive. If its ahead, it plays still risky. The UCT-version plays such positions safly home. The test is biased, because the human is always Peter Woitke. The Go-European Championship in Villach/Austria will be a better test. Chrilly UCT_verrueckt_02.sgf Description: Binary data ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Who else uses Hashtables in UCT?
I have no finished a plain vanilla 9x9 Suzie-UCT Version. The UCT-tree is stored in a Hashtable. I am interested who else uses this approach. The reason for using a hashtable was: I was too lazy to implement an explicit tree. At least at 9x9 I have no problem with memory size. In fact there are 2 hashtables, one for the Alpha-Beta and one for the UCT-Version. With the default parameters each version uses 160 MB. A chessprogrammer in Go-Land, part X: I interpreted SuperKo as repetition of position (which seems to be correct, although Stefan Mertin told me, there are numerous versions of SuperKo). I used the Nimzo/Hydra code to detect this. But there is a - not a very subtle - difference between Go and Chess. A move which generates a repetition of position is in Chess legal, in Go it is'nt. But I assumed its legal and had quite complicated and buggy code to handle this case. I did not know how to evaluate it. It came not to my mind, that its just an illegal move and one only has to generate the nextbest one. Stefan Mertin told me the difference several times, but it did not help, only the advice of Peter Woitke, just delete this stupid code, was the right instruction level. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Who's going to the Gifu Challenge?
- Original Message - From: Ian Osgood [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, July 09, 2007 8:01 PM Subject: [computer-go] Who's going to the Gifu Challenge? From what I can tell, there has not been a clash of the Go titans since the 2003 Gifu Challenge, which had all of KCC Igo, Haruka, Go+ +, Goemate/Handtalk, Many Faces, GNU Go, and Go Intellect participating. (This was the last public competition for many of these programs.) It seems with the tuning of MoGo and CrazyStone for the full size board and their recent success at the Olympiad, that there is a chance to knock KCC Igo (sold as Silver Star in Japan) from its four year throne. Are any of the Mogo, CrazyStone, and other professional program authors leaving room in their autumn schedules to travel to Ogaki City, Japan for this year's Gifu Challenge? Is there a price money? Or at least some sponsorship for traveling? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 9x9 games wanted and the next big challenge
Sil wrote: How about http://home.wwgo.jp/jp/minigo/ It seems that only 24 games are available. Is the whole collection available somewhere? Rémi I have read dozens of times that computer-Go is the next big challenge. But in fact it is a completly amateuristic field where even the most basic things are missing. As a chess programmer I did not even think about, that it is a problem to get a good game collection. There are no proper interfaces, no serious tournaments, a wired data standard... AND there is no money involved: For professional programming I get 60Euro/h (1Euro=1.35$). 2.000h x 60 = 120.000 Euro. This equation is of course completly wrong. One can not make in 2000h a very strong Go programm and one can not earn 120.000 Euro with it. A more realistic equation is; 20.000 Euro/5000h = 4Euro/h. The minimum wage (by law) is in Austria 6Euro/h. Obviously Go programming is even more unqualified than washing dishes in a restaurant. If it would be really a big challenge, there would be some money. In chess nowadays there is also no money. But once it was a good business and there was some considerable money for Deep Blue and on a smaller scale also for Hydra, there was Don's project at MIT, one got a big Cray for Cray-Blitz, Ken Thompson build a chess engine Its like some hobbyst engineers and hobby-pilots would try to fly to the moon. Its probably only good for to write some academic papers. In this case its even an advantage that everything is so amateuristic. The general level is low and one can be the one-eyed king under blind ones. Its clear to me that things are as they are in the West. Go is played only by a small freak community. But if it is so important in China/Korea/Japan why is'nt there something like Fritz and ChessBase? Or does it exist and we are living in a completly other Go-world? Chrilly P.S.: I do not want to offend anyone in this list. Everybody here does his best. I am just feed up with the things as they are. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 games wanted and the next big challenge
3) seriousness can't be measured as the short term money you can make directly selling your work. I understand that you think that researchers are paid just to play writing useless papers for themself. But there are not more stupid than others, and maybe they think they are doing something useful, even if it can't be measured by the direct sell of what they produce. I think UCT is an major new idea. Like Alpha-Beta. I am not at all against scientific work or papers. I have myself written some of them and even succeeded to place one in the Journal of the American Statistical Association. And I also understand, that everybody has to present his work as very important. Otherwise other people who are better in this respect get the funds. And one can do only a good work, if one really believes in this. A classical quote from the German scientist Max Weber is: To be a good scientist one has to write every sentence as if the existence of the world depends on this sentence. (Although one of course knows that this is usually not the case). But science, the science world, is also a very closed world and there is a tendency for l'art pour l'art. I am just critizing this aspect. Chrilly ___ 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
It seems to me that a domain where everything is so amateuristic has its advantages, if you can only see them. Here is a field that is small enough that most people know each other and anyone can contribute with a certain amount of effort. These are the early days; computer go's best years are surely yet to come. And yet it is not so early that progress is slow and there is little hope. Isn't that better than working in an area where everything has been done? Yes. The original meaning of amateur is lover. E.g. I enjoyed the athmosphere when I was operating GoAhead in the olympiad 2003. Its also known that humans generally evaluate/feel the difference and not the absolute level. So its nicer to be in the non-saturated point. But as professional its a job and one can not completly ignore mundane tasks like the Euro/h. The formula: There is money for everything what is important, and if there is no money, it is not important, is certainly also wrong. A counter-example is the research for Leprosy-medicaments. They ones who have Leprosy have no money and there is no incentive for the pharma-companies to invest. But also academic institutions do almost no research. There are no funds from industry. I don't follow computer chess, but my naive outsider's perception is that it is largely solved. Perhaps those who know more about it can say more. Its not solved in the theoretical sense. God could certainly give them 2 pawns as handicap. But it is solved from the practical sense, because God could give the top-humans a knight ahead. The only way to measure the difference between Rybka and Fritz is to let them play against each other. Just looking on the play of each of them or playing against them, most humans would not be able to say: Rybka is 100 Elo stronger. Even Topalov does not play nowadays for fun in the evening some blitz-games against a programm. Although he likes challenges, he neither runs with his head against the wall in his living room to check who is stronger. Most of the top-GMs hate the programms, because the size of opening theory has become a nightmare. Some opening lines are practically fully analysed and hence not playable anymore. I know some top players who would like to ban computers for preperation. But its impossible to check such a ban. Chrilly . , so also these GMs use very heavily PCs. - Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Explanation to MoGo paper wanted. (BackGammonCode)
Thanks, the dictionary is really great. Chrilly - Original Message - From: David Silver To: computer-go@computer-go.org Sent: Tuesday, July 03, 2007 11:29 PM Subject: [computer-go] Re: Explanation to MoGo paper wanted. (BackGammonCode) It's because Go is not only game in the world and certainly not only reinforcement learning problem. They are using a widely accepted terminology. But a very inappropriate one. I have read Suttons book and all the things I know (e.g. TD-Gammon) are completly obfuscated. Its maybe suitable to present generel concepts, but it is extremly complicated to formulate an algorithm in this framework. Here is quick and dirty RL-Computer Go translation kit to try and help bridge the gap! RL terminology Go terminology State Position Action Move Reward Win/Loss Return Win/Loss Episode Game Time-step One move Agent Program Value function Evaluation function Policy Player Default policy Simulation player Uniform random policy Light simulation player Other stochastic policy Heavy simulation player Greedy policy 1-ply search player Epsilon-greedy policy 1-ply search player with some random moves FeatureFactor used for position evaluation Weight Weight of each factor in evaluation function Tabular representation One weight for each complete position Partial tabular UCT tree representation State abstraction One weight for many positions Linear value function Evaluation function approximation using weighted sum of various factors Feature discovery Learning new factors for the evaluation function Sample-based search Simulation (Monte-Carlo methods, etc.) Transition function Rules of the game Environment Rules of the game + opponent Trajectory Move sequence Online During actual play Offline Before/after actual play (e.g. preprocessing) On-policy If both players play as normal Off-policy If either player behaves differently -Dave -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Explanation to MoGo paper wanted.
Hello all, We just presented our paper describing MoGo's improvements at ICML, and we thought we would pass on some of the feedback and corrections we have received. (http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf) I have the feeling that the paper is important, but it is completly obfuscated by the strange reinforcement learning notation and jargon. Can anyone explain it in Go-programming words? Is the RLOG Evaluation function used for evaluation or for just selecting the best move? (by doing a 1 Ply search). Can anyone explain me, why it is necessary to obfuscate things at all? Why is a move an action and not just a move, a game an episode and not a game? Is it less scientific if coders than myself can understand it? It was pointed out by Donald Knuth in his paper on Alpha-Beta, that the - simple - algorithm was not understood for a long time, because of the inappropriate mathematical notation. For recursive functions, (pseudo-)code is much better suited than the mathematical notation. Actually its pseudo-mathematic notation. Why is this inappropriate notation still used? I have build just for fun a simple BackGammon engine. I think it does what the paper proposses for the Monte-Carlo-Part. It uses a simple evaluation function to select the next move in the Rollout aka Monte-Carlo simulation. The engine does not build up an UCT-tree. It uses UCT only at the root. The rollout always starts at the first ply. The 1ply engine has not the slightest chance against sophisticated BackGammon programm. But the simple minded UCT version is already a serious opponent. By build up an UCT tree one could probably reach top Backgammon level (the effort to do this does not pay. The backgammon market is saturated). The simple engine behaves in a give position and dieces deterministic. But the roll of the dices generates sufficient randomnes. Chrilly ___ 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.
I have build just for fun a simple BackGammon engine. [...] Interesting - did you also try it for chess, or do you think there's no point in this? The Hydra team has thought about this. Especially the Hydra chess expert GM Lutz. Some endgames are difficult to understand, but the moves are more or less forced. One could play down the line and evaluate once a clear position has been reached. One problem is the definition of clear positon. The even more difficult problem is how to incorporate this in a normal Alpha-Beta framework. How to mix the result of the normal eval with the rollout. The results in Go are spectacular, because the quality of conventional evaluations is low. In chess its at least not that bad. But one could argue, that in BackGammon the quality of the eval is even higher. The simple Rollout programm is not as strong as the best ones. But it is in relation to its eval very strong. It has also a remarkable programming-effort/playing-strength ratio. These things are also done in FPGA and the FPGA code is already much too complicated. FPGA-programming is easier than ASIC-design, but its still much more cumbersome than conventional software development. Just trying out things is not possible. We felt also, that even if it works, the improvement measured in Elos would not be very spectacular. The Elo/Effort ratio is low. I was simply too lazy (or too professional) to give it a try. Chrilly ___ 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.
The most important thing in the paper is how to combine RAVE(AMAF) information with normal UCT. Like this: uct_value = child-GetUctValue(); rave_value = child-GetRaveValue(); beta = sqrt(K / (3 * node-visits + K)); uct_rave = beta * rave_value + (1 - beta) * uct_value; Thanks for the translation. The only point I am still missing: What is RAVE(AMAF)? Chrilly ___ 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.
We felt also, that even if it works, the improvement measured in Elos would not be very spectacular. The Elo/Effort ratio is low. I was simply too lazy (or too professional) to give it a try. it might be fun (even from a non-FPGA point of view) to try it just to see where it lies versus a convential piece of code on equivalent hardware. the game length is roughly the same, or smaller, and the number of move choices is quite a bit more limited than a 19x19 go board, (although larger than a 9x9 board in the sense that in the endgame the board is often fairly empty rather than full) so it might be surprisingly successful. Backgammon has the big advantage, that the dices generate the randomness. Its not fully clear how to do this in chess. GM Lutz had more forced variations in mind. Its another matter who to determine forcedness. Inspite all the nasty details the idea sounds interesting. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Explanation to MoGo paper wanted.
2. We want other communities to find out about UCT, and start using it many different domains. It is not just a Go-programming algorithm! Yes. I think the idea has many potential fields of application. In the samewhat dated book R.Epstein: The of Gambling and Statistical Logic the simple algorithm Play an arm as long as he is winning is proposed. But does not help too much. E.g. J.Schaeffer invented the History-Heuristik. This was long before jump-prediction become an important topic in microprocessor design. The first jump-predictions where static rules. After some years the hardware-designers invented then their own history-heuristic for jumps. ideas: http://www.cs.ualberta.ca/~silver/research/presentations/files/sylvain-silver.pdf Thanks. Actually I think the best notation would be: description in plain text + mathematical notation + pseudocode + many diagrams. But in a conference paper we have just 8 pages to describe everything, so we must make some compromises. Yes, I fully agree. Why do you call this UCT if there is no tree? Isn't this just roll-out simulation, as used by Tesauro and Galperin in 1996? Its the selection rule for making the rollouts at the root. This is a variant of UCT. Exactly its the multiarmed-bandit selection rule. It differs e.g from the rule proposed by Epstein. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Explanation to MoGo paper wanted. (BackGammonCode)
Isn't there room for both? Shouldn't we present our work within our own community, but also make efforts to share our ideas with others? Yes, I do this by writing popular articles about computer-chess and games programming. The point of concern is: One is only considered important if one considers ones one work as important. Sometimes I have the feeling that academic researchers are a little bit ashamed that they do not do something more serious, important. And they hide then their work behind a more serious title/topic and vocabulary. E.g. J. Schaeffer Donsky wrote Falling from Grace. Both made important contributions to computer-chess. But in this article they blamed themself, that its their own (and the communities) fault that they have fallen from AI-Grace. But isn't it the problem of AI when the concepts do not work? Why didn't they wrote an article The concepts of AI are bullshit? Feng Hsu was the first one who did this. He was proud enough about his work. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Explanation to MoGo paper wanted.(BackGammonCode)
the language of mathematics is perhaps the most universal language for computer scientists. pseudocode comes in somewhere after that, and well-known algorithms probably somewhere inbetween. game programming is an application of computer science, and the language of game programming isn't necessarily appropriate (and would seem obtuse) to the much larger audience of potential readers outside of its domain. whenever an algorithm is applicable outside of the game programming field, rephrasing its game-specific language might make the most sense to the readers who are intended to read about it. that having been said, the most appropriate language is obviously that which is understandable by the largest number of potential readers interested in the title and (if there is one) the abstract. s. I have a PhD in Mathematical statistics. So I am not at all against the use of Mathematics. I think the language should be choosen which is most appropriate. For some mathematical proofs about the Big-O behaviour of algorithms there is no other language than mathematics. But for describing algorithms this notation is not suited. D.Knuth choose in the Art of Computer Programming structured English and for a precise analysis MIX. His argument for MIX is, that he writes books for eternity. Therefore he can not use the latest fashion in programming language. There is some reason behind this argument, but I think that only a few programmers can read nowadays MIX. MIX does also not reveflect the capabilities of modern hardware. Knuth has therefore to rewrite his books in MMIX (Inschallah). Maybe pseudo-Algol would have been more ethernal than MIX. But in any case he uses different levels of notation. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Interviews of Participants in the Computer Olympiadon YouTube.
Here are some interviews from the Computer Olympiad in Amsterdam: http://www.youtube.com/results?search_query=computer+olympiade+amsterdamsearch= In 1981 there was a game of Belle against GM Donner in Delft. Donner wrote an article about this event. He makes very bad remarks about the man, who had the big mouth there, but is in fact unable - and will be ever unable - to produce something of any relevance. The times have obviously not changed, as far as I see on the link, the man has also in this event the big mouth. The only contribution I ever recognized from him was to bother the participants with his incompetence. David Levy is keen on Sachertorte. In the Bilbao 2005 I promised him a Sachertorte if he is able to stop the man from making one of his infamous speeches. Fortunately David does everything to get a Sachertorte and he indeed succeeded in this mission impossible. The most strange of these speeches was on the funeral of Jan Louwman. Instead of making a funeral speech, the man presented 10 theses about computer chess and of course that he - the man - was always right. There must be something wrong with the Dutch academic system if such a man can get 2 professorships. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Yet another article
MessageThe translation is not completly stupid (for an automatic translator). But its funny that it tries to translate English parts like the title of the first Chiptest/Deep Blue paper and mangles this completly. It fails to translate Austrian. E.g. bisserl (a little bit, ein wenig in German). These are the parts the German editors of my writings also want to translate to German. But on the same time it shows that the translator misses any minimal context knowlegde. E.g. Checkers is called in German Dame, which means also Lady. Lady is statistically the better guess, but in this context the lady programm Chinnok is of course completly stupid. The most funny translation is Fuer Fritz Programmierer Frans Morsch to For Fritz programmers fray to rotten. morsch means in German indeed rotten. But Frans is no valid word. As the name is written in uppercase the translation programm should have known that it can not mean rotten. I know no German language construct where one can write morsch in uppercase (besides at the beginning of a sentence). But upper/lowercase rules are in German extremly complicated. Constructs like Fritz Programmierer Frans Morsch are typical for my writing style. According my wife (she has studied linquistics) its a bad habit and not real German. The translator expected therefore some verbs. I do not now why Ed Schroeder is made to OD. Ed is also no German word. What does OD mean? Bayesion pattern matching is also tried in Go. I think the results are similar. There are some meaningfull game fragments reproduced, but overall it lacks any higher meaning. The approach also fails when the player deviates either on purpose (like in bisserl) or because he has learned bad style (e.g. Fritz Programmer Frans Morsch). Chrilly - Original Message - From: David Fotland To: 'computer-go' Sent: Saturday, May 26, 2007 6:55 PM Subject: RE: [computer-go] Yet another article I threw it at Google translation, which is supposed to be the best machine translator available now, using only Bayesian statistics with no knowledge. It mangles it, but the meaning comes through. It sounds like an interesting article. It would be nice to have a good translation. David Drosophila's luck and end God regarded everything, which it had made: It was very good. It became evening and it became morning: the sixth day. Towards. 1,31 If I intend a larger financial transaction, I ask a friendly economist over the prevailing opinion to this topic. Then I with some security, like it does not become white and does not depend on it. In my Profession is still simpler the thing. The prognoses John McCarthy's and its AI-young form an entropy set. The area of the hopeless solutions. Stanley Kubrick' s HAL and my Windows PCs have only one together: Sometimes goes nothing at all more. 1989 published J. Schaeffer and M.Donskoy Perspectives on Falling from Grace. The Confessiones of two successful academic chess programmer. One betrayed the holy goal of the computer Drosophila by the longing of the tournament victory. Schaeffers Bekehrungserlebnis was a bitter defeat against chip test. It became again backdue however with the lady program Chinnook. 1989 I worked in the European space Technology Centre in Noordwijk/NL. In the damp and cold winter evenings I felt lonely and had homesickness. Around this feeling to betäuben I bought the Mephisto Polgar Brettcomputer of OD Schroeder. Playing against helped also nothing and seized I one evening the resolution in such a way: I can bisserl games of chess, I can program, why I do not make a chess program? The goal was, a PC program, which can take up it with that. I had increased thereby the drug, became sufficient depressing drums of the rain the pleasant mood music. However I suffer until today from heavy craze features. Of the McCarthy' Drosophila did not have I the smallest rope, McCarthy was me only as a creator of its own programming language a vague term. It would have been also perfectly all the same me: My goal was to betäuben and strike homesickness. 1989 rank among the sieved fat years of computer chess. OD Schroeder lives this very day of the pole percentages of profits. 1989 defeated chip test the first large masters. The first article over this program carried the title by program for Designing A single chip Grandmaster while knowing emergency-hung about chess . Chip test attained as Deep Blue world fame. John McCarthy, which had formulated the victory over the chess world champion once as warming up exercise for the actual tasks of the AI, reacted in a book review in Science to Deep Blues summit victory säuerlich. Three feature OF of human chess play acres required by computers programs when they face of harder problems than chess. Two OF them were used by early chess programs but were abandoned in substituting computers power for thought. 1) Human chess players CAN emergency examine all
Re: [computer-go] KO in Hashtable-UCT?
I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly So does your hash function consider all previous board states (for superKo)? If so, how? I can think of one way, but I don't use it since I have a tree that handles the allowable moves independent of the hashtable. When going down a variation the Hash and other Board-State Information like e.g. the KO-Point are stored on a stack. Starting from the current Top of Stack the detection goes down and search for the same hash-key and Ko-Point. Its the Repeated Position Detection method of chess. The Gamestack-Pointer is decremented by 2, one can stop, when a non-capturing move is done (in chess its the other way round). One can start 4 Plies from the top of stack. Due to the stoping criterion one has to check only a few entries (most of the time none). If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. Probably a better way is to ignore the result. But I assumed that SuperKO is a rare event and the result has no significant impact on the search-tree. Maybe there is something wrong with this approach and the Ko-Problems I have a related to this simple SuperKO handling. I noticed several times that a direct transformation of chess methods has some subtle flaws. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
Non-capturing moves can create repetition (but there will of course be captures elsewhere in the cycle). So far the SuperKOs I have found where a round-trip of KOs. Fortunately, there are other simple criteria. E.g., you can stop whenever a move is played on an intersection for the first time. Okay. If a SuperKO occurs, the position is evaluated by the Material-Balance. BlackCaptures - WhiteCaptures + Komi. I guess you mean the *change* in material balance after one cycle. I don't see why komi should be used here. No. I assume the game is over. As there is usually no reliable method for counting territory I use the difference of the captured stones as a - first approximation - for the evaluation. If e.g. both sides have captured - in the whole game - the same amount of stones, the eval is 0, but white wins due to Komi. At least for significant differences in captures this is true. MC-Runs are also stopped, when one sides leads in Capture by a large margin. Depending on the margin it produces only a negible bias. Only for balanced cycles. The cycles I have found so far are balanced. Each side captures in turn 1 stone. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
I have now also finished a first version of UCT-Suzie (in parallel the Peter Woitke works on the Alpha-Beta Version). UCT-Suzie uses a hashtable, mainly because I found the programming of the tree too complicated. The Monte-Carlo part uses some simple patterns according the MoGo article. Progress is rather slow, because I am working (more than) full-time on FPGA-projects in Computer-Tomography. Here are the problems with hash tables as a tree: 1. Time - it is more expensive - you must gather the children together when making decisions about which node to expand (which generally involves re-generating the keys by making all the legal moves.) There are ways around this that trade space for time but in either case it is more expensive. I do not understand this. In UCT-Suzie the moves are generated, when a new leaf-node is reached. The Hashtable has a link to the move-list. When the node is reached the next time, the moves must not be generated again. Just the calculation of the UCT-Urgency value (WinRate + sqrt() ) has to be done. I assume that this calculation has to be done also in a tree representation. I see no difference in this respect with Gunnars Gnu-GO UCT code. Memory is at least for 9x9 no problem. The number of Monte-Carlo runs/sec. is about 17K (9x9). This can be improved, because the UCT-Player uses the Alpha-Beta DoMove/UndoMove functions which are overkill for UCT. 2. GHI - you must take special care to deal with Graph History Interaction - primarly recognizing that ko situations are different. You can get by with relatively simple solutions that don't fully address this issue but it's still imperfect. I have serious problems with KO. UCT-Suzie plays generally strong, but makes terrible blunders in KO-positions. So far I do not even understand the problem. Could you describe it more detailed? I had also some serious SuperKO problems. UCT-Suzie was very clever to find SuperKOs. We do not check for SuperKO in Alpha-Beta. The search is not deep enough. Ignoring SuperKO in UCT is for a Hashtable version deadly. GameStack-Overflow. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kirtag
I am working now in Germany and just read this - for me - very interesting information. Robert Sedlaczek is a very Austrian name. Its Czech. A lot of Austrians in the Vienna region have Czech or Hungarian names and one of the differences of Austrian-German and German-German is the use of original Czech, Hungarion and Jiidish words. Chrilly - Original Message - From: Nick Wedd [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, May 02, 2007 11:20 AM Subject: [computer-go] Kirtag Some months ago, someone here (I think it was Chrilly) used the Austrian expression Kirtag, and wondered how to express it in standard German. I now have an answer. Robert Sedlaczek wrote to me: quotation starts This is an easy one: Kirtag is in austria the word for an annual parish fair commemorating the inauguation of a church, in german it is Kirmes oder Kirchweih. It is nowadays often combined with a temporary amusement park including . You find Kirmes in: http://dict.leo.org/ende?lp=endelang=desearchLoc=-1cmpType=relaxedsec tHdr=onspellToler=onsearch=parish+fairrelink=on And this is the explanation in Duden, Das große Wörterbuch der deutschen Sprache: Kirch|weih, die; -, -en [vgl. Kirchweihe]: [jährlich gefeiertes] Fest [auf dem Land] mit Jahrmarkt u. anderen Vergnügungen, das zur Erinnerung an die Einweihung der Kirche gefeiert wird: © 2000 Dudenverlag Man kann nur auf einem Kirtag tanzen means: You cannot be everywhere; also: you are involved in too many (conflicting) business affairs. You can also say: Er tanzt auf allen Kirtagen: He is a Jack of all trades. In Germany they say: Er tanzt auf jeder Kirchweih: You can find him everywhere. In my book Das österreichische Deutsch you can read about Kirtag: Ö: Kir(ch)tag, Kirchweih, Dult D: Kirchweih, Kirmes Die Wörter „Kir(ch)tag“, „Kirchweih“ und „Kirmes“ sind bedeutungsverwandt. Ursprünglich hat man damit das „Fest der Kirchweihe“, dann das „Erinnerungsfest an die Einweihung der Kirche“ und schließlich „Fest, Jahrmarkt“ ganz allgemein bezeichnet. Die Wörter „Kir(ch)tag“ und „Kirchweih“ sind vor allem in Österreich und Bayern gebräuchlich, der Ausdruck „Kirmes“ ganz im Westen Deutschlands. In Oberösterreich, Salzburg und Bayern wird außerdem der Begriff „die Dult“ (= Fest, Jahrmarkt) verwendet. „Kir(ch)tag“ geht zurück auf mittelhochdeutsch kirchtac. Das Wort ist im österreichisch-bayerischen Raum entstanden. „Kirchweih“ ist im Althochdeutschen als kirihwîha belegt. „Kirmes“ geht zurück auf mittelhochdeutsch kir(ch)messe (= Gottesdienst an „Kirchweih“). Vermutlich handelt es sich um eine Kurzform von „Kirchweihmesse“. Das Wort „Dult“ ist im Althochdeutschen als tuldî belegt. Es ist vergleichbar mit gotisch dulps (= Fest). Herkunftswort könnte ein gotischer Ausdruck für „in Ruhe verharren = Feiertag“ sein. Der österreichische Sprachforcher Eberhard Kranzmayer weist darauf hin, dass „Kirchweih“ ursprünglich nur der Name für die kirchliche Feier des Patroziniums war. „Kirchtag“ war wiederum ursprünglich nur der Termin für diese Feier. Im österreichisch-bayerischen Raum wurde dann das Wort „Kirchtag“ verallgemeinernd auch für das Weihefest verwendet. Im Alemannischen und im Ostfränkischen kam es zu einer umgekehrten Entwicklung. Dort wird das Wort „Kirchweih“ schließlich auch für den Termin verwendet. Die Redensart „auf zwei/vielen Kirtagen tanzen“ bedeutet „überall dabei sein wollen“. – „Mit einem Arsch auf neun/zehn Kirtagen sein“ heißt „überall dabei sein“. Literatur: Popowitsch/Voc., 1. Band, S. 303 f.; Ebner, 1998, S. 175 f.; Eichhoff, 1977 ff., 1. Band, S. 31 f., Karte 44; Eberhard Kranzmayer: „Die bairischen Kennwörter und ihre Geschichte“, Wien 1960, S. 12; Kluge, 1995, S. 443 und S. 198. Is there a similar phrase in English? Robert quotation ends Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Thanks Chrilly. For anyone else interested, it is here: http://www.xilinx.com/publications/xcellonline/xcell_53/xc_pdf/xc_hydra53.pdf But, as you say, the the search tree as an adaptable error filteridea is only mentioned in passing. I guess I'll just have to wait for Ulf Lorenz to translate his Dissertation into English :-). Or you learn German. As I side effect you can than also read Goethe and my chess columns. The chess columns are interesting, but then you have to learn also the Austrian version of German). Ulf has used this model for a project to improve the robustness of airplane-schedules. ... Interesting. It is always motivating to hear about game theory getting applied to the real world. (And having been stuck in Amsterdam airport for 5 hours because KLM forgot to schedule a pilot for my flight, I think the airline industry needs all the help it can get!) The problem is, that there is no economic incentive. A robust solution is usually somewhat worse than the non-robust one. I assume that you did not get any compensation for the 5 hours in Schiphol. Such methods will only become important, if KLM has to pay you. 50 Euro/h. The scheduling was done before by humans. These schedules have been robust. Simply for the fact that it is too complicated for a human to make an optimal schedule. But also because humans have some feeling what can go wrong and they anticipate the most likely delays. To a certain degree computer-optimization was introduced to make the schedules less robust. But you have also choosen a very poor airline. KLM was fine a few years agos, but then they started to save money and now its notorious for being late, loosing baggage. But as the other lines have gone the same way, it makes no big difference. There a few good lines left. I my experience the best one is Emirates from Dubai. You should give it a try the next time. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Noise reduction in alpha-beta search
Ingo Althoeffer has published some time ago a theoretical article about this idea. He called it telescope evaluation. According his theorectical findings is the error propagation not better than the usual approach. K.Chen proposed a similar approach. Use the mean of the last and second-last evaluation. I tried this. It makes the search more stable. With the normal search we have strong odd/even effects. At odd depths Suzie evaluates the position (considerable) higher than at even depths. At odd depths Suzie has 1 move more in the variation than the opponent. This odd/even effect disappears with the K.Chen mean. Also the search depth increases, because move ordering is more stable. But the result in the autoplay-matches was worse. One gets effects like the following: 1 Ply before the horizon the opponent makes a threat. The evaluation goes down considerable, but there is a defense move and at the horizon nothing has happened.. But according the mean the programm is still in some trouble. Or if one reverses the role, Suzie would like to play the threat-move. This scheme increases therefore even the potential of the programm to cheat. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Monday, April 09, 2007 4:48 PM Subject: [computer-go] Noise reduction in alpha-beta search I think following is a way to reduce the noise in alpha-beta search. Instead of using the evaluation values, use the cummulative evaluation values. That is the sum of the evaluation values of each node of the playing path under examination. Daniel Liu -- AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Noise reduction in alpha-beta search
It can't be. He was probably studying the general game, not Go Ingo Althoefer published his results in the context of chess. Alpha-Beta Search was until recently not a topic in Go (besides its not possible). The score in Go is additive, if the score is territory. But that is not a possible evaluation function. E.g. in the first stages only on small parts of the board is white/black territory defined. The rest is influence/Moyo (or nothing). One needs also some notion of weakness of a group. The All or Nothing (Group is Living or Death) approach does not work. There must be some evaluations/stages in between. If a weak group controls some territory, this territory should also count less... This problem is to be solved by deeper search. Yes. But it is very difficult to find reasonable quiet criterions. One has to stop the search at one point, because otherwise it explodes. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tuesday, April 10, 2007 5:23 PM Subject: Re: [computer-go] Noise reduction in alpha-beta search It can't be. He was probably studying the general game, not Go. The score in Go is additive, if the score is territory. 2-steps approach make some sense, but not in general situation. At each step the pendlum swings to one side is the nature of the game. Nothing wrong with it. One gets the same problem with single step evaluation too. This problem is to be solved by deeper search. Daniel Liu -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Tue, 10 Apr 2007 1:46 AM Subject: Re: [computer-go] Noise reduction in alpha-beta search Ingo Althoeffer has published some time ago a theoretical article about this idea. He called it telescope evaluation. According his theorectical findings is the error propagation not better than the usual approach. Chrilly - Original Message - From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Monday, April 09, 2007 4:48 PM Subject: [computer-go] Noise reduction in alpha-beta search I think following is a way to reduce the noise in alpha-beta search. Instead of using the evaluation values, use the cummulative evaluation values. That is the sum of the evaluation values of each node of the playing path under examination. Daniel Liu AOL now offers free email to everyone. Find out more about what's free from AOL at AOL.com. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] LISP question (littlle bit off topic)
Paper 1 in the list below states: Numbers were originally implemented in Lisp I as a list of atoms. and the Lisp 1.5 manual states: Arithmetic in Lisp 1.5 is new Could you give an example how the number 3 was implemented in Lisp-1 and how 2+1? So far I have found only this remarks but not programming examples. It would be much more instructive for my article if I could quote these examples. Chrilly - Original Message - From: Ron Goldman [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Cc: Chrilly [EMAIL PROTECTED] Sent: Sunday, April 08, 2007 2:23 AM Subject: Re: [computer-go] LISP question (littlle bit off topic) Crilly, I used to program in LISP and had never heard of this, so I did some checking. I think this is a misconception from the fact that numbers were considered atoms and hence stored on the list of atoms. Instead of just being a numeric value they consisted of an association list (e.g. a list of atoms) containing a tag to indicate the value was a number and another word with the value. The LISP I Programmers Manual [1] gives an example: -1 = (MINUS . (ASSOC NUMB FLO (1.0))) (In fact LISP I (1960) only supported floating-point numbers, LISP 1.5 (1961) supported both integers floats. [2]) As a result of storing values in an association list arithmetic routines had to do several memory references to obtain the numeric value. In a paper on the History of Lisp John McCarthy [3] discussed this writing that Numbers were originally implemented in LISP I as lists of atoms, and this proved too slow for all but the simplest computations. A reasonably efficient implementation of numbers as atoms in S-expressions as made in LISP 1.5, but in all the early LISPs, numerical computations were still 10 to 100 times slower than in FORTRAN. Later versions of LISP [4] used better tagging schemes for numbers and were able to produce compiled code that was as fast (or faster) then C or FORTRAN. Finally LISP early on had bignums to compute using arbitrary- precision integers (similar to Java's BigInteger). Useful if you needed to compute factorial of 1000 exactly. -- Ron -- 1. http://community.computerhistory.org/scc/projects/LISP/book/LISP% 20I%20Programmers%20Manual.pdf 2. ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-024.pdf 3. http://www-formal.stanford.edu/jmc/history/lisp.ps 4. http://doi.acm.org/10.1145/1086803.1086804 On Apr 7, 2007, at 12:54 PM, Chrilly wrote: Up to my knowledge the first Lisp Versions had no number system. The number n was represented as the list of numbers from 1 to n (which is also the mathematical/axiomatic definition of the natural numbers). But its not very practical. Can anyone provide me with a link how this was done. I am speaking some computer languages, but Lisp is not among them. I want to present the code in an article for the Austrian AI- Journal (as an example that mathematical elegance and practically usefull are 2 different things). Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
According these results the slope is considerable greater than in chess. In the classical experiment of Ken Thompons searching 1 ply deeper is worth about 200 Elo. 1 ply corresponds to 5-6 times longer/faster. In 9x9 already a factor of 2 gives the same improvement. This is really remarkable. Another explanation would be, that 100 Elo have in Go a different meaning than in chess. It is often argued that the distance between week and stronger player is much greater in Go than in Chess. In chess the distance between an average club player and top humans is about 1000 Elo. Maybe in Go its 2000 Elo?? In chess the green level-11 version would have world-champion level. Is it just enough to make a 2 million playouts version to beat the top-Dans in 9x9? Is it that easy? Just build a special purpose chip like ChipTest aka Deep Blue. Or implement it on a cluster. Or just wait a few years on do it on the PC. Or a playstation. Chrilly Is there any notion of the Elo rating of a professional Go player. In chess terms the - Original Message - From: Don Dailey [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, April 08, 2007 3:05 AM Subject: [computer-go] The physics of Go playing strength. A few weeks ago I announced that I was doing a long term scalability study with computer go on 9x9 boards. I have constructed a graph of the results so far: http://greencheeks.homelinux.org:8015/~drd/public/study.jpg Although I am still collecting data, I feel that I have enough samples to report some results - although I will continue to collect samples for a while. This study is designed to measure the improvement in strength that can be expected with each doubling of computer resources. I'm actually testing 2 programs - both of them UCT style go programs, but one of those programs does uniformly random play-outs and the other much stronger one is similar to Mogo, as documented in one of their papers. Dave Hillis coined the terminolgoy I will be using, light play-outs vs heavy play-outs. For the study I'm using 12 versions of each program. The weakest version starts with 1024 play-outs in order to produce a move. The next version doubles this to 2048 play-outs, and so on until the 12th version which does 2 million (2,097,152) playouts. This is a substantial study which has taken weeks so far to get to this point. Many of the faster programs have played close to 250 games, but the highest levels have only played about 80 games so far. The scheduling algorithm is very similar to the one used by CGOS. An attempt is made not to waste a lot of time playing seriously mis-matched opponents. The games were rated and the results graphed. You can see the result of the graph here (which I also included near the top of this message): http://greencheeks.homelinux.org:8015/~drd/public/study.jpg The x-axis is the number of doublings starting with 1024 play-outs and the y-axis is the ELO rating. The public domain program GnuGo version 3.7.9 was assigned the rating 2000 as a reference point. On CGOS, this program has acheived 1801, so in CGOS terms all the ratings are about 200 points optimistic. Feel free to interpret the data any way you please, but here are my own observations: 1. Scalability is almost linear with each doubling. 2. But there appears to be a very gradual fall-off with time - which is what one would expect (ELO improvements cannot be infinite so they must be approaching some limit.) 3. The heavy-playout version scales at least as well, if not better, than the light play-out version. (You can see the rating gap between them gradually increase with the number of play-outs.) 4. The curve is still steep at 2 million play-outs, this is convincing empirical evidence that there are a few hundred ELO points worth of improvement possible beyond this. 5. GnuGo 3.7.9 is not competive with the higher levels of Lazarus. However, what the study doesn't show is that Lazarus needs 2X more thinking time to play equal to GnuGo 3.7.9. This graph explains why I feel that absolute playing strength is a poor conceptual model of how humans or computers play go. If Lazarus was running on the old Z-80 processors of a few decades ago, it would be veiewed as an incredibly weak program, but running on a supercomputer it's a very strong program. But in either case it's the SAME program. The difference is NOT the amount of work each system is capable of, it's just that one takes longer to accomplish a given amount of work. It's much like the relationships between power, work, force, time etc. in physics. Based on this type of analysis and the physics analogy, GnuGo 3.7.9 is a stronger program than Lazarus (even at 9x9 go). Lazarus requires about 2X more time to equalize. So Lazarus plays with less force (if you use the physics analogy) and needs more TIME to get the same amount of work done. ELO
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I have this idea that perhaps a good evaluation function could replace the play-out portion of the UCT programs. The evaluation function would return a value between 0 and 1 and would be an estimate of the odds of winning. I have tried this with an older and much weaker version of Suzie. It played positionally better than the Alpha-Beta version, but the rate of very strange moves also increased. UCT greates a more unbalanced tree than Alpha-Beta and the programm has therefore even more chances to cheat. For the same reason extensions do not work so far in Suzie. But I tried not with 0-1 but used the full eval. Maybe I should give it a second try. But as I work now 45 hours/week on Computer-Tomography (which is also quite interesting) and comute each weekend between Germany and Austria its difficult to do. Chrilly ___ 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)
I don't understand your question. I don't claim non-determinism helps with alpha beta and I'm not recommending a fuzzy evaluation function, I'm just saying it still works. A deeper search will produce better moves in general. One has the randomness anyway. A heuristic evalution can be considered as the sum of a systematic term which is an estimator of the true evaluation and an error term (and a bias). One consequence of this model is, that the shape of the search tree has a significant influence on the evaluation. The programm will favour variations where it has a lot of good moves and the opponent has only a few. Because the more (good) moves the program has, the higher is the expected value of the error terms. The programm has more tickets in the error-term lottery. I have noticed this effect constantly. E.g. if one extends captures, the programm tends to favour lines with captures, if one extends checks stronger, the program likes to check... Chrilly ___ 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)
There is a chapter in Ulf Lorenz Dissertation about this topic. Ulf mentions this aspect also in the Hydra papers. E.g. the one for the XCell Journal. Search on the net for Lorenz, Donninger, Hydra and format pdf. But in this papers the concept is only mentioned without a detailed proof/explanation. This is only done in the Diss. The title of the Diss. is: Ulf Lorenz: Controlled Conspiracy Number Search, Paderborn 2000. But the work is in German. After the match Adams-Hydra Ulf wrote a longer article about his error-filter theory for the ICGA-journal. But the article was rejected. Ulf has used this model for a project to improve the robustness of airplane-schedules. The current algorithms just optimize the scheduling of airplanes (and the crew), but they have usually no notation of robustness. If there is a delay in London, then the flight Frankfurt Paris might be delayed too, because according the schedule the airplane is used after the return from London in Frankfurt for the Paris fligth. And this can in turn delay the flight from Paris to Madrid, because the crew has now - according the law - to take a rest in Paris, but the scheduling programm calculated that its optimal that they are also on board for Paris-Madrid and take the rest in Madrid One can consider the time according schedule as a noisy evaluation function and can try to find more robust solutions which is not much worse than the best solution. Its a conspiracy approach for scheduling problems. Chrilly - Original Message - From: Darren Cook [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Saturday, April 07, 2007 2:18 AM Subject: Re: [computer-go] The dominance of search (Suzie v. GnuGo) (R==1). An incorrect pruning decission is not taken forever. The general idea is to use information from the search tree to shape the search tree. Ulf Lorenz from the Univ. Paderborn considers the search tree as an adaptable error filter. ... UCT and Monte Carlo. It's not as much Monte Carlo any longer. Yes, ecaxtly. I also think that the difference is fuzzy. Both methods fit into the adaptable error filter model of Ulf. Hi Chrilly, Do you have a recommendation for a good paper to read on this? Ideally one that doesn't need specialized chess knowledge to appreciate, but I may not have a choice: google is giving me 0 hits on adaptable error filter. Darren -- Darren Cook http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary) http://dcook.org/work/ (About me and my work) http://dcook.org/work/charts/ (My flash charting demos) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] LISP question (littlle bit off topic)
Up to my knowledge the first Lisp Versions had no number system. The number n was represented as the list of numbers from 1 to n (which is also the mathematical/axiomatic definition of the natural numbers). But its not very practical. Can anyone provide me with a link how this was done. I am speaking some computer languages, but Lisp is not among them. I want to present the code in an article for the Austrian AI-Journal (as an example that mathematical elegance and practically usefull are 2 different things). Chrilly ___ 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)
Thanks for your report. The question of UCT versus Alpha-Beta is not open any more in my opinion. The current state of the art of Monte Carlo tree search is about 500 Elo points stronger than the version of Crazy Stone you tested against. Do you believe you can easily catch up with those 500 Elo points ? Also, I am convinced that UCT has tremendous potential for further improvement. I have improved Crazy Stone by about 50 Elo points per day in the past 10 days (on 9x9. The improvement on 13x13 and 19x19 is much more). I am very confident that I can easily improve it further very much. Rémi The main point of my mail was: Search works (at least in 9x9) well. I think we can agree on this point. For the UCT v. Alpha-Beta question there is a simple proof of the pudding: Sent us the latest/strongest version and we will try to beat it. Suzie is so far a very propretiary system which runs only under GoAheads GUI. And GoAhead does not support GTP. GnuGo is run with a hack. The matches against Crazy-Stone are done by hand. Its Stefan Mertins version of watching TV. I am working currently on a modern C# based GUI which shall support also GTP. But progress is due to my engagement by Siemens rather slow***. Once this GUI exists we will be able to participate on KGS tournaments and other programmers could get Suzie if they like. *** I have also done almost nothing to improve the search, the main progress is due to Peters intensive work on the evaluation. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re:[computer-go] MoGo
One further important rule. One should never be ironic in interviews. The ironie is almost always lost. E.g. when we played against Adams the default question was why do you not play against Kasparov. I could not stand this question anymore and in a press conference shortly before the match I said Because Adams is the much stronger opponent. I got bad comments on this sentence.. Another rule is: Most journalists are writing almost all of the time about themselves and not about the topic at hand. If one is interested in a story, the easiest thing to get one is to invite the journalist and to cook for them. They can than write how they liked the eating. Which is already a story about themselves. Chrilly - Original Message - From: Sylvain Gelly To: [EMAIL PROTECTED] ; computer-go Sent: Wednesday, April 04, 2007 2:00 PM Subject: Re: Re:[computer-go] MoGo Thank you Don. I did not know that, I am not used to :-). Then I'll stop worrying for these kind of things and stop trying to give back the truth :). Bye, Sylvain 2007/4/4, Don Dailey [EMAIL PROTECTED]: On Wed, 2007-04-04 at 10:52 +0200, Sylvain Gelly wrote: You should also know that we never claimed that MoGo plays 9x9 go near the level of a professional go player, which is of course false, and even if it was true should ask for many many experiments, and we would have never say that. It doesn't surprise me. It's common to get misquoted. One thing that is even more common - at some point you are likely to make a quote that will live forever (and it can even be a misquote.)Someone will quote it, they will latch onto it, and others will cut and paste from the first author who quoted (or misquoted) you! - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [spam probable] Re: [computer-go] Gnugo vs commercial programs
I have such games. It was with a expermental version of Suzie, were Suzie played quite aggressive/over optimistic. Gnu-Go calculated very long, but won these games at the end completly When Suzie plays sound and wins or looses only be a small margin, Gnu-Go plays also with level 16 relative fast. I am currently in my private house in Austria, the games are on my computer in Germany (where I work currently during the week). I will send it on Monday. Chrilly - Original Message - From: Arend Bayer To: computer-go Sent: Saturday, January 20, 2007 11:09 PM Subject: Re: [spam probable] Re: [computer-go] Gnugo vs commercial programs Hi Sylvain, On 1/10/07, Sylvain Gelly [EMAIL PROTECTED] wrote: So between the default level (8) and the level 16, there are 7% winning difference at around 50%, which is significant, but do not change by far the results Hiroshi posted. It is far less than 100 ELO right? I did not measure the thinking time of GnuGo level 16, but it seems quite long, and some games (at least 1, I don't remember) never finish after a lot of hours. Perhaps it is just a bug :). So I think using GnuGo level 8 is reliable (and for experiments much faster). If you have (or anyone else has) examples of .sgf-files with such extra-ordinary long thinking times for a single move, I would be interested in seeing them. (Send them to me, to gnugo-devel-at-gnu.org, or attach them at http://trac.gnugo.org/gnugo/ticket/160.) My suspicion is that most of them are related to explosion of branching factors in the local reading of ko fights - due to various reasons these are not very well controlled in GNU Go. Arend -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Can Go be solved???... PLEASE help!
Another interesting question would be the score (eg. territorry) that black/white can reach assuming perfect play on both sides. If we knew that, a perfectly fair komi could be calculated. From what I know, even chess is still unsolved conserning this matter - noone knows if white (or even black) can force a win. eph Such a Komi would not be fairer than the current one. If a perfect player would win with 15 points. Should the komi be increased to 15 points, although humans can not realize this advantage and there would a much higher winning-rate for white? The most fair decisiion is that the Komi brings the winning chances in practical play as close to 50% as possible. One could compute the black advantage from a big games database and set then the Komi to the mean value. This is much simpler than solvint the game and also fairer than some theoretical limit which is irrelevant for human-human play. It would be interesting if the empirical Komi depends on the playing strength. I would assume,that the tempo of Black is worth more for strong players. But there is on the other side the law of the balance of stupity. Also white loosed due too his lack of skills tempo/sente and the net effect is for all playing levels the same. Monte-Carlo Go is based on this law. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
- Original Message - From: Jeff Nowakowski [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, January 11, 2007 3:37 PM Subject: Re: [computer-go] Gnugo vs commercial programs On Thu, 2007-01-11 at 07:40 -0500, Don Dailey wrote: Of course there is some questions about how long Moore's law will hold. If you are referring to CPU speed doubling (as opposed to transistor count), then that has been over for at least 5 years. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software http://www.gotw.ca/publications/concurrency-ddj.htm The problem is that concurrency doesn't scale well. -Jeff Yes, the INTEL engineers have long solved the problems of the programmers. But now the programmers have to solve the problems of the engineers. They do not know what to do with additional gates. The simplest way is to add another core. And if you have still too much gates left, make a quad core. The problem is that concurrency doesn't scale well. I think it depends on the application. In the simplest case, a server with many processes, it scales well. There are other applications like graphics were scaling is up to a certain limit relative straightforward. And there are still other applications like Alpha-Beta search which scale badly. Although up to 4 processors even Alpha-Beta scales well. In the Hydra FPGA there are also enough gates for a 2nd chess-core. But until now I have not succeeded to get a speedup with the second core. One very nasty limiting factor is the slow PCI bus. The Software side can not feed this cores fast enough (the CPU speed is sufficient, but bringing it over the bus is the problem). Another problem is Alpha-Beta itself. The FPGAs search with a fixed depth 4. If at Depth 4 nothing is to distribute, because the first move creates already a cutoff, the second core sits idle. The bus problem is a general one. E.g. modern graphic cards have a very powerfull GPU. One could use this e.g. for the computation of neural networks. The theoretic speedup is impressive, but the practical is low or it even slows down things. The neural-network-computation must - in comparision to the data - very large. Otherwise the transfer of data eats up all the speedup. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Allocating remaining time
How much time should a program spend on each move? I think this is one of the most important and also difficult questions in game programming. Much effort is done to speed up the node-count by 10%, but a good time control is a much more effective speedup. If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. One should at least use t/(m+1). There is also a locial reason for this. If m is very small, especially m==1 one should have some extra time if the programm recognizes a problem. In this case it should search deeper. Generally this t/(m+k) should only be a target time. The final decision should be based on the results of the search. It is important to recognize trivial/forced moves and to stop in this cases search earlier. If the programm sees a problem than it should search longer. I have made recently a simple (but strong) UCT backgammon programm. UCT gives much better information for time-control than Alpha-Beta. E.g. if almost all search effort is concentrated on the best move, one can reasonable conclude that its a trivial/forced move. If the eval of the best moves decreases in the last period constantly and there are some chances that the second best becomes best, one should search on In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) Go-Programmers like it complicated. It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? One should forget human behaviour. If I would have to make a Turing test - is the player human or a programm - I would not look at the moves but on the time behaviour. The fundamental difference is that (good) humans know when the position is difficult and when its easy. Programms have no understanding of this at all. Humans play Chess/Go, programm make chess/Go moves. Consequently humans think for a few moves very long, and play other moves rather fast. But I think that the time-control of humans is not at all optimal. Its very human to try to solve an urgent problem even at the risk that it makes solving a further problem more difficult. Humans tend therefore to get into Zeitnot. When playing against GM Adams I proposed 40 Moves in 2 hours. He proposed 40 Moves in 1 hour 40 minutes plus 30 sek/move. In the first moment I could not see the difference. In both cases one has 2 hours for 40 moves. But at move 30 its different. The flag is falling there already at 1h 55 minutes. Its a psychological trick to avoid extreme Zeitnot. But if the human would have a good time-control algorithm there is no need for this trick. He could save this 30 seks for himself. Chrilly Note: One should forget human behaviour generally. A programm is a programm is a programm. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Sho-Dan-level at 9x9
- Original Message - From: Sanghyeon Seo [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wednesday, January 03, 2007 10:04 AM Subject: Re: [computer-go] Sho-Dan-level at 9x9 2007/1/3, Chrilly [EMAIL PROTECTED]: As I told before I organized with Nimzo a jackpot bltiz system. When the jackpot reached 500 ATS (50 $) there was a queue of GMs who wanted to play. This was during the tournament and they had their own games running. They did not care about their own games anymore, the only wanted the jackpot. They are gambling-junkies. A lot of German GMs have now practically stopped serious chess and play on internet poker. That reminds me of Jimmy Cha. A professional go player (and strong!), at the same time world-class poker player. http://en.wikipedia.org/wiki/Jimmy_Cha There is another famous example in Backgammon. Paul Magriel x-22, world-champion and author of the classical backgammon introduction. http://en.wikipedia.org/wiki/Paul_Magriel Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Sho-Dan-level at 9x9
- Original Message - From: Nick Wedd [EMAIL PROTECTED] To: [EMAIL PROTECTED]; computer-go computer-go@computer-go.org Sent: Tuesday, January 02, 2007 11:47 AM Subject: Re: [computer-go] Sho-Dan-level at 9x9 In message [EMAIL PROTECTED], Don Dailey [EMAIL PROTECTED] writes Hi Chrilly, I find it pretty amazing that even a little money will inspire people to play a computer who wouldn't otherwise. Many years ago my old chess programs were welcome at tournaments, but as soon as players started losing, the program wore out it's welcome! The change was like night and day. We came to one tournament and almost everyone signed the refuse to play a computer list. So I offered 5 dollars for a draw and 10 dollars for a win. This tiny incentive caused almost all the players to agree to play the computer and in fact many players begged to play it. What was ironic, was that didn't pay out a single penny but everyone was happy! I don't think you understand how mean Go players are. Many of them have beards because they are too mean to pay for razors. Nick -- I thought that the Go and chess community is different. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Sho-Dan-level at 9x9
The Cotsen Open has a cash prize for the best computer program, which I felt somewhat guilty accepting after loosing all games due to the bug, but SlugGo was the only program entered this year, and the cash did help to offset the cost of renting the wheelchair van with hydraulic ramp that I needed to transport the cluster. Why does Slu-Go not play remote? E.g the only thing I transported to London for playing against GM Adams was a notebook. The Hydra-Cluster would have been a little bit difficult to transport. Even in Abu-Dhabi the operating is remote. The Hydra-Sheikh sits in his palace and the Cluster is in another part of the town. Its for the chess-engine completly transparent. The engine writes/reads to stdout/stdin. If the GUI is on the same PC, the communication is directly done. When playing remote SSH (Secure Shell) is started and the rest goes as before. Chrilly P.S.: There are some chances that not only Hydra but also Mona Lisa will be placed in Abu-Dhabi. Louvre-III is planned for Abu-Dhabi. (Louvre-II in Atlanta). 1 billion $ is a very convincing argument. Officially are only the plans for Louvre-III, but as I know the Abu-Dhabi Sheiks they will put all effort to get at least for some time Mona Lisa. They always want the best/most exclusive. And I also know from own experience that nobody can resisit the smell of Petro-$. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Strongest 9x9 programm?
- Original Message - From: alain Baeckeroot [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Monday, January 01, 2007 2:33 PM Subject: Re: [computer-go] Strongest 9x9 programm? Having various opponents is the best way for improvement. Yes, I fully agree. I believe Sluggo is an extreme example of this, it is by design especially strong against GNU http://files.gokgs.com/games/2006/12/20/GNU-slugGo.sgf but it is not clear that it is stronger against other opponents: Yes, a well known effect. Very similar to Gnu-Go, but slightly stronger. This has a big impact. But GNU seems significantly stronger than Mogo19 (rated 2k higher on kgs) http://files.gokgs.com/games/2006/12/18/MoGoBot19-GNU.sgf For 19x19 Gnu-Go is also no good sparring partner for Suzie. Its too strong. The ideal sparring partner is slightly stronger. I think that any kind of search works quite well on 9x9. Search works too at 19x19, but the hardware is at the moment not fast enough. The INTEL engineers have to work a little bit harder for 19x19. Ok, crazystone 9X9 is available for download at Remi's page, but i see no license, so i suppose using it for testing is ok. Thanks for the information. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Strongest 9x9 programm?
Are we to assume that Size is starting to get good at 9x9 and can beat Gnugo consistently? - Don Peter Woitke has done a great job in the last month. He deserves the Hero of the Suzie work medal. Especially he fixed a lot of bugs. But on 19x19 its still not satisfactory, so Peter gave it a try on 9x9. To his surprise its much stronger than Peters own programm GoAhead. On 19x19 GoAhead is still clearly better. So he started to play with Gnu-Go. But thats still a little bit too weak. Suzie does not win all the time but she is already better. Peter does his experiments with a fixed depth 7 ply search. I want to improve the search in the next time. E.g. introducing time control, permanent brain, rote-learning Some basic things every chess programm has. But if the opponent is already beaten 70% of the time, its difficult to measure the effects. Therefore I am looking for an opponent which is at least as good. Attached is best of Suzie (or worst of Gnu-Go). But its not always like this. Yes, I forgot to mention that. KGS tournaments are only played once a month but there is nothing like the stress of a tournament to bring out bugs,and poblems. This is a very good rate of playing. Playing constantly is pointless, because one has always already something new. But one can make every month a stable version and look how it plays. Very stupid question: Were to I get a fool-proof description how to join the tournament? You know I am from the generation, were one travelled to tournament, shake hand with the programmer of the opponent, entered the moves by hand These internet tournaments are also a cultural shock. Chrilly GnuGo-Suzie_02_43.sgf Description: Binary data ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Sho-Dan-level at 9x9
For Suzie I try for 9x9 to establish a Dan-ranking at the next European Championship in Villach/Austria. Do you mean that you are planning to enter it for a regular human Go event? Have you checked that the organisers will allow this? I once entered Professor Chen's HandTalk for a human Go tournament which I was organising, in Oxford. I received no complaints from its opponents, but several from stronger players, and from British Go Association officials, who asked me never to do this again. Nick I am in touch with the organizers. They have asked me to give a lecture about computer-go. Maybe one can organize around this a 9x9 match humans against Suzie. Some sort of practical lecture. One has to give the humans some (small) incentive to take the match serious. E.g. at the Vienna chess open I played once with Nimzo Blitz. Every player had to pay 1$. The money was put in a pot and the first winner of a game got the pot. This was extremly popular and some players even went away during their games to hit the jack-pot. I do not plan to play in the official part of the tournament. There is up to my knowledge anyway no 9x9 tournament and if it is, an EC is for humans and not for computers. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Are there researches about human annotation togamerecords ?
Dogs can play Go? No. They can't. Dogs also cannot search for files on your computer. Why are my CPU cycles being wasted to animate a dog who may or may not pretend to know something that I don't? Is it purely to annoy? If so, hats off. Most (German) users enjoyed the dog. It was just fun. My nephew was too young. He did not understand that the word of the dog are not serious. Thats also a lesson we learned. The wasted cycles are no problem for a chess programm. Its anyway too strong for most users. It was in fact a challenge to make the programm weaker. Nobody plays nowadays for fun against a chess programm at its highest level. Its not sufficient just to search more shallow. The programm should mimic human errors. E.g. even world champion Kramnik missed recently in the match against Fritz a mate in 1, because it was an unusual pattern. But other mate in 1 are even for a beginner easy to spot. For a programm a mate in 1 is a mate in 1. One has therefore to introduce filters which differentiate between easy and difficult mates. Generally Artificial Stupidity is almost as difficult as Artificial Intelligence. In both cases one has to understand the working of the human mind. I think it is also generally an interesting and important topic to present computation results in a more natural way than numbers. The Schweinehund was just for entertainment. But entertainment is also a serious and difficult business. Chrilly On 12/14/06, Chrilly [EMAIL PROTECTED] wrote: I know of no research, but chess-programms like e.g. Fritz do this to a certain degree. There was (maybe is) an award by the ICCA-Journal for the best annotation by a programm. But I do not remember any papers how this is done. Trade secret. I have implemented another form of annotation in my chess-programm Schweinehund. An animated dog made comments on the game. This was insofar relastic, as my nephew felt insulted by his uncle. The dog made some bad comments about his playing style. But the underlying mechanism was rather primitive. The animation sequences were mainly selected due to evaluation changes and some online behaviour. E.g. when the human opponent took a long time for his move, he was many or only a few moves in the opening book... The impression of realism and meaningfull comments was due to the dog. I have my doubts that one can make with current Go programms a meaningfull annotation. For this purpose the programm must be much stronger than the user. E.g. when the dog said this was your second best move the programm must be relative sure, that the human played a blunder. It increases the fun if the dog is in a small percentage of cases wrong. But if the dog is most of the time wrong and the human move was in fact quite strong, its annoying. The generell advantage of an animated character is, that the comment/annotation must no be so detailed and one can cheat a little bit. E.g. if the programm realized that the comment before was wrong, the dog can say forget it, was just a joke. The difficult part is that it is an online-algorithm. In case of an annotation one can analyse the whole game before generating some comments. Chrilly - Original Message - From: 荒木伸夫 [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thursday, December 14, 2006 2:51 AM Subject: [computer-go] Are there researches about human annotation to gamerecords ? Hello. I'm Araki. Nice to meet you. I'm searching researches about human annotation to game records for machine learning. (for example, these stones are weak, this move is for attack those stones, this move was bad ...etc) Does anyone know such researches? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Are there researches about human annotation to gamerecords ?
I know of no research, but chess-programms like e.g. Fritz do this to a certain degree. There was (maybe is) an award by the ICCA-Journal for the best annotation by a programm. But I do not remember any papers how this is done. Trade secret. I have implemented another form of annotation in my chess-programm Schweinehund. An animated dog made comments on the game. This was insofar relastic, as my nephew felt insulted by his uncle. The dog made some bad comments about his playing style. But the underlying mechanism was rather primitive. The animation sequences were mainly selected due to evaluation changes and some online behaviour. E.g. when the human opponent took a long time for his move, he was many or only a few moves in the opening book... The impression of realism and meaningfull comments was due to the dog. I have my doubts that one can make with current Go programms a meaningfull annotation. For this purpose the programm must be much stronger than the user. E.g. when the dog said this was your second best move the programm must be relative sure, that the human played a blunder. It increases the fun if the dog is in a small percentage of cases wrong. But if the dog is most of the time wrong and the human move was in fact quite strong, its annoying. The generell advantage of an animated character is, that the comment/annotation must no be so detailed and one can cheat a little bit. E.g. if the programm realized that the comment before was wrong, the dog can say forget it, was just a joke. The difficult part is that it is an online-algorithm. In case of an annotation one can analyse the whole game before generating some comments. Chrilly - Original Message - From: 荒木伸夫 [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thursday, December 14, 2006 2:51 AM Subject: [computer-go] Are there researches about human annotation to gamerecords ? Hello. I'm Araki. Nice to meet you. I'm searching researches about human annotation to game records for machine learning. (for example, these stones are weak, this move is for attack those stones, this move was bad ...etc) Does anyone know such researches? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Are there researches about human annotation to gamerecords ?
If you had such annotated games, wouldn't you also need an impressive English language parser? Even more impressive if you consider the task of parsing English-as-a-second-language dialects. I do not understand the meaning of this sentence. Could you please explain it more explicetly? Chrilly On 12/13/06, 荒木伸夫 [EMAIL PROTECTED] wrote: Hello. I'm Araki. Nice to meet you. I'm searching researches about human annotation to game records for machine learning. (for example, these stones are weak, this move is for attack those stones, this move was bad ...etc) Does anyone know such researches? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] language choices
On 12/6/06, Magnus Persson [EMAIL PROTECTED] wrote: Note that to get these data I deleted all games where Valkyria lost on points, because close to 100% of those games were not scored correctly. I do not know if it is incompetence or outright cheating, but it happens a lot. Fortunately Valkyria always resigns when it loses so it easy to filter out those game. I found that humans tend to cheat a lot against computers in the scoring phase. This used to be the case on NNGS (my thesis contains some statistics on that if you're interested), and I don't see any reason why this should now be different on KGS, unless of course if computer players now have the same rights in the scoring phase as humans... Erik I think that humans tend to cheat also against other humans. When I started on KGS I was cheated several times very badly and I have stopped to play. I thought Go players have better manners than chess players. This is probably true in real-live, but on an unpersonal environment of a server all the Go-etquiette vanishes. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] language choices
that's truly bizarre. i've never been cheated on kgs, and in fact think that with the right ruleset it would be very difficult to be cheated. anything about which there is any confusion can easily be settled by playing it out. One example: The other player made very strange moves building a perfect but very small territory in his corner. I got the rest of the board. I found his play very strange. Then he passed and he asked me to pass too. I thaught he wanted to resign and passed also, it was a clear win for my position. But then the stupid software could only recognize only his territory and declared its a win for him. I did not know how to correct it and lost the game. Other players just disappear from the board. Without saying anything or resigning. When one the also quits the game it can happen that the game is considered lost. The reason for disappearing was no technical problem, because one could see them playing on in other games. The most annoying thing on KGS is Kyu-Fetishm. Due to this experiences above and also my lack of experience with humans I was rated 19 Kyu. My true playing strength is about 15. But it is very difficult to improve, because all the people want to play with a better ranked player. I setup as condition 19 +/- 2. One almost only gets offers from 20 or 21 players, seldom from 19 Kyu and practically never from 18 or 17. If one contacts oneself an 18 Kyu player, this offer is usually declined. Personally I never delined a 20 or 21 Kyu. I wanted to play, but it would be more interesting to play a few ranks below. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Knowing nothing about it
Sylvain Gelly wrote: You are totally right. For Yizao (one of the author of MoGo), who is a good Go player, this gives a bad style to MoGo. As I don't know how to play Go (beyond the rules :)), I don't see any style and I don't care :). I forwarded this to other people in the computer-chess community. The common answer was: Sylvain has the right qualification to be the new shooting star in Computer-Go. Feng Hsu wrote in the beginning of the Deep Blue project a paper Building a GM-level chess programm without knowing nothing about chess. This was probably a paraphrase of Hans Berliner, the former correspondence chess world-champion who build HiTech. I assume everytime Feng Hsu made a proposal Berliner did not like, he told him that he knows nothing about chess. Feng Hsu had even at the end of the Deep Blue project problems to make moves correctly on the board. It was not obvious for him were the square c5 is. There is another Chrilly's law: Everybody besides a GM can write a strong chess programm. Maybe this holds also for Go-Programms. Everyboyd beside a Dan can write a strong programm. Or maybe its the other way round. The programms are relative weak, because the programmers are all too strong. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] language choices
A note: we're working on converting Orego back from C++ to Java, and we're getting 5,000 (totally random at this point) simulated games per second. We'll probably continue in this direction. Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ Probably the most important feature of any programm is the Bugs/sec. rate. One method to find bugs is to have 2 independent versions and to compare the results. This is common practice in hardware design where one has e.g. a C version/simulator and a VHDL/Verilog design. Or everything is in VHDL but its programmed at different abstract levels. I does not help against conceptual bugs, but one catches at leas the stupid bugs. I have found this technique very usefull in Hydra. I think one should to the same in software-development too. But it is usually only done in very mission-critical software. But in your case you have already a Java and a C++ version. This is a big chance. I would develop both versions further in parallel. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to improve Orego
In the Orego paper the problem of selecting a move when the board is filled with stones is mentioned. Orego uses a sort of double-hashing scheme. But isn't it trivial to keep a list of empty intersections? Before the MC-run is started, one builds up this list. If a stone is placed now on the board, the entry is removed from the list and the last entry is copied into this slot. In this way the list is always dense. One can of course not run linearly trough the list to find the entry which should be removed. Instead one builds at the beginning another array which is indexed by the board-point and which contains the index of the point in the empy-point-list. This second array has to be changed too when the last entry is copied into the removed slot. With a few operations one gets the big advantage to sample all the time only the empty points. I think this solution is much simpler and more efficient than the double-hashing scheme of Orego. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Technical Report on MoGo
- Original Message - From: House, Jason J. [EMAIL PROTECTED] To: [EMAIL PROTECTED]; computer-go computer-go@computer-go.org Sent: Monday, December 04, 2006 8:10 PM Subject: RE: [computer-go] Technical Report on MoGo I'd be a bit more careful about the comparison with alpha-beta in section 2.3. I believe that iterative deepening of alpha-beta is very common. It can be argued that when iterative deepening is used, an early termination isn't very detrimental. I've seen people get completely turned off to a paper simply because they compare their carefully optimized results to a poor implementation of some other algorithm (ie. alpha beta). Alpha-Beta is for practical reasons of course also an anytime algorithm. In chess one does not send the first iterations to the GUI, because showing the result in the GUI is slower than the calculation of the engine. And the user would not notice it anyway, its too fast. My reaction when I read this statement was: iterative deepening is not yet invented in the Go community. But Alpha-Beta is not a continous algorithm. If one searches to depth k, the nodes till the first move at depth k+1 is completly searched have no additional information. Usually one does some estimates beforehand if it pays to search for another iteration. Chrilly -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: Friday, December 01, 2006 6:03 PM To: computer-go@computer-go.org Subject: [computer-go] Technical Report on MoGo Hello all, as perhaps some of you may be interested, I give here a link to a technical report about MoGo. You can find there a lot of details about the ideas around MoGo. While we tried to be as clear as possible, some details may lack. There is still no number on this report, but this will come in a few days. http://hal.inria.fr/inria-00117266 I would like to thank of course all the authors, but also Rémi Coulom who shared a lot of details about CrazyStone and his ideas. I also would like to thank all the contributors in this list for interesting discussions. Now my feeling is that the improving random simulations part of this work is promising. We have only done very few steps in this direction, and it gives quite convincing results. It was what I meant in the random distribution discussions we have in this list. I am pretty sure that making improvements in this direction would increase a lot the level of MC players even (or especially) in 19x19. And this can be done very soon (well, perhaps not before sunday :)). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo is the future of19x19
Le Vendredi 01 Décembre 2006 11:57, Chrilly a écrit : On a P4 3.0Ghz mono processor, the number of evaluations per seconds is in the order of 4500/s in 9x9, 2500 in 13x13 and 1100 in 19x19. If one assumes 300 moves/Plies on 19x19 it would be about 330 KNodes/sec? No, that just mean 1100 Nodes/sec in 19x19. When I meant 1 evaluation, I meant 1 random simulation. For me, 1 position=1node=1random simulation. Sorry I don't see exactly why you are multiplying by 300, but I think now we understand each other :). Sylvain Well, at least I learn at lot. E.g. that you are the author of MoGo :-) As an old chess-programmer the unit is not games/second but nodes/sec. Making a move and undoing it (if undo is done at all). Thats the basic unit in any game. In your MoGo paper you mention the First-Play-Urgency FPU. I did not understand precisly what FPUs is: Is it: If a node is visited first (or not all moves have been tried out) the nodes are not selected with uniform probablity but e.g. Capture and Atari moves have a higher probablity? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Making Java much faster
I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust (like Mogo has with 9x9 Monte Carlo Go.)This happened in computer chess several times, someone came up with some breakthrough idea, proved it with actual results and everyone else had to play follow the leader to catch up. Do you think its also the future of 19x19 or only of 9x9 (maybe 13x13)? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo is the future of 19x19
Are there any details, or publications, on what Mogo is doing at 19x19? I'd thought consensus opinion here was that monte carlo scaled to 19x19 badly. Darren A very stupid question: What is Mogo, who has it written? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Making Java much faster
However, we are finding C++ an exceedingly frustrating language to work in. I won't go into the details here -- we don't need another language war -- but suffice it to say that it seems like we're spending a lot of time messing with details that aren't of interest for the research. Now that I've found that Java can have speed within a factor of 2 of C++, I'm thinking of going back to Java. I have run over the years bug-statistics. At least in my code the error-rate is language independent. This holds even for Assembler and Hardware-Description languages. There are some typical errors one makes in one language which are not done in another one. But overall this has minor influence one the bug-statistic. The real source of bugs are exceptional cases and not well understood concepts or a new concept which does not fit to the initial design. E.g. there is hardly any chess programm which has no enpassant bug. C and Java are in my opinion almost the same languages. I think the error rate and nowadays also the speed is very close. Its just a matter of taste and not of any real advantage of one language. Concerning memory leaks I think one should avoid to allocate memory at all. This makes the programm faster and avoids memory leaks. E.g. Suzie has besides allocating the hashtable at startup no memory allocation. I had also a mixture of UCT with an static evaluation and even this version had not memory allocation. If one allocates dynamically memory, a memory leak is a sign of a flaw in the design. The Java garbagge collection avoids the crash. But this is no advantage, because the flaw is just hiden. The programm will also eat up memory in Java. A bug which lets the programm crash is a harmless bug. The really bad bugs never show up. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
I assume in Go the difference is also a very large handicap. in any case, i think that the difference is probably much larger than just one or two stones. :) It is said if has 4 stones handicap, every Pro will accept games play with God even if bet his life. When in limited local fighting like TumeGo, Pro plays just like God. igo One has to differentiate: In chess humans play very close to optimal in the subset of chess which is played by humans. But this is only a very small subset of what is really playable. E.g. There is currently a match between Kramnik and Fritz. I showed the Kramnik team a game were Hydra crashes Fritz in an important variation with a rook v. bishop sacrifice. But the team said: Theoretcially convincing, but of no use for us. Kramnik can not play this tactical massacre against a computer. Thats unhuman chess. Humans are very far away from optimal play in unknown positions. E.g. they are helpless against a perfect endgame database. Such a DB plays from the human point of view completly crazy moves. A human opponent would never play this. In human-machine matches it is very important for the machine team to deviate from the human-patterns and to get a chaotic position. In the preperation for the Adams-Hydra match we spent a lot of effort to deviate as soon as possible from known opening theory and also that the programm plays strange moves which are not necessarily optimal. The only requirement was, that this strange moves are not really bad. This is completly sufficient against a human. My personal criterion was: When the Hydra chess expert GM Lutz said Hmmm, whats this, I asked him if its bad. If he could not give a convincing reason why its bad within 10 seconds, it was a very good move against Adams (but not against God). I think the same will happen also in Go. They have only a chance if God plays human-Go. But against non-human moves they are certainly as helpless as the chess-players. I assume its even worse, because Go is more pattern related and more complex than chess. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
In the second game Fritz against Kramnik Fritz played strategically very poor (or Kramnik very strong), Kramnik avoided a 3-times repetition offer of Fritz, but at the end Kramnik missed an easy to see mate in 1!! and lost very badly. Thats the end of the match. He will not be able to recover from this blunder. This is a rather drastic example of Chrillys law: Humans can not play in a complicated position more than 10 moves in a row without making an serious blunder. And it also very drastic example how far they are away from God. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] .. if Monte-Carlo programs would play infinitestrong
on a practical note, i think that MC is a great idea for 9x9, and might even be a great idea as a subset of a larger piece of code that employs human knowledge, but that MC will never beat a decent human at 19x19. the time/space limitations are just too great. Does this mean that it does not converge to optimal play when processing power goes to infinite or do you mean that it converges from the practical point of view much too slow? I think an MC player with 10**10 nodes/sec is even with todays technology possible. A system like Deep Blue with 256 special purpose hardware chips could reach this number. (There is of course then also the question about the parallel speedup). E.g. running with 500 MHz and using 12 clock-cycles/position gives 40 MPos/sec per chip. Hydra uses 8-9 clock-cycles per position, but the programm runs only at 55 MHz. The FPGA chips are already dated, on the newest generation it would be = 100 MHz. ASICs like in Deep Blue are faster. Generally I assume that Go would run with a higher clock-rate than in chess. The speedup in relation to a software solution would be considerable greater, because the board is larger and one could use the fine grained parallelism of a hardware-chip better. One could even design a 3 GHz Go-chip, but then one has to invest about the same amout of money like for a Pentium. This would be even for a Sheikh too expensive. Up to 500 MHz the design costs should be within a Sheikhs budget (unfortunately Sheiks do not even know the game of Go). What would it mean for a 19x19 player? What would it mean to build a 10**12 nodes/sec machine (which is with todays technology not possible, but according to Moores law in 10 years). Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Positions illustrative of computer stupidity ?
The attached position requires some basic understanding of Go. But its in my experience a nasty problem. There is a simple rule for capture races. The side with the higher number of liberties wins (if there are no eyes and more =2 inside liberties involved). The side to move counts as a 1/2 liberty. Unfortunately this rule is not valid in the position. White is unconditionally dead. All liberties are equal, some are more equal. Chrilly Semeai01.sgf Description: Binary data ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Positions illustrative of computer stupidity ?
Attached is another simple problem. A tactical-solver might work as this. It checks all strings. If the number of liberties is below a thresold (e.g. 3) it defines the string as a prey and tries to kill the string. Then the solver takes the next prey, tries to kill it. For this tactical solver the white stones are save. Each prey can escape individually, but due to the double-atari one of them is dead. This is a trivial example, but there are more difficult ones which are much harder to solve. Even the best strong programms like Handtalk are very vulnerable to double attacks (there are other ones like Many Faces which do not suffer from this problem).. Chrilly DoubleThreat.sgf Description: Binary data ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
