Hi i'm looking for some ideas for data structures to use in my creation of
the board game Go. As is i'm looking at using lists of lists and using a
2-D array as well as an efficient interface to those lists. That is the
lists of lists will update the 2-d array upon and changes (ie after a move
is made) and then for the next move for things such as validation (ie
suicide and ko) can be checked straight from the 2-d array and I don't need
to waste time going through lists. Any interesting data structures I should
look into?
Any intelligent thoughts? Speaking of intelligent another issue is the AI
ever done any go AI? got any (I mean any) good notes code etc?
Opinions of the best Go AI agents?
Thanks Krishan
From: Joe Marshall
Subject: Re: i'm writing a yet another GO game
Date:
Message-ID: <65wjwggn.fsf@ccs.neu.edu>
"Krishan Prathapan" <·······@optushome.com.au> writes:
> Hi i'm looking for some ideas for data structures to use in my creation of
> the board game Go. As is i'm looking at using lists of lists and using a
> 2-D array as well as an efficient interface to those lists. That is the
> lists of lists will update the 2-d array upon and changes (ie after a move
> is made) and then for the next move for things such as validation (ie
> suicide and ko) can be checked straight from the 2-d array and I don't need
> to waste time going through lists. Any interesting data structures I should
> look into?
What are the lists for, then?
> Hi i'm looking for some ideas for data structures to use in my creation of
> the board game Go.
Computer Go Bibliography:
http://www.markus-enzenberger.de/compgo_biblio/compgo_biblio.html
Kimmo
--
((lambda (integer) ;; http://www.iki.fi/kt/
(coerce (loop for i upfrom 0 by 8 below (integer-length integer)
collect (code-char (ldb (byte 8 i) integer))) 'string))
100291759904362517251920937783274743691485481194069255743433035)
"Krishan Prathapan" <·······@optushome.com.au> writes:
> Any intelligent thoughts? Speaking of intelligent another issue is the AI
> ever done any go AI? got any (I mean any) good notes code etc?
> Opinions of the best Go AI agents?
http://www.gameai.com/go.html
http://www.reiss.demon.co.uk/webgo/compgo.htm
http://www.britgo.org/gopcres/playit.html
Go for it.
KBK
"Krishan Prathapan" <·······@optushome.com.au> wrote in message news:<·························@news.optusnet.com.au>...
> Hi i'm looking for some ideas for data structures to use in my creation of
> the board game Go.
> ..... .....
> Thanks Krishan
Hello Krishan,
My Springer-Verlag Scheme book had a simple Go playing framework. Let
me know offline if you would like that code.
One of the Go programming pioneers, Zobrist (spelling??) prototyped in
Lisp.
A very good Go program is GNU-Go; my older brother taught me to
play Go when I was 8, and GNU-Go is actually a stronger player
than my brother is :-) GNU-Go is written in C, but I recommend that
you take a good look at it.
-Mark
-- Mark Watson, computer consultant and author
-- Free Web Books and Open Source: www.markwatson.com
-- Live demos of AI and NLP products
From: Mark Dalgarno
Subject: Re: i'm writing a yet another GO game
Date:
Message-ID: <uy99emuqi.fsf@scientia.com>
"Krishan Prathapan" <·······@optushome.com.au> writes:
> Hi i'm looking for some ideas for data structures to use in my creation of
> the board game Go. As is i'm looking at using lists of lists and using a
> 2-D array as well as an efficient interface to those lists.
Some vague thoughts:
I'd consider separate (bit) arrays for black/empty, white/empty
black/white. This may help if you plan to use any pattern matching.
Groups could be modelled as CLOS instances.
Not sure what the lists are required for.
Mark
"Krishan Prathapan" <·······@optushome.com.au> writes:
>
> Hi i'm looking for some ideas for data structures to use in my creation of
> the board game Go. As is i'm looking at using lists of lists and using a
> 2-D array as well as an efficient interface to those lists. That is the
> lists of lists will update the 2-d array upon and changes (ie after a move
> is made) and then for the next move for things such as validation (ie
> suicide and ko) can be checked straight from the 2-d array and I don't need
> to waste time going through lists. Any interesting data structures I should
> look into?
>
> Any intelligent thoughts? Speaking of intelligent another issue is the AI
> ever done any go AI? got any (I mean any) good notes code etc?
> Opinions of the best Go AI agents?
>
I am myself ignorant in these matters, but I do remember that Peter
Norvig in his book _Paradigms of Artificial Intelligence Programming:
Case Studies in Common Lisp_ has a chapter in which he describes the full
process of writing a Go game and even implements a simple version with
exercises that expand it to less-simple version. As can be guessed from
the title of the book, there is also detailed description of the AI
involved.
The URL to the web-site is given below, if you can't buy the book, you can
at least download the code and see if you get any ideas from that:
http://www.norvig.com/paip.html
Hope this helps!
--
Richard Krushelnitskiy "I know not with what weapons World War III will
rkrush (at) gmx.net be fought, but World War IV will be fought with
http://rkrush.cjb.net sticks and stones." -- Albert Einstein
Richard Krush wrote:
> I am myself ignorant in these matters, but I do remember that Peter
> Norvig in his book _Paradigms of Artificial Intelligence Programming:
> Case Studies in Common Lisp_ has a chapter in which he describes the full
> process of writing a Go game and even implements a simple version with
> exercises that expand it to less-simple version. As can be guessed from
> the title of the book, there is also detailed description of the AI
> involved.
Unfortunately, what you remember is untrue. There is
a (very good) chapter about a program to play Othello.
PAIP is a fantastic book, but if you look up "go" in
the index the only one you'll find is the one that occurs
inside a tagbody. :-)
--
Gareth McCaughan ················@pobox.com
.sig under construc
Krishan Prathapan wrote:
> Hi i'm looking for some ideas for data structures to use in my creation of
> the board game Go. As is i'm looking at using lists of lists and using a
> 2-D array as well as an efficient interface to those lists. That is the
> lists of lists will update the 2-d array upon and changes (ie after a move
> is made) and then for the next move for things such as validation (ie
> suicide and ko) can be checked straight from the 2-d array and I don't
> need
> to waste time going through lists. Any interesting data structures I
> should look into?
>
> Any intelligent thoughts? Speaking of intelligent another issue is the AI
> ever done any go AI? got any (I mean any) good notes code etc?
> Opinions of the best Go AI agents?
>
> Thanks Krishan
GO is a very active research field in AI. There was even a multi-page
article in NYT about this a couple of months ago.
As to your question, I think a good data structure choice to represent the
board is a bit array with 2 bits per field. For instance, you can use the
first bit to show whether the field is empty, and the second field to show
the color of the species on that field (The second bit will be nonsensical
if the field is unoccupied, of course).
HTH
Oleg