Re: [computer-go] Are there researches about human annotation togamerecords ?
You are right, I understood it in the wrong way. The programm should annotate. But its the other way round. In chess there is a language independent annotation vocabulary defined by the informator. E.g. "!!" means very strong move, "??" plunder But usually there are also natural-language comments. The language is very restricted, but it is nevertheless difficult to understand/parse it. Chrilly - Original Message - From: "Chris Fant" <[EMAIL PROTECTED]> To: "computer-go" Sent: Thursday, December 14, 2006 8:51 AM Subject: Re: [computer-go] Are there researches about human annotation togamerecords ? My understanding of Araki's message was that he wants to input human-annotated games into his learning machine. My point was that humans writings are not very precise (especially when using a non-native language). On 12/14/06, Chrilly <[EMAIL PROTECTED]> wrote: > 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/ ___ 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 ?
On 12/14/06, Chrilly <[EMAIL PROTECTED]> wrote: > 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? If I understand correctly, the point was that: (a) parsing English is hard (b) most English language comments on Go games are made by those for whom English is a second language, who don't use "correct" English :. (c) (b) is likely to make (a) even harder. Personally I disagree, but that's entirely off topic. cheers stuart ___ 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: 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] OT: Are there researches about human annotation to gamerecords ?
Le jeudi 14 décembre 2006 10:36, Stuart A. Yeates a écrit : > If I understand correctly, the point was that: > (a) parsing English is hard > (b) most English language comments on Go games are made by those for whom > English is a second language, who don't use "correct" English > :. (c) (b) is likely to make (a) even harder. > > Personally I disagree, but that's entirely off topic. > > cheers I think that (b) makes (a) much easier. English is very irregular language, and very comon mistakes are to "regularize" it (ed for past, "more" everywhere instead of "er"...) My personal experience is: i understand easyly people for whom english is not mother tongue, but i have bigger problems with native speakers. btw, there was some times ago a disccussion about sgf format, and some ideas from PGN chess format: this one includes standardised annotation (http://www.very-best.de/pgn-spec.htm) ! good move !! very good move ? bad ?? very bad !? interesting move ?! dubious move +- white wins += white better =+ black better -+ black wins this is easy to parse :) but not standard in go yet. Need some worldwide lobbying to convince chinese korean and japanese people to annotate games like this for ease of poor westerners guys, but i m rather sure they have some ideogram which says much more than this and will confuse us :) cheers Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] OT: Are there researches about human annotation togamerecords ?
Le jeudi 14 décembre 2006 10:36, Stuart A. Yeates a écrit : If I understand correctly, the point was that: (a) parsing English is hard (b) most English language comments on Go games are made by those for whom English is a second language, who don't use "correct" English :. (c) (b) is likely to make (a) even harder. Personally I disagree, but that's entirely off topic. cheers I think that (b) makes (a) much easier. English is very irregular language, and very comon mistakes are to "regularize" it (ed for past, "more" everywhere instead of "er"...) My personal experience is: i understand easyly people for whom english is not mother tongue, but i have bigger problems with native speakers. Yes, I worked at the European Space Agengy. The official language was English. The only ones which spoke a disturbing and difficult to understand language were the staff members from the U.K. Actually the official language was a sort of Pidgin. But this is also true for international conference papers and other sorts of international communication. I think it is on the one side nice to be able to communicate e.g. with people from Finnland without speaking Finnish. But after some time I found this Pidgin rather depressing. One can not communicate more subtle thoughts or feelings. Thats not only a language question, but also of the cultural background/semantics. Its e.g. also difficult for an Austrian to have a subtile conversation with a German, although the language is almost the same. But the German takes everything face value, the meaning of an Austrian sentence is often the opposite. E.g. "I enjoyed the party very much, it was very, very nice" means for an Austrian "It was a boring evening". btw, there was some times ago a disccussion about sgf format, and some ideas from PGN chess format: this one includes standardised annotation (http://www.very-best.de/pgn-spec.htm) ! good move !! very good move ? bad ?? very bad !? interesting move ?! dubious move +- white wins += white better =+ black better -+ black wins This is the Informator-standard in chess. There are additional characters like "with the idea of". Some of them are chess specific like e.g. the characters for pieces. this is easy to parse :) but not standard in go yet. Need some worldwide lobbying to convince chinese korean and japanese people to annotate games like this for ease of poor westerners guys, but i m rather sure they have some ideogram which says much more than this and will confuse us :) Or we are too lazy, ignorant to learn it. I have bought a "Japanese for Dummies" CD, but its too difficult for me. I admire the Japanese native speakers which learn English. I think it is also the other way round quite difficult. 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 to gamerecords ?
I like the chess player dogs. Thumbs up for them. Anyway, Searcher dogs should be killed this way: http://news.bbc.co.uk/2/hi/europe/4489792.stm :-P --- Chris Fant <[EMAIL PROTECTED]> escribió: > 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. > > > 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: > > 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/ > __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Slow KGS computer Go Tournament
The 2006 Slow KGS computer Go tournament will be next week, starting at 00:00 on Monday 18th UCT (GMT). It will be a five round Swiss, with each game taking a full day (i.e. eleven hours fifty minutes each, sudden death). Each game is scheduled to start at midnight in my UK timezone, so the five rounds will occupy Monday, Tuesday, Wednesday, Thursday and Friday. With apologies for the short notice - I want to get this done before the end of the year, so as to at least partly keep to promises made earlier. You can regard it as a test slow tournament. The rules are, 19x19 boards, Chinese rules, 7.5 points komi. Apart from the long time limits, it will be like the previous KGS bot tournaments that I have organised. The entrance requirements will be slightly tighter than for the Open divisions of those, at my discretion - e.g., I don't want several slightly modified versions of GNU Go playing, but I will welcome a genuine GNU Go and SlugGo. The KGS page for the event is http://www.gokgs.com/tournInfo.jsp?id=255 The entry instructions, as usual, are at http://www.weddslist.com/kgs/how/index.html Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] OT: Are there researches about human annotation togamerecords ?
Dear Araki, actually I just wrote a master thesis on a the issue of concept learning on patterns. I labeled the connectivity between two chains according to five classes: 1.strongly connected 2.connected (two moves can separate) 3.conditionally connected 4.separated (two moves can connect) 5.strongly separated With that I learnt a classifier using low level features from the Common Fate Graph defined by Thore Graepel et al. Results are quiet encouraging. My advice, only use annotations that you can record using first order logic and make the annotations specific. Try thinking of learning concepts that you believe are hidden inside your representation. This almost always means that you should try to learn local concepts. For instance you could learn the weakness of a group by labeling them from 1 to 10. The defence is due tomorrow, if the thesis is available by internet I led you know. Cheers, Emil Nijhuis On 12/14/06, Chrilly <[EMAIL PROTECTED]> wrote: Le jeudi 14 décembre 2006 10:36, Stuart A. Yeates a écrit : > If I understand correctly, the point was that: > (a) parsing English is hard > (b) most English language comments on Go games are made by those for whom > English is a second language, who don't use "correct" English > :. (c) (b) is likely to make (a) even harder. > > Personally I disagree, but that's entirely off topic. > > cheers I think that (b) makes (a) much easier. English is very irregular language, and very comon mistakes are to "regularize" it (ed for past, "more" everywhere instead of "er"...) My personal experience is: i understand easyly people for whom english is not mother tongue, but i have bigger problems with native speakers. Yes, I worked at the European Space Agengy. The official language was English. The only ones which spoke a disturbing and difficult to understand language were the staff members from the U.K. Actually the official language was a sort of Pidgin. But this is also true for international conference papers and other sorts of international communication. I think it is on the one side nice to be able to communicate e.g. with people from Finnland without speaking Finnish. But after some time I found this Pidgin rather depressing. One can not communicate more subtle thoughts or feelings. Thats not only a language question, but also of the cultural background/semantics. Its e.g. also difficult for an Austrian to have a subtile conversation with a German, although the language is almost the same. But the German takes everything face value, the meaning of an Austrian sentence is often the opposite. E.g. "I enjoyed the party very much, it was very, very nice" means for an Austrian "It was a boring evening". btw, there was some times ago a disccussion about sgf format, and some ideas from PGN chess format: this one includes standardised annotation (http://www.very-best.de/pgn-spec.htm) ! good move !! very good move ? bad ?? very bad !? interesting move ?! dubious move +- white wins += white better =+ black better -+ black wins This is the Informator-standard in chess. There are additional characters like "with the idea of". Some of them are chess specific like e.g. the characters for pieces. this is easy to parse :) but not standard in go yet. Need some worldwide lobbying to convince chinese korean and japanese people to annotate games like this for ease of poor westerners guys, but i m rather sure they have some ideogram which says much more than this and will confuse us :) Or we are too lazy, ignorant to learn it. I have bought a "Japanese for Dummies" CD, but its too difficult for me. I admire the Japanese native speakers which learn English. I think it is also the other way round quite difficult. 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] Anchor Player
I would like to take part in the 19x19 competition. I also prefer kyu rating to Elo, but I got the impression that you were relating kyu rating with handicap games (that is usually done by human players). I think handicap is a bad idea for computers. Handicap requires human intelligence to understand how the playing style must be changed. It completely ruins fuseki databases and may also make josekis that are good under equal play too slow. Of course, if you pretend to ruin fuseki database programs, its a good idea. But I think dan/pro level fuseki is not only legitimate, but probably the best possible fuseki and it can be played in ultrablitz which preserves computing time for later moves. The only drawback is 10 Mb of disk space. Any silly welcome video is heavier than that. I suggest, if handicap is implemented, it should be optional. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Anchor Player
I'd really like to see a way to work out the issue of handicap stones so that they can enter into computer go competitions. In the past, there's been strong complaints about stronger bots playing against weaker bots. Would giving handicap make such match ups at least seem more interesting? I think that if we can find a way to make the winning probability for any given game close to 50%, all both authors will get more useful information. If 19x19 shows a clear leader like MogoBot on 9x9, I'd bet the authors would take pride saying they were 4 stones ahead of the competition. As a weak bot author, I'd take pride in being able to beat Gnu Go with 6 stones given to my bot. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Anchor Player
Handicap seems to be an integral part of the game of GO, however I won't be implementing it right away.Perhaps at a later time I will add it. When and if the time comes I will solicit suggestions, as this server is primarily for the use of developers. - Don On Thu, 2006-12-14 at 19:05 +, Jacques Basaldúa wrote: > I would like to take part in the 19x19 competition. > I also prefer kyu rating to Elo, but I got the impression that > you were relating kyu rating with handicap games (that is > usually done by human players). > > I think handicap is a bad idea for computers. Handicap > requires human intelligence to understand how the playing > style must be changed. It completely ruins fuseki databases > and may also make josekis that are good under equal play > too slow. Of course, if you pretend to ruin fuseki database > programs, its a good idea. But I think dan/pro level fuseki > is not only legitimate, but probably the best possible fuseki > and it can be played in ultrablitz which preserves computing > time for later moves. The only drawback is 10 Mb of > disk space. Any silly welcome video is heavier than that. > > I suggest, if handicap is implemented, it should be optional. > > Jacques. > ___ > 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] Anchor Player
There are two basically different handicap systems, right? One of them allows free placement of the handicap stones and the other is fixed. I would probably do the fixed version for consistency. To accommodate programs that haven't implemented handicps I could just send play commands along with the appropriate passes to start the game. - Don On Thu, 2006-12-14 at 14:22 -0500, House, Jason J. wrote: > I'd really like to see a way to work out the issue of handicap stones > so that they can enter into computer go competitions. In the past, > there's been strong complaints about stronger bots playing against > weaker bots. Would giving handicap make such match ups at least seem > more interesting? > > I think that if we can find a way to make the winning probability for > any given game close to 50%, all both authors will get more useful > information. If 19x19 shows a clear leader like MogoBot on 9x9, I'd > bet the authors would take pride saying they were 4 stones ahead of the > competition. As a weak bot author, I'd take pride in being able to > beat Gnu Go with 6 stones given to my bot. > ___ > 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] Anchor Player
> Handicap seems to be an integral part of the game of > GO, however I > won't be implementing it right away.Perhaps at a > later time I will > add it. > > When and if the time comes I will solicit > suggestions, as this server is > primarily for the use of developers. for future consideration: chinese handicap might be useful for programs -- as each handicap stone is played, the board is simply going to look better and better. sure, you won't be able to consult an opening library, but it might be interesting to see where your code thinks that the first 4 (for instance) stones on an empty board should go. there are lots of good options, so the play might not be as bad as it sounds. joseki in the hands of anyone, including a computer player, is hard to do correctly. s. Any questions? Get answers on any topic at www.Answers.yahoo.com. Try it now. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Anchor Player
Increasing KOMI is much easier than placing stones, right? Jacques Basaldúa³ñ <[EMAIL PROTECTED]>: >I would like to take part in the 19x19 competition. >I also prefer kyu rating to Elo, but I got the impression that >you were relating kyu rating with handicap games (that is >usually done by human players). > >I think handicap is a bad idea for computers. Handicap >requires human intelligence to understand how the playing >style must be changed. It completely ruins fuseki databases >and may also make josekis that are good under equal play >too slow. Of course, if you pretend to ruin fuseki database >programs, its a good idea. But I think dan/pro level fuseki >is not only legitimate, but probably the best possible fuseki >and it can be played in ultrablitz which preserves computing >time for later moves. The only drawback is 10 Mb of >disk space. Any silly welcome video is heavier than that. > >I suggest, if handicap is implemented, it should be optional. > >Jacques. >___ >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/
Re: [computer-go] Fast Board implementation
> At the time of Your post I've had it already implemented and regarded > it like "my sweet secret" :) I don't know how sweet this secret is, but it does help. I just implemented it in Lazarus and I get about a 20% speedup. That's not bad, but nothing to write home about. To a chess programmer this is rather enormous! I am guessing that the win would be much greater on bigger boards. In principle it would probably be FAR faster, but it adds extra complexity, operations and overhead to executing a move which subtracts some from the savings. The question is: "what is the best way to implement it?" The problem is that you now must track pseudo liberty counts for every chain on the board. This is more complicated obviously. Every time a stone is placed or removed, 4 additional entries must be accessed in order to update the pseudo liberty counts. It's still a good trade-off because the testing for whether a move is a capture or suicide is cheap. I'm reviewing my design now and I think I see some ways to improve. Here is the current data structure (assuming the 9x9 board): 1. A 10x11 board (actually 10x11 plus 1 for diagonal checking.) 0 = empty 1 = white 2 = black 4 = off-board points. 2. Another 10x11 board-like array - if there is a occupied point on the board this array contains the index (hash key) of a "string" data type. 3. A list of string data types (a struct in C): 1. stone count 2. pseudo liberties for the whole string 3. a reference stone. To save time, the list of strings is really more like a hash table, not a proper list. It's a perfect hash table because the keys will never collide. I use the reference stone as the key for each string which is generally the first stone placed in the string. So the hash key computation is just a table lookup and is the only thing the second table is used for. So to summarize, I really have 3 10x11 arrays, one of them is an array of structs in C (actually in D) and is viewed as a hash table. I could pack all of the information into a single array. Here is one possible scheme which fits in 32 bits and accommodates all board sizes: 3 bits to identify white/black/empty/off-board 9 bits for the hash key (the reference stone) 9 bits for pseudo liberty count 9 bits for stone count It's kind of interesting when you think about it. A single array does triple duty as a: 1. Go board. 2. Hash table. 3. lookup table - to get the "hash key" (table index) of the data for the string that occupies this point. The hash table bits in the table are usually irrelevant, it is only valid for the single point that represent the hash table entry for a given string. So this scheme does no list manipulations and has a fixed size in memory. It's compact and I think fast. Is there anything obvious I'm missing that simplifies things? By the way, stone count field is helpful but not necessary. But it's trivial to keep updated and it's convenient. Using the compact representation would slow down some of the operations which are in fast inner loops now, but would probably be a win overall, perhaps a big win because I'm not manipulating several different arrays. So I will also try this compact implementation unless someone has a superior scheme to suggest. - Don On Mon, 2006-12-11 at 20:00 +0100, Łukasz Lew wrote: > At the time of Your post I've had it already implemented and regarded > it like "my sweet secret" :) , so I was expecting that when You > published it everybody will appreciate, and start using. But I guess > it wasn't easy to see benefits. > I wonder how many really good ideas came through this list unnoticed. > > Best Regards, > Lukasz > > > On 12/11/06, House, Jason J. <[EMAIL PROTECTED]> wrote: > > Wow. Did some of my early posts on liberties/chains actually get used > > by someone? Or did the idea of pseudo-liberties and union sets exist > > before my post(s) on the topic? I remember a lot of negative feedback > > on pseudo-liberties at the time of my post. > > > > -Original Message- > > From: [EMAIL PROTECTED] > > [mailto:[EMAIL PROTECTED] On Behalf Of Lukasz Lew > > Sent: Monday, December 11, 2006 1:31 PM > > To: [EMAIL PROTECTED] > > Cc: computer-go > > Subject: Re: [computer-go] Fast Board implementation > > > > Pseudo liberties of a group is a sum of liberties of each stone, > > example: > > > > O > > OXXXO > > OX.XO > > OXXXO > > O > > > > "X" group have 4 pseudo liberties. > > > > If You merge two groups just add pseudo liberties. > > If PL = 0 then group should be removed. > > > > This is simple and sufficient :) > > > > Lukasz > > On 12/11/06, Don Dailey <[EMAIL PROTECTED]> wrote: > > > > > > > > > On Mon, 2006-12-11 at 18:22 +0100, Łukasz Lew wrote: > > > > - pseudo liberties at top of union-set tree > > > > > > > > > Refresh my memory on this. I remember talking about thi
Re: [computer-go] Slow KGS computer Go Tournament
Hi Nick, I'm not going to be ready for such a tournament - but I really want to be. I hope you have another one at a later date. - Don On Thu, 2006-12-14 at 12:49 +, Nick Wedd wrote: > The 2006 Slow KGS computer Go tournament will be next week, starting at > 00:00 on Monday 18th UCT (GMT). It will be a five round Swiss, with > each game taking a full day (i.e. eleven hours fifty minutes each, > sudden death). Each game is scheduled to start at midnight in my UK > timezone, so the five rounds will occupy Monday, Tuesday, Wednesday, > Thursday and Friday. > > With apologies for the short notice - I want to get this done before the > end of the year, so as to at least partly keep to promises made earlier. > You can regard it as a test slow tournament. > > The rules are, 19x19 boards, Chinese rules, 7.5 points komi. Apart from > the long time limits, it will be like the previous KGS bot tournaments > that I have organised. The entrance requirements will be slightly > tighter than for the Open divisions of those, at my discretion - e.g., I > don't want several slightly modified versions of GNU Go playing, but I > will welcome a genuine GNU Go and SlugGo. > > The KGS page for the event is http://www.gokgs.com/tournInfo.jsp?id=255 > The entry instructions, as usual, are at > http://www.weddslist.com/kgs/how/index.html > > Nick ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fast Board implementation
Are you using the union-find algorithm with path compression for joining strings? It's very simple and very fast. http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests The other main thing to consider is reducing branch mispredictions, which (I'm guessing) could very well use more clock cycles on a P4 than performing the actual calculations themselves. I think this is why the next_stone list is faster than using e.g. a recursive algorithm, which involves a lot of if's that cannot be predicted. Compact data I think is unnecessary, although perhaps eliminating the String struct would speed things up a tad. In fact, on a P4, shift operations are slower than L1 cache memory retrievals, so fancy packing of data is not worthwhile. As long as all data fits in the L1 cache it should be max speed. I am working on a program myself, and I will be porting it to assembly at some point; right now I am just experimenting with the algorithm design in C. (Although this happens pretty slowly since I am very busy with work.) I think that this sort of algorithm is perfect for assembly language, where hand-optimization can be much better than compiler optimization. I will let you know how it turns out compared to Lukasz :) At the time of Your post I've had it already implemented and regarded it like "my sweet secret" :) I don't know how sweet this secret is, but it does help. I just implemented it in Lazarus and I get about a 20% speedup. That's not bad, but nothing to write home about. To a chess programmer this is rather enormous! I am guessing that the win would be much greater on bigger boards. In principle it would probably be FAR faster, but it adds extra complexity, operations and overhead to executing a move which subtracts some from the savings. The question is: "what is the best way to implement it?" The problem is that you now must track pseudo liberty counts for every chain on the board. This is more complicated obviously. Every time a stone is placed or removed, 4 additional entries must be accessed in order to update the pseudo liberty counts. It's still a good trade-off because the testing for whether a move is a capture or suicide is cheap. I'm reviewing my design now and I think I see some ways to improve. Here is the current data structure (assuming the 9x9 board): 1. A 10x11 board (actually 10x11 plus 1 for diagonal checking.) 0 = empty 1 = white 2 = black 4 = off-board points. 2. Another 10x11 board-like array - if there is a occupied point on the board this array contains the index (hash key) of a "string" data type. 3. A list of string data types (a struct in C): 1. stone count 2. pseudo liberties for the whole string 3. a reference stone. To save time, the list of strings is really more like a hash table, not a proper list. It's a perfect hash table because the keys will never collide. I use the reference stone as the key for each string which is generally the first stone placed in the string. So the hash key computation is just a table lookup and is the only thing the second table is used for. So to summarize, I really have 3 10x11 arrays, one of them is an array of structs in C (actually in D) and is viewed as a hash table. I could pack all of the information into a single array. Here is one possible scheme which fits in 32 bits and accommodates all board sizes: 3 bits to identify white/black/empty/off-board 9 bits for the hash key (the reference stone) 9 bits for pseudo liberty count 9 bits for stone count It's kind of interesting when you think about it. A single array does triple duty as a: 1. Go board. 2. Hash table. 3. lookup table - to get the "hash key" (table index) of the data for the string that occupies this point. The hash table bits in the table are usually irrelevant, it is only valid for the single point that represent the hash table entry for a given string. So this scheme does no list manipulations and has a fixed size in memory. It's compact and I think fast. Is there anything obvious I'm missing that simplifies things? By the way, stone count field is helpful but not necessary. But it's trivial to keep updated and it's convenient. Using the compact representation would slow down some of the operations which are in fast inner loops now, but would probably be a win overall, perhaps a big win because I'm not manipulating several different arrays. So I will also try this compact implementation unless someone has a superior scheme to suggest. - Don On Mon, 2006-12-11 at 20:00 +0100, Łukasz Lew wrote: At the time of Your post I've had it already implemented and regarded it like "my sweet secret" :) , so I was expecting that when You published it everybody will appreciate, and start using. But I guess it wasn't easy to see benefits. I wonder how many really good ideas came through this list un
Re: [computer-go] Fast Board implementation
On Thu, 2006-12-14 at 22:51 -0500, Luke Gustafson wrote: > Are you using the union-find algorithm with path compression for joining > strings? It's very simple and very fast. > http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests No, but I will check it out and do an implementation based on it. It's very easy for me to completely change the data structure of my program, the class I'm using to represent the board and all the operations on it are just about 4K of D code. > The other main thing to consider is reducing branch mispredictions, which > (I'm guessing) could very well use more clock cycles on a P4 than performing > the actual calculations themselves. I think this is why the next_stone list > is faster than using e.g. a recursive algorithm, which involves a lot of > if's that cannot be predicted. I use a lot of tricks to try to prevent branching at all. A common idiom I use to count a specific thing is to count ALL of them. For example, if I have a big array that has values from 1 to 10, and I want to count the number of 5's, I count everything into an array: int count[10]; foreach( int i; bigarray ) count[i]++; As opposed to: int count = 0; foreach( int i; bigarray ) if (i==5) count++; > Compact data I think is unnecessary, although perhaps eliminating the String > struct would speed things up a tad. In fact, on a P4, shift operations are > slower than L1 cache memory retrievals, so fancy packing of data is not > worthwhile. As long as all data fits in the L1 cache it should be max > speed. I didn't realize this about the P4. I thought bit operations were always fast and easily pipelined. We will see if it makes a difference. It's actually pretty trivial making the changes.I'll give a report. When I get something I like, I will port the tiny class part to C which will link directly in to a D program. I've written whole chess engines in assembler (back in the 80286 days) and I may write the time critical portions of my code in assembler. D has very nice facilities for making this easy. I appreciate the advice - I'll try the union find stuff next, it does look very easy. - Don > I am working on a program myself, and I will be porting it to assembly at > some point; right now I am just experimenting with the algorithm design in > C. (Although this happens pretty slowly since I am very busy with work.) I > think that this sort of algorithm is perfect for assembly language, where > hand-optimization can be much better than compiler optimization. I will let > you know how it turns out compared to Lukasz :) > > >> At the time of Your post I've had it already implemented and regarded > >> it like "my sweet secret" :) > > > > I don't know how sweet this secret is, but it does help. I just > > implemented it in Lazarus and I get about a 20% speedup. That's not > > bad, but nothing to write home about. To a chess programmer this is > > rather enormous! I am guessing that the win would be much greater on > > bigger boards. > > > > In principle it would probably be FAR faster, but it adds extra > > complexity, > > operations and overhead to executing a move which subtracts some from > > the > > savings. > > > > The question is: "what is the best way to implement it?" The problem > > is that you now must track pseudo liberty counts for every chain on > > the board. This is more complicated obviously. > > > > Every time a stone is placed or removed, 4 additional entries must be > > accessed in order to update the pseudo liberty counts. > > > > It's still a good trade-off because the testing for whether a move > > is a capture or suicide is cheap. > > > > I'm reviewing my design now and I think I see some ways to improve. > > > > Here is the current data structure (assuming the 9x9 board): > > > > 1. A 10x11 board (actually 10x11 plus 1 for diagonal checking.) > > 0 = empty > > 1 = white > > 2 = black > > 4 = off-board points. > > > > 2. Another 10x11 board-like array - if there is a occupied point on > > the board this array contains the index (hash key) of a "string" > > data type. > > > > 3. A list of string data types (a struct in C): > >1. stone count > >2. pseudo liberties for the whole string > >3. a reference stone. > > > > To save time, the list of strings is really more like a hash table, > > not a proper list. It's a perfect hash table because the keys will > > never collide. I use the reference stone as the key for each string > > which is generally the first stone placed in the string. So the hash > > key computation is just a table lookup and is the only thing the > > second table is used for. > > > > So to summarize, I really have 3 10x11 arrays, one of them is an array > > of structs in C (actually in D) and is viewed as a hash table. > > > > I could pack all of the information into a single array. Her
RE: [computer-go] Fast Board implementation
Handtalk has a clever trick. He uses the LSB of the string number as the color of the string. Even strings are black and odd strings are white. So he only needs one array for the board which has both color and string number. David > > 1. A 10x11 board (actually 10x11 plus 1 for diagonal > checking.) > > 0 = empty > > 1 = white > > 2 = black > > 4 = off-board points. > > > > 2. Another 10x11 board-like array - if there is a > occupied point on > > the board this array contains the index (hash key) of > a "string" > > data type. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Fast Board implementation
The compressed version was just a little slower than the non-compressed one, just as you predicted. I could possible optimize it to get it closer, but I try the union set stuff next. - Don On Thu, 2006-12-14 at 22:51 -0500, Luke Gustafson wrote: > Are you using the union-find algorithm with path compression for joining > strings? It's very simple and very fast. > http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests > > The other main thing to consider is reducing branch mispredictions, which > (I'm guessing) could very well use more clock cycles on a P4 than performing > the actual calculations themselves. I think this is why the next_stone list > is faster than using e.g. a recursive algorithm, which involves a lot of > if's that cannot be predicted. > > Compact data I think is unnecessary, although perhaps eliminating the String > struct would speed things up a tad. In fact, on a P4, shift operations are > slower than L1 cache memory retrievals, so fancy packing of data is not > worthwhile. As long as all data fits in the L1 cache it should be max > speed. > > I am working on a program myself, and I will be porting it to assembly at > some point; right now I am just experimenting with the algorithm design in > C. (Although this happens pretty slowly since I am very busy with work.) I > think that this sort of algorithm is perfect for assembly language, where > hand-optimization can be much better than compiler optimization. I will let > you know how it turns out compared to Lukasz :) > > >> At the time of Your post I've had it already implemented and regarded > >> it like "my sweet secret" :) > > > > I don't know how sweet this secret is, but it does help. I just > > implemented it in Lazarus and I get about a 20% speedup. That's not > > bad, but nothing to write home about. To a chess programmer this is > > rather enormous! I am guessing that the win would be much greater on > > bigger boards. > > > > In principle it would probably be FAR faster, but it adds extra > > complexity, > > operations and overhead to executing a move which subtracts some from > > the > > savings. > > > > The question is: "what is the best way to implement it?" The problem > > is that you now must track pseudo liberty counts for every chain on > > the board. This is more complicated obviously. > > > > Every time a stone is placed or removed, 4 additional entries must be > > accessed in order to update the pseudo liberty counts. > > > > It's still a good trade-off because the testing for whether a move > > is a capture or suicide is cheap. > > > > I'm reviewing my design now and I think I see some ways to improve. > > > > Here is the current data structure (assuming the 9x9 board): > > > > 1. A 10x11 board (actually 10x11 plus 1 for diagonal checking.) > > 0 = empty > > 1 = white > > 2 = black > > 4 = off-board points. > > > > 2. Another 10x11 board-like array - if there is a occupied point on > > the board this array contains the index (hash key) of a "string" > > data type. > > > > 3. A list of string data types (a struct in C): > >1. stone count > >2. pseudo liberties for the whole string > >3. a reference stone. > > > > To save time, the list of strings is really more like a hash table, > > not a proper list. It's a perfect hash table because the keys will > > never collide. I use the reference stone as the key for each string > > which is generally the first stone placed in the string. So the hash > > key computation is just a table lookup and is the only thing the > > second table is used for. > > > > So to summarize, I really have 3 10x11 arrays, one of them is an array > > of structs in C (actually in D) and is viewed as a hash table. > > > > I could pack all of the information into a single array. Here is one > > possible scheme which fits in 32 bits and accommodates all board sizes: > > > > 3 bits to identify white/black/empty/off-board > > 9 bits for the hash key (the reference stone) > > 9 bits for pseudo liberty count > > 9 bits for stone count > > > > It's kind of interesting when you think about it. A single array does > > triple duty as a: > > > >1. Go board. > >2. Hash table. > >3. lookup table - to get the "hash key" (table index) of the data > > for > > the string that occupies this point. > > > > The hash table bits in the table are usually irrelevant, it is only > > valid for the single point that represent the hash table entry for a > > given string. > > > > So this scheme does no list manipulations and has a fixed size in > > memory. It's compact and I think fast. Is there anything obvious I'm > > missing that simplifies things? > > > > By the way, stone count field is helpful but not necessary. But it's > > trivial to keep updated and it's convenient. > > > > Using the compact representation would slow down some of the > > opera
