Re: [computer-go] Former Deep Blue Research working on Go
On Thu, 2007-10-11 at 18:37 -0400, Chris Fant wrote: > Someone already did: Stone eater. > > On 10/11/07, terry mcintyre <[EMAIL PROTECTED]> wrote: > > > > Erik, > > > > It would be great to see Steenvreter on the 9x9 cgos server. BTW, can you > > translate "Steenvreter" for us English speakers? Thanks! "Eater" is a bit too weak, IMHO. "Stone gobbler" or "stone muncher" seems more appropriate. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] SGF parsing
On Mon, 2007-07-09 at 12:46 -0400, Joshua Shriver wrote: > Ok found some KGS games, and they make a lot more sense. With the > specification I can see what all of the OT, AP, TM, FF, etc commads > are. However I don't understand the way it sets the location, so far > nothing I've seen describes it. > > ;B[kr] for example. > I thought Go boards used A..x 1..y notation. Perhaps I'm wrong. SGF uses a different coordinate system (making it easier to make mistakes ...) It is all in the Fine Manual: http://www.red-bean.com/sgf/go.html#properties Read it. SGF is surprisingly easy to parse; the only "special" tokens the parser needs to recognize are ()[]; ( \n and newline escaping add some complexity, but can _initially_ be ignored.) > -Josh > > On 7/9/07, Joshua Shriver <[EMAIL PROTECTED]> wrote: > > Do you have a good example of a regular Go game in sgf? > > A lot of the examples I found on the SGF spec site seem confusing, and > > not sure if they're even for Go or backgammon, etc. Ignore everything except for GM[1] (= go), and the generic part. For simple sgf, (without variations or game collections) you can create a parser in a few hours. This will probably include reading the manual and understanding the format, too. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] transition to the new CGOS
On Wed, 2007-04-04 at 15:25 +0200, Unknown wrote: > either, would have preferred periods or semicolons.) Oops. I meant colons, of course. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] transition to the new CGOS
On Tue, 2007-04-03 at 23:10 -0400, Don Dailey wrote: > On Tue, 2007-04-03 at 23:01 -0400, Don Dailey wrote: > > > > cgos_player color name > > example: cgos_player white Lazarus > > > > cgos_elo color elo_rating > > example: cgos_elo white 1739? > > > > and since cgos does use kyu/dan, I don't want to specify > > a command at this time, but if I do it would likely be: > > > >cgos_rank color rank > Also, I forgot that I want to be able to specify the cgos > game number, so I would also add this command: > > cgos_gameid some_integer > > Instead of polluting the namespace with a lot of domain-specific set/get commands, you could wrap them all into one 'umbrella' command, eg 'info' cgos-info opponent_name Aunt Maud cgos-info opponent_rank 10k cgos-info game_date 20070304132355 cgos-info game_name [EMAIL PROTECTED] cgos-info pressure 1013hPa This naming for games is similar to what SMTP does with email, and will allow you to run multiple instances of the server. > It is likely there will be more than 1 instance of the > CGOS server (perhaps 1 for different board sizes) but I > hesitate to try to distiguish between them with more GTP > commands. So I would leave it up to the program authors > to keep track of which server a game Id belongs to. > > It's of course possible to send this all in one uber > command: > > cgos_game_info gameID white_name white_elo black_name black_elo > > but it does not seem to be in the spirit of GTP. > According to the GTP-draft, you are supposed to use hyphens, not underscores to prefix your private extensions. (I don't like them either, would have preferred periods or semicolons.) HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] documentation for the IGS protocol ?
On Thu, 2007-02-22 at 17:50 +, Stuart A. Yeates wrote: > Does anyone know of a document outlining the IGS protocol? > > There are a number of programs and servers which support the IGS > protocol, including the IGS server. I am trying write a tool to > interact with these servers and would prefer not to have to reverse > engineer the protocol from the programs, especially since most > implement only a very small handful of commands. This one looks reasonable complete and original (though a bit verbose): http://www.koders.com/noncode/fid2C78D24147B76E1CF1196C20428DC7BC62715F38.aspx Enjoy ;-) AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] documentation for the IGS protocol ?
On Thu, 2007-02-22 at 17:50 +, Stuart A. Yeates wrote: > Does anyone know of a document outlining the IGS protocol? > > There are a number of programs and servers which support the IGS > protocol, including the IGS server. I am trying write a tool to I'm (still) working on one, too. (Basically for NNGS, but should work on IGS, too) I have been googling for "protocol.txt", but it seems to have vanished. (that's what the "server wars" were all about) I'll see if I can dig it up somewhere. In the mean time: reversed engineering is certainly the way to go ... Check: http://computer-go.org/pipermail/computer-go/2006-July/005662.html NB Yesterday, I released NNGS-1.1.21. ( http://sourceforge.net/projects/nngs/ ) Might come in handy for testing purposes. Dave Dyer had a NNGS clone installed at boardspace.net, too, some 1-2 years ago. I have one running on my home machine at nngs.ziar.net 9696 Recently, a russian guy set up mastergo.ru 9696 , but he probably does not like too much automated play (without notice). Linkspam: I have a copy of the archives of this mailing list (from 1992 or so) set up at: http://nngs.ziar.net/cgml/ HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Fwd: [computer-go] Zobrist hashing with easy transformation comparison
On Wed, 2007-02-14 at 10:45 +0100, Erik van der Werf wrote:
> > From: Nic Schraudolph <[EMAIL PROTECTED]>
> > Date: 12 February 2007 10:45:50 GMT+11:00
> > To: computer-go
> > Subject: Re: [computer-go] Zobrist hashing with easy transformation
> > comparison
> >
> >> did you read Anti Huima's paper? The idea looks similar, but
> >> unfortunately it does not work. I provided a proof of the defect
> >> on this list (end of 2002 if I remember well). It's not that easy
> >> to get a working scheme. In fact there is only one combination
> >> with 8 chunks of data. In 2002 I exchanged a lot of email with
> >> Nici Schraudolph, and we found the right scheme. We wanted to
> >> write a paper, but we did not (it takes time, and I had not that
> >> much time - mathematic and computer go is just a hobby for me).
> >
> > The bad news: a colleague here has proven that no standard
> > segmented Zobrist hash can work in less than 8 chunks - and that's
> > without color symmetry. That makes 16 chunks with color, not very
> > attractive!
> >
> > The good news: I've developed a defect-free scheme including color
> > symmetry that works in only 6 chunks, and has a very efficient way
> > to compute a canonical hash (that is: without having to compute all
> > 8/16 candidates). No contradiction to the above proof as it's not a
> > standard Zobrist hash. This is provably the minimal scheme.
> >
> > Do sit on me - I really need to finish writing this up! In the
> > meantime, as long as you don't need color, the 8-chunk scheme Erik
> > posted works fine. Nick's (if I understood it correctly - I took
> > r_x, r_y, r_xy to mean reflection about vertical, horizontal, and
> > diagonal axis, respectively) has a problem though: for all
> > positions p, r_x(r_xy(r_x(r_xy(p == p. Huima's scheme can't
> > work because it's really a 4-chunk scheme doubled up for color
> > symmetry.
Me too:
#define T_X(h) \
( (((h) & 0x) >>1 ) \
| (((h) & 0x) <<1 ) \
)
/* { 2,3,0,1,6,7,4,3} */
#define T_Y(h) \
( ( ((h) & 0x) >>2 ) \
| ( ((h) & 0x) <<2 ) \
)
/* { 3,1,2,0,7,5,6,4} */
#define T_P(h) \
( ( ((h) & 0x) ) \
| ( ((h) & 0x) <<3 ) \
| ( ((h) & 0x) >>3 ) \
)
/* { 0,2,1,3,4,6,5,7} */
#define T_Q(h) \
( ( ((h) & 0x) ) \
| ( ((h) & 0x) <<1 ) \
| ( ((h) & 0x) >>1 ) \
)
#include
#include
int main()
{
unsigned long val0, val1, val2, val3;
unsigned aa,bb,cc;
unsigned at,bt;
char * legend[4] = { "(X)" ,"(Y)" ,"(P)" , "(Q)" };
val0 = 0x12345678;
at = bt = 4;
for (aa=0; aa <4; aa++ ) {
switch(aa) {
case 0:val1 = T_X(val0); break;
case 1:val1 = T_Y(val0); break;
case 2:val1 = T_P(val0); break;
case 3:val1 = T_Q(val0); break;
}
for (bb=0; bb <4; bb++ ) {
if (bb==aa) continue;
if (bb < bt) at =4;
switch(bb) {
case 0:val2 = T_X(val1); break;
case 1:val2 = T_Y(val1); break;
case 2:val2 = T_P(val1); break;
case 3:val2 = T_Q(val1); break;
}
for (cc=0; cc <4; cc++ ) {
if (cc==bb) continue;
switch(cc) {
case 0:val3 = T_X(val2); break;
case 1:val3 = T_Y(val2); break;
case 2:val3 = T_P(val2); break;
case 3:val3 = T_Q(val2); break;
}
if (aa!=at) fprintf(stdout,"%8lx -%s-> %8lx"
,val0,legend[aa],val1);
else fprintf(stdout," -%s-> "
,legend[aa], val1);
if (bb!=bt) fprintf(stdout," -%s-> %8lx"
, legend[bb],val2);
else fprintf(stdout," -%s-> "
, legend[bb]);
fprintf(stdout," -%s-> %8lx\n",legend[cc],val3);
at = aa; bt = bb; ;
}
}
}
exit(0);
}
/**
Legend: T_X() and T_Y() transform the hash value, when flipping the X
and Y coordinates; T_P() and T_Q()
flipping over the diagonals. The rest is trivial.
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:58 -0800, steve uurtamo wrote: > > > > tranforms as the "cannonical" key. In most cases 8 positions will > > > > > > IIRC, choosing the smallest may cause some unwanted effects. Not sure... > > > > It's not quite as good as using 64 bits free and clear because there is > > compression towards the lower bits. > > i must be missing something here -- the whole point of canonicalization is > that you want to be able to recognize a 'book line' when it appears, even if > you have to rotate and/or reflect your board in order to match the book line, > right? you save 8x the space by only stashing one copy of the book line, > and by using some canonical version of the hash key and doing 8 transforms > on every board position when the game move is less than the longest known > line length, or somesuch. Yes. But Don's confusion was independent of the canonicalization, though it was probably caused by it. > > if you're only storing a few hundred lines, or a few thousand, why not store > all 8 copies? then it's just a lookup with no extra transforms. > Sure. It is just an engineering decision: do you want to waste the RAM-space, or only the CPU-time. For a few hundred records, optimising for space is probably not worth the effort. For a larger fuseki / joseki /pattern book, it probably is. CPU is cheaper than RAM, and a cache miss is worth tens of instructions. It depends. (though "travel light" is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) BTW: once you choose the /8 gain by implementing canonicalization, you'll probably want to implement /2 color-swaps, too. (but this will only be profitable for libraries, not for 'history' such as in Don's case.) HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:55 -0500, Don Dailey wrote: > The children of one parent almost certainly will have different 64 bit > keys than the children of the other parent. Not if the parents collide. (apart from symmetry/canonical considerations): if H(A)==H(B), then after applying move 'm' -->> H(A) ^ some_constant == H(B) ^ some_constant So if you use Zobrist[move] as a some_constant value (which I understand you do), then if both parent moves A,B have a successor move (coordinate+color) in common, the resulting hashes for the successors will also collide. > I don't see how you can conclude that I'm not getting much extra > safety. > > By the way, I use zobrist hashing with XOR to generate these keys and > do all the rotations - choosing the smallest key of the 8 possible > tranforms as the "cannonical" key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... > hash to this same key but the positions are symetrically equivalent. You mean: _after the canonisation_ they hash to the same key. > > You could of course look at it backwards, what are the odds that > 2 child keys will match? If you can find 2 that do match, what are For two children of the same parent, this is (given an adequate Zobrist table) impossible. After canonisation, this is unclear (but can be guaranteed by careful construction of the Zobrist tables). > the odds that their parents will also have a matching key? I > think this is very unlikely. I think this is just as likely as the other way around, since the ^ is its own inverse function. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Wed, 2007-02-07 at 16:28 -0500, Don Dailey wrote:
> On Wed, 2007-02-07 at 16:17 -0500, Don Dailey wrote:
> > I have a hash funciton that creates a 64 bit "cannonical" hash of
> > the position. The same hash is produced after a rotation for
Most people do incremental hashing, which is cheaper even if 8(16)
symmetric copies are to be maintained. YMMV.
> > example. A book entry is a record with 3 fields, a priority
> > value (how many times the deep search selected this position),
> > the cannonical hash of the parent position and the cannonical
> > hash of the posiiton AFTER the move is played.This makes
> > collision very unlikely.The cannonical hash takes into
> > consideration simple ko, so if a ko is possible it will hash
> > differently than the same position where the ko is illegal.
>
> Here is some more detail to make this clearer:
>
Since you seem to be replying to yourself, I'll add some comments.
> typedef struct
typedef is useless here, IMO.
(but this is a matter of style, I agree)
> {
> intcount; // number of times this position/response seen
> (priority)
Warning: alignment will cause this struct to be 3* sizeof(U64), wastong
32 bits.
Warning2: if the count is never negative, "unsigned" would be more
appropiate.
> u64key; // cannonical position key
> u64resp;// resulting cannonical position
Warning: you are wasting (64- ~9) bits here, since the response stems
from a set of 361+1 choices, maximal.
(this would be different if you intend to search backwards in the
tree/dag, with 'resp' as search key)
> } book_entry;
That could reduce your struct to:
struct booklet {
u64 key;
u32 count;
u16 move;
/* you *could* store the de-canonilisation-info here: */
u16 spare;
};
, which will take only 2*64 bits.
>
> These book_entry records are stored in a file and I keep them
> sorted. So the procedure to see if there is a book move is
Sorted on key? (Keep them sorted == resort periodically)
In that case, some kind of hashing would seem more appropiate, IMHO
> to binary search the file on the parent position key,
> collect all of these records together (making sure there is a
> legal move which leads to the cannonical response key) and then
You are not clear here.
Is there only a one-move-step between key and resp ?
Why not store the move in the first place ? (instead of the resulting
hash)
> choose one of the available moves in proportion to the
> priority values (the count field.)
HTH,
AvK
___
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!
On Fri, 2007-01-12 at 15:51 +, Mehdi Ahmadi wrote: > Hello & thank in advance for any interests/ responses. > > I'm unfortunately (or not) doing a dissertation as part of my final year > project (undergraduate) on the game of Go. The exact title is: "Can the game > of go be solved? Analysis of computational methodologies for go." And I have > included my overall objectives below. > > I have many works from different people on different aspects of Computer Go > which would make for great inclusion at different parts - but overall I am > still gravely struggling. In reviewing some of these my greatest difficulty > is in understanding exactly how say Monte-Carlo-UCT or even Alpha-Beta > testing (pruning, etc) occur so as to be able to give a simplified depiction > (illustrated or otherwise) of the process. Can this be done without having > to go through the source code of say something like GNU Go? > > Also another difficulty I've had is in trying to get further information on > the commonly referred top ranking packages, Handtalk, Go++, Many Faces of > Go, etc due to their commercial nature? (the only thing I've been able to > find which is a bit outdated: > http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html). If they still exist online, most of these papers are suggested reading, IMHO WRT classic methods (alpha-beta, evaluation, Zobrist hashing, etc) a lot of material can be found in computer-chess publications. Another source of links can be found at Markus Enzenberger's online bibliography: http://www.cs.ualberta.ca/~emarkus/compgo_biblio/ Most of the computer go authors have posted on this mailing list, and discussed their views and methods, and the design of their programs. The archive of this mailinglist can be found at: http://computer-go.org/pipermail/computer-go/ This archive starts at approx 2003. I have an archive of older stuff (1993-) from this mailinglist stored on my personal website: http://nngs.ziar.net/cgml/ HTH, AvK ___ 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
On Thu, 2006-11-30 at 14:44 -0800, David Doshay wrote: > This is not my experience at all. > > SlugGo was first written by a graduate student with data structures > that made sense to them, but not to me. I rewrote it to use > completely different data structures but with exactly the same > algorithm. It took less than half the time to run, and play was at > exactly the same level because it was move for move identical. Data > structures can have tremendous effect upon speed. > > Also, my data shows that if I doubled the time allowed for playing, > thus "using" the time gained from faster execution for doing deeper > lookahead, the results did not improve, but actually got worse. > To me, this just seems like horizon-effect in disguise. Once you exhaust your ability to evaluate, you cannot see through the fog. The horizon is dictated by the inability to evaluate correctly. (try fuzzing up the evaluation results by 0.01-1 stone just by adding some noise, to get my point. You will see the horizon come closer) Using multiple instances of gnugo to do the evaluation for you, still sticks you to the (#1) minimax+evaluation model, even if you apply the slave-gnugo processes only for "local" problems (not mentioning interactions, or how to identify subproblems) Having slave processes to do your tsumego- or MC-evaluations for you, still keeps you dependent on their evaluation noise. Adding CPU's wont help to beat the noise, IMHO. It just pushes your horizon upto the point where the fog hits you. This is the point where I would like to introduce a paradigm shift. But I cannot invent one, presently. HTH, AvK (#1) by "minimax", I mean minimax-variants, including alpha-beta. They are all the same. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
