Author |
Topic: Board Representation (Read 8134 times) |
|
doublep
Forum Guru
Badger author
Gender: 
Posts: 82
|
 |
Board Representation
« on: Oct 16th, 2005, 4:09pm » |
 Quote  Modify
|
Discussion here seems to concentrate on important things, like search algorithms and evaluation. Why not talk about something more to the ground?
I wonder which board representation is more popular among Arimaa bot authors. I'm aware of three standard schemes: a collection of bitmaps, a two-dimensional array or a single-dimension array (or there could be not one but a few arrays.) Which one do you use and why? Maybe you use something completely different? Do you prefer several arrays of primitive types or an array of objects?
Aami-ra uses two single-dimension arrays. The main array stores actual board situation: each element (of type `char') contains a code for a piece, an empty square or an off-board code. Second array (also `char') contains auxiliary data that allows to quickly determine if a piece is frozen and how many neighbors of different kinds it has. We prefer single-dimension arrays since they are more efficient (you only pass one index around) and actually easier to work with, once you get used to. Arrays of objects are usually less efficient too, because CPU memory caching suffers. Anyway, in our case the object would have been just two `char's if we had used them.
Both arrays are updated incrementally. Move/step undoing is performed using a change stack: whenever a value in either of the two arrays changes, Aami-ra stores the old value together with its address. Undoing then simply consists of copying the old values back.
|
|
 IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #1 on: Oct 16th, 2005, 4:44pm » |
Quote Modify
|
I never gave it too much thought. I just assumed everybody used 64-bit bitmaps.
It's memory efficient and you just use fast bitwise operations.
I thought using arrays would be much slower, but your solution of using a second array keeping auxiliar data seems like a clever solution.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Board Representation
« Reply #2 on: Oct 16th, 2005, 6:14pm » |
Quote Modify
|
Clueless uses 64 bit bitmaps.
The board is stored as an array of 12 bit maps plus an int for the number of steps used in the game so far.
Last year's move representation was a 4 step move compressed into a 64 bit long.
This year a move is stored in the same format as the board. The makemove routine xor's the current position with the move to get the new position. Nothing is done incrementally.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Board Representation
« Reply #3 on: Oct 16th, 2005, 9:42pm » |
Quote Modify
|
I suppose I should let Fotland speak for himself, but he seems not to be active at the moment. I seem to recall him telling me that Bomb uses bitmaps for speed.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #4 on: Oct 17th, 2005, 12:22am » |
Quote Modify
|
Gnobby uses the bitmap representation used by Don in the sample bot (because I don't know enough to better it).
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Board Representation
« Reply #5 on: Oct 17th, 2005, 3:42pm » |
Quote Modify
|
We use arrays since they seem to easier to work with in tactical reading (we have unfinished 4 steps goal lookahead and directed search for trapping moves intended to improve move ordering.) Basically, each board square is described with just two values, which you don't even need to extract from a bitmask. This approach may be more efficient in some cases, for instance the check if a piece is frozen is a single comparison. Additionally, our GNU Go experience might have played its role 
|
|
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: Board Representation
« Reply #6 on: Oct 17th, 2005, 4:33pm » |
Quote Modify
|
my first bot used VB (no comment, it was a first try ever) arrays, but after I read the sample bot I learned C and used bitmaps ...
suddenly everything became faster (and move generation as well as evaluation much easier)
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Board Representation
« Reply #7 on: Oct 18th, 2005, 2:40pm » |
Quote Modify
|
on Oct 17th, 2005, 4:33pm, PMertens wrote:my first bot used VB (no comment, it was a first try ever) arrays, but after I read the sample bot I learned C and used bitmaps ...
suddenly everything became faster (and move generation as well as evaluation much easier) |
|
Well, in this case the speedup is of course because of changing the language. No matter how you do it in C, it will be faster than VB. Actually, C and C++ are you best languages if you want something to be _real_ fast.
|
|
IP Logged |
|
|
|
ntroncos
Forum Junior Member
Weiser's trainer
Gender:
Posts: 9
|
|
Re: Board Representation
« Reply #8 on: Nov 13th, 2005, 2:16pm » |
Quote Modify
|
It seems that 64 bitmap is the common usage. By the way this is quite good and they will benifit from 64bit procesor. With 32bit Procesors we need 2 (normaly) instructions to handle the bitmap, with the new 64bit this is reduced to 1 (normaly), hence we see a speed enhancement.
Normaly what you should try is to avoid is a representation where you store to much zeros, bitmap in this case. But the tradeof of this representation is that we have a vision of the board as a whole, be sides the space overhead for each zero is only 1bit.
Never the less other other representation should be explored, maybe there is a whole new, more eficient representation waiting to be implemented  .
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Board Representation
« Reply #9 on: May 17th, 2006, 6:59am » |
Quote Modify
|
Can someone help me understand bitboards? ... and how the Sample C bot implements it?
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Board Representation
« Reply #10 on: May 17th, 2006, 8:26am » |
Quote Modify
|
http://en.wikipedia.org/wiki/Bitboard is a decent description.
The sample bot also defines some Arimaa specific bitboards, like trap squares and squares adjacent to trap squares etc.
|
|
IP Logged |
|
|
|
unic
Forum Guru
Arimaa player #1878
Gender:
Posts: 63
|
|
Re: Board Representation
« Reply #11 on: May 17th, 2006, 9:29am » |
Quote Modify
|
Fairy represents the board as an array[100]. I find it easier to understand and to write evaluation for than a bitboard - might be slower in execution, but quicker in development for me.
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #12 on: May 17th, 2006, 10:12pm » |
Quote Modify
|
on May 17th, 2006, 9:29am, unic wrote:| Fairy represents the board as an array[100]. I find it easier to understand and to write evaluation for than a bitboard - might be slower in execution, but quicker in development for me. |
|
You should rethink that, i did some tests a while ago, and it really is a LOT slower.
Maybe you should write a couple of functions to manipulate the bitboard, so you write the bitwise operations only once.
|
| « Last Edit: May 17th, 2006, 10:13pm by nbarriga » |
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Board Representation
« Reply #13 on: May 18th, 2006, 2:42am » |
Quote Modify
|
Is it clear cut? ... I didn't think it was when reading the wikipedia article and also this:
http://www.cis.uab.edu/hyatt/boardrep.html
It seemed to me that the two links are saying that bitboards may be better, but not by much (if both methods are done properly)? Although there may be a significant difference with a 64 bit processor?
I know next to nothing about both methods, and so I don't know what I'm talking about ... I'm interested in you're opinions.
From what I've read so far, bitboards seem more logical to me, but if I use them, it may slow my bot development down quite a bit while I get to grips with bitboards. At the moment, I'm just wondering if I spent that time on developing an effective pruning strategy instead, that I'd have a faster bot in the end. I'm wondering this as both articles warn that bitboards take a long time to get to grips with, and that any bitboard code must be well-commented in order to develop more code and to debug it too ... I'm not sure that the sample C bot is all that well-commented?
|
| « Last Edit: May 18th, 2006, 2:51am by Swynndla » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #14 on: May 18th, 2006, 3:08am » |
Quote Modify
|
I learnt bitboards from the sample code. I don't think they're *that* hard to get to grips with.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print