Re: [computer-go] Rules for remote play at the Computer Olympiad
Vincent Diepeveen wrote: If a program under no circumstance can reproduce a specific move and that for several occasions, then that's very clear proof of course. [...] Statistics prove everything here. No. Rather it proves that the program cheats OR that the methods of detecting cheating are improper. > One always must have a logfile Good. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Rules for remote play at the Computer Olympiad
Hi, I see there has been some discussion in this list about cheating remote. In computerchess this toleration has grown out of hand. Setting the rules clear and sharp there in computer-go might avoid for the future a lot of problems. There is a very simple manner to avoid cheating in go. But let me adress a few points first. 1) neural nets forget about neural nets and cheating. A year or 12+ ago we had a lot of neural net guys in computerchess as well. ANN's are not even close to representing the human mind, as modern insights in how brains work shows clearly already for quite a while. Most important is that the automatic learning techniques of neural nets are so total inefficient that it is really difficult to use them well. Soon anything that is neural net will be beaten by the rest major league. The only case i remember that was a tad more stubborn was basically someone who tried to fool the rest; he bought source code from someone and sold that as the 'neural net optimized version' engine. Yet the original programmer of that code (Joost Buijs), he assured me that this program definitely used his parameters and not some neural net optimized parameters, as he could reproduce even every score of it. So in that case it was not the neural net that was there, it just was getting used as a sales reason. Yet the neural nets will get beaten major league. If not next year, then some years later. You can't forever improve a product without good debugging methods of what it actually is doing. A black box that is real clever and intelligent doesn't exist. 2) sure on paper it is really easy to cheat. IT IS ALSO REALLY EASY TO CHEAT WITHOUT REMOTE MACHINES IN FACT. Oh in computerchess we've seen it all. There is a certain species of persons on the planet, they are not in big numbers there, who are capable of fooling in a professional manner other persons, James Bond is nothing compared to the sneaky manners they get things done. For sure a bunch of them will also try it in computer-go. For these guys, considering how weak for the coming few years go computers will play, there is not a big difference between remote machines and local machines. It's too easy to cheat for them. Communication to and from a program is too difficult to 100% monitor. So to speak just keeping the mouse at a certain spot is already enough to cheat, or having someone a fewmeters away at his laptop signal something over blue tooth or whatever to the playing machine. All been done. The only real simple manner of catching crooks is by having a good tournament director who will enforce in case of suspected moves played, that an engine must reproduce the move it played, with some reasonable decent score. Now some of you will argue loud in one choir: "parallel search doesn't reproduce moves". One move can make or break a game, yet those who cheat have the habit to cheat many moves a game and for several games. So there should be many datapoints one complains about. If a program basically cannot reproduce a move, at the discretion of the tournament leader who might want to see whether a move in question has a very similar score to other alternatives (in which case of course you don't know which of the equal scored moves or nearly equal scored moves can get played). But the principle thing is reproduction of great moves. If a program under no circumstance can reproduce a specific move and that for several occasions, then that's very clear proof of course. That is a rule that should be introduced in computerchess also IMHO. Note there is also the time constraint. And search depth constraint. One always must have a logfile displaying which iterations or steps a program already has performed; if one searches in a very selective manner, a rather easy form of cheating that is 'near undetectable', is when a program plays moves that it normally spoken would not have found on that hardware, yet iterations deeper. As in selective search you can assume that in a move sequence m0..mN that the moves 0..N represent the line that one needs to see to find it, there will be of course selectively moves in that sequence that might have been reduced somehow. So if one takes care that in the 'hashtable' such sequence already gets searched deeper, by manually enforcing that sequence, then the program 'learns' itself from hashtable sooner that move. Now in chess this is easier than go currently, as the search method used is reductions, but it'll come in go also. Really effective is giving in the 'mainlines' of your opponent to be searched fully by a number of cores. Yet again the only way to really detect this is by forcing reproduction of the moves by the tournament director. If a system can't reproduce enough of the great moves played, for whatever reason, bad luck. For parallel systems that search total non-deterministic, there is also a simple lemma;
Re: [computer-go] Re: GCP on ICGA Events 2009 in Pamplona
hi, You're miscounting here completely again. Counting the number of federation members is a bad idea. Count the number of people who know a game and regurarly play it. Draughts (internatoinal 10x10 checkers, using polish rules) is really tiny. It is not culture to get a member of a club in a nation like Netherlands anymore, netherlands is a very weird nation in that respect. Yet many learn the game. You shouldn't let yourself get led by federation numbers, but by the number of people who know a game and play it regurarly. Active official competition players is simply a bad measure. The online chess servers are indeed a bad measure. It is spreaded over a number of servers. Yahoo has a daily load of about 7000 that are nonstop playing, chessclub.com which used to be a paid club and still is, it has about a million who visit, yet as a membership has a cost of 50 dollar, which is 500 yuan nearly a year, that's a price i'm not willing to pay either. chessclub offers free membership to titled players. Yet i'm titled and i have to pay how about that? Having 2 dutch titles and a fidemaster title seemingly doesn't count :) The strongest players are at chessclub.com It's about 2500 nonstop (so 24 hours load) now, chessbase is becoming a tad larger now, note also a paid chess club. About 3000 load. Yet again you have to either buy a product of them for 50+ euro for a free 1 year membership, or you have to pay 25 euro a year for membership. There is a range of servers. Each one has about a 500-1000. Most are paid. There chess is really doing bad of course. Experience learns when you setup a free server with a good client that you soon get a huge load. 5000+ is very normal. There is a lot of tiny communities with a 400+ players 24 hours a day online. that's what you get when there is 105+ nations playing chess. Each federation wants their own server. Yet they do not want to pay for it. FIDE really is doing very bad there. Their problem would be they go to commercial companies which have all their own interest, instead of using a few of their guys who already work in organisations and are objective. Vincent On Jan 14, 2009, at 4:06 PM, Mark Boon wrote: On Jan 14, 2009, at 12:43 PM, Thomas Lavergne wrote: Couting xiangqi and shogi players as chess players is a bit unfair... Sorry if I caused confusion, I didn't mean to count those as Chess- players. I just stated that to show that despite large population- numbers in say China, most of those people play Xiang-Qi rather than Wei-Qi. This in contrast to a large country like Russia where I believe Chess is by far the most popular. In Holland however, Chess comes only at third place (or maybe even lower) after Bridge and Draughts. Mark ___ 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: GCP on ICGA Events 2009 in Pamplona
On Jan 14, 2009, at 1:42 PM, Mark Boon wrote: It's difficult to get hard data about this. Go is only the most popular game in Korea. In other countries like Japan and China it comes second by far to a local chess variation. Possibly Chess is more ingrained in Western culture than Go is in Asia, I don't know really. But Chess has the population-numbers of West vs. East against it. If there are more chess-players than Go- players in the world then it won't be by much. But the Go market is probably a lot bigger. Look only at the money in professional Go tournaments. It's probably an order of magnitude more than the money in professional Chess. But I must admit this is just a guess of mine. Mark Oh la la, The origin of chess and go isn't far away from each. Chess originates from India, go not far away from there, if you look at it from a global perspective. Both go and chess are really similar in that they are symmetric games. From strong player perspective there isn't that much difference in the game in intellectual experience. A good chessplayer can be a good go player and vice versa. Quite the opposite with the zillions of checkers versions there are. Checkers is NOT a symmetric game. If Chess would get added again to the olympic sports (which i doubt happens, but you never know how political decision taking takes place) that would be good news for China's women team. Maybe they lose on board 1 sometimes, but the other boards they'll win all games. Chess is becoming really big in China now (heh i'm still looking for a girlfriend, know a Chinese female go or chessplayer?) I'm quite sure chess is by now bigger in China than go there. Of course the step from Chinese chess to chess is real real tiny as well. Chess gets played in every nation on the planet. Tiniest chess is probably in Japan. Shogi and go seem to be more popular there. South Korea used to be real tiny also for chess, a new initiative there might boost it a tad more. Chess' advantage is of course the fact that the game is a lot quicker than go. Now for serious, strong players, that is not an advantage, but for the 'big masses' it is. Chess computers used to get exported to 105+ nations world wide. As for the rest of the planet, with exception of Japan and Korea, go doesn't exist. There is no doubt about that some very succesful chess and go players to be very very wealthy. If you're good in that game, you have good brains of course, everyone likes to pay you, most chessplayers even get asked to run a business of some billionair type guys. I don't doubt that's identical in go. Whether 1 go player has more billions worth of wealth than a chessplayer, that's not very interesting. As for the 'subtop', there chess is quadratic bigger than go. How many people live from chess? Well thousands. Amazing yet true. Whereas in a few nations like Netherlands the number of chessplayers that are a member of a federation is getting less, realize the tiny size of the nation here, netherlands has exactly 16.5 million inhabitants. Even then each town still has a chessclub. Chess is total booming in India, China, Turkey and Spain. Just these 3 nations are already nearly 3 billion people. When i was in China, i saw zero go boards anywhere. Vincent On Jan 12, 2009, at 9:22 AM, steve uurtamo wrote: i think you might be estimating this incorrectly. s. On Sat, Jan 10, 2009 at 9:00 AM, Gian-Carlo Pascutto wrote: Ingo Althöfer wrote: What prevents you from freezing in your chess activities for the next few months and hobbying full (free) time on computer go. The amount of chess players compared to the amount of go players. -- GCP ___ 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] Pseudo liberties: Detect 2 unique liberties?
Isaac, Most groups have only say 4 to 8 liberties. This is why simple arrays of liberty locations work so well. The new Intel CPUs have instructions that can search strings 16 bytes at a time, so it could run even faster. Bit vectors also work, but if you want a true liberty count, then you have to avoid counting (1 or 1) as 2, which is the pseudo liberty problem, and which takes more code to write and more time to compute. When I started, I wanted to find a better implementation than gnugo, and I was unable to do so. Of course one can refine or simplify the gnugo code in many different ways, but gnugo has all of the good ideas. Michael Wing PS: Here is the data for how many times the program tried to insert a stone into a chain that has x liberties or x adjacencies. It was taken from a run that combined monte carlo simulations and ladder reading exercises. Note that there are only 2% as many liberties/adjacencies of size 8 as there are of size 0. Chains with liberties/adjacency lists of size 16 are so few as to be irrelevant. 0 => 4662825 1 => 3524214 2 => 2323725 3 => 1167185 4 => 368184 5 => 245659 6 => 167392 7 => 117655 8 => 84715 9 => 61126 10 => 44407 11 => 32309 12 => 24105 13 => 17639 14 => 13111 15 => 9935 16 => 7378 17 => 5417 18 => 3975 19 => 2900 20 => 2111 21 => 1566 22 => 1055 23 => 783 24 => 616 25 => 399 26 => 290 27 => 221 28 => 174 29 => 127 30 => 95 31 => 71 32 => 60 33 => 44 34 => 15 35 => 4 36 => 2 37 => 1 38 => 1 39 => 0 40 => 0 41 => 0 42 => 0 >> On Thu, Apr 2, 2009 at 5:14 AM, wrote: >>> Isaac, >>> >>> I implemented about 6 way to track liberties, >>> a couple years ago, and measured the running >>> performance, and by far the best is also the >>> simplest: keep an array of liberties for each >>> chain, and do a simple linear search. >>> >>> This may seem slow, but it has a couple real >>> advantages. First, it works with the cache >>> to maximize locality. Second it is very simple. >>> > > This *does* seem slow, even when caching the number of liberties. You > mentioned that you did this a couple years ago, do you think it still holds > true? Thank you for the information. > >> This is what I do too. I never bothered with bit-arrays but possibly >> that's simply because I fail to see how you can merge two chains and >> count liberties in O(1). > > Merging would be a simple OR operation. Counting can be done, for example, > with some kind of binary search. Counting the bits set has been well > researched and many different algorithms exist. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
From: Heikki Levanto On Fri, Apr 03, 2009 at 05:07:41PM +0200, Isaac Deutsch wrote: > > > This may seem slow, but it has a couple real > > > advantages. First, it works with the cache > > > to maximize locality. Second it is very simple. > > This *does* seem slow, even when caching the number of liberties. You > mentioned that you did this a couple years ago, do you think it still holds > true? Thank you for the information. > > > This is what I do too. I never bothered with bit-arrays but possibly > > that's simply because I fail to see how you can merge two chains and > > count liberties in O(1). > > Merging would be a simple OR operation. Counting can be done, for example, > with some kind of binary search. Counting the bits set has been well > researched and many different algorithms exist. > besides, most often you only need to know if a string has zero, one, two, or many liberties, so the counting can be aborted early. Most cases do test for zero/one/two/many, but if we want smart playouts, it helps to know in advance exactly how many liberties some strings have, compared to others in a capturing race. Any program which assumes that "n liberties is enough to live" may be tricked by a player who can count to n+1. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
On Fri, Apr 03, 2009 at 05:07:41PM +0200, Isaac Deutsch wrote: > > > This may seem slow, but it has a couple real > > > advantages. First, it works with the cache > > > to maximize locality. Second it is very simple. > > This *does* seem slow, even when caching the number of liberties. You > mentioned that you did this a couple years ago, do you think it still holds > true? Thank you for the information. > > > This is what I do too. I never bothered with bit-arrays but possibly > > that's simply because I fail to see how you can merge two chains and > > count liberties in O(1). > > Merging would be a simple OR operation. Counting can be done, for example, > with some kind of binary search. Counting the bits set has been well > researched and many different algorithms exist. besides, most often you only need to know if a string has zero, one, two, or many liberties, so the counting can be aborted early. -H -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: RE: [computer-go] Pseudo liberties: Detect 2 unique liberties?
> On Thu, Apr 2, 2009 at 5:14 AM, wrote: > > Isaac, > > > > I implemented about 6 way to track liberties, > > a couple years ago, and measured the running > > performance, and by far the best is also the > > simplest: keep an array of liberties for each > > chain, and do a simple linear search. > > > > This may seem slow, but it has a couple real > > advantages. First, it works with the cache > > to maximize locality. Second it is very simple. > > This *does* seem slow, even when caching the number of liberties. You mentioned that you did this a couple years ago, do you think it still holds true? Thank you for the information. > This is what I do too. I never bothered with bit-arrays but possibly > that's simply because I fail to see how you can merge two chains and > count liberties in O(1). Merging would be a simple OR operation. Counting can be done, for example, with some kind of binary search. Counting the bits set has been well researched and many different algorithms exist. -- Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] UCT: Artificially increasing the number of visits to a node.
Hi, While recently implementing UCT, I've come across two cases where one may want to increase the number of visits to a node by something greater than 1. A) Leaf nodes - Artifically set the number of visits to some very high number. The rationale for this is to accelerate propagation of the leaf condition "up the tree" so as not to waste future time descending on parts of the tree which have a known outcome. Does that make sense? B) In the section "UCT with Prior Knowledge" within the paper "Combining Online and Offline Knowledge in UCT' Gelly/Silver mention seeding the visits with the "equivalent experience" contained in the prior value function, eg. n(s,a) <- n-prior(s,a) Therefoe, I assume that in Gelly/Silver's "updateValue(node,value), the line: node[i].nb = node[i].nb + 1; is replaced with something like: node[i].nb = node[i].nb + k; where k >= 1 This raises two questions: 1) What is an effective way of dealing with leaf nodes? Is what I describe above in A) typical? 2) Is it really OK to increase the number of visits and propagate them "up the tree" this way? Does it break any of the statistical assumptions inherent in the algorithm. I suppose it must be "OK" in that it is mentioned in the paper. Sorry if these questions seem basic, but I think it's important to get the details right. Thanks, I appreciate any further insights. -- Greg ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
