Author |
Topic: Board Representation (Read 7861 times) |
|
BlackKnight
Forum Guru
Arimaa player #695
Gender: 
Posts: 98
|
 |
Re: Board Representation
« Reply #15 on: May 18th, 2006, 3:37am » |
 Quote  Modify
|
I think it also helps a lot to write down the following:
// The squares on the board (looking from Gold's side) have the indices
// (within the bitstring):
// 0 1 2 3 4 5 6 7
// 8 9 10 11 12 13 14 15
// 16 17 18 19 20 21 22 23
// 24 25 26 27 28 29 30 31
// 32 33 34 35 36 37 38 39
// 40 41 42 43 44 45 46 47
// 48 49 50 51 52 53 54 55
// 56 57 58 59 60 61 62 63
// And the bitstring is numbered 63 62 61 ... 2 1 0.
Then you can easily get the following constants:
#define A_FILE 0x0101010101010101ULL
#define B_FILE 0x0202020202020202ULL
#define C_FILE 0x0404040404040404ULL
#define D_FILE 0x0808080808080808ULL
#define E_FILE 0x1010101010101010ULL
#define F_FILE 0x2020202020202020ULL
#define G_FILE 0x4040404040404040ULL
#define H_FILE 0x8080808080808080ULL
#define RANK_1 0xff00000000000000ULL
#define RANK_2 0x00ff000000000000ULL
#define RANK_3 0x0000ff0000000000ULL
#define RANK_4 0x000000ff00000000ULL
#define RANK_5 0x00000000ff000000ULL
#define RANK_6 0x0000000000ff0000ULL
#define RANK_7 0x000000000000ff00ULL
#define RANK_8 0x00000000000000ffULL
#define LEFT_SIDE 0x0f0f0f0f0f0f0f0fULL // a, b, c, d
#define RIGHT_SIDE 0xf0f0f0f0f0f0f0f0ULL // e, f, g, h
#define TRAPS 0x0000240000240000ULL
#define TRAPGUARDS 0x00245a24245a2400ULL
#define RING0 0x0000001818000000ULL // same as small center
#define RING1 0x00003c24243c0000ULL
#define RING2 0x007e424242427e00ULL
#define RING3 0xff818181818181ffULL // edges
|
|
 IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #16 on: May 19th, 2006, 11:52pm » |
Quote Modify
|
on May 18th, 2006, 2:42am, Swynndla wrote:| I'm not sure that the sample C bot is all that well-commented? |
|
Well, with ntroncos we may contribute a bit on that. We are giving his students an assignment, consisting on understanding the sample C bot, and commenting using doxygen style. I think in about a month we may publish here the best commented program of the class.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Board Representation
« Reply #17 on: May 20th, 2006, 6:49am » |
Quote Modify
|
I'm getting a lot of help ... thanks to all your posts!
on May 19th, 2006, 11:52pm, nbarriga wrote:
Well, with ntroncos we may contribute a bit on that. We are giving his students an assignment, consisting on understanding the sample C bot, and commenting using doxygen style. I think in about a month we may publish here the best commented program of the class.
|
|
Nice! ... I look forward to it  What course are the students studying?
BlackKnight, thanks for those lines ... why is the board numbered from a8 instead of a1?
|
| « Last Edit: May 20th, 2006, 7:06am by Swynndla » |
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #18 on: May 20th, 2006, 11:26am » |
Quote Modify
|
on May 20th, 2006, 6:49am, Swynndla wrote:| Nice! ... I look forward to it What course are the students studying? |
|
It's a second year course called Programming Workshop, where they learn programming good practices, and some tools. first they are introduced to the all the dark corners of C , then some tools like gdb, autotools, doxygen.
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #19 on: May 25th, 2006, 9:06pm » |
Quote Modify
|
I just made a simple test to find out if 64 bit CPUs are worth it. I used bot_SampleC compiled using gcc 4.1.0 with -O4, searching 10 steps, on the following position:
5w
+-----------------+
8| r r r r r r r |
7| h d c m h |
6| X c d |
5| e E r |
4| |
3| X X |
2| H D C M R C D H |
1| R R R R R R R |
+-----------------+
a b c d e f g h
(sorry for the ugly board, i just copy and paste the matchMove file)
One PC, an athlonXP 2600+ clocked at 1900Mhz with 512kb L2 cache, i compiled with -march=athlon-xp. The other, a Sempron64 2800+ clocked at 1600Mhz with 256kb L2 cache, compiled with -march=athlon64
Results from 3 consecutive runs:
XP:
real 0m13.628s
user 0m13.461s
sys 0m0.152s
real 0m11.492s
user 0m11.353s
sys 0m0.116s
real 0m11.222s
user 0m11.025s
sys 0m0.184s
------------------------------------
and Sempron64:
real 0m7.916s
user 0m7.792s
sys 0m0.048s
real 0m8.431s
user 0m8.217s
sys 0m0.052s
real 0m9.581s
user 0m9.425s
sys 0m0.056s
------------------------------
If would be nice if someone not using bitboards could send me his bot compiled for the two different architectures to run the same test.
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: Board Representation
« Reply #20 on: May 25th, 2006, 9:26pm » |
Quote Modify
|
Is there any translation from chinese to english of this post ?
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Board Representation
« Reply #21 on: May 25th, 2006, 9:32pm » |
Quote Modify
|
Checking through my notes, here are some results of a perft using clueless's makemove/undo. They are all pure bitboard methods.
This is on an AMD64 2.2Ghz
The java and c versions are as close to the same code as I could make them.
java32 3719 Knps
java64 13791 Knps
gcc64 23065 Knps
|
|
IP Logged |
|
|
|
unic
Forum Guru
Arimaa player #1878
Gender:
Posts: 63
|
|
Re: Board Representation
« Reply #22 on: May 25th, 2006, 9:35pm » |
Quote Modify
|
I offered in the chat earlier today to upload a non-bitboard sample bot in C (i.e. a somewhat cleaned-up and simplified version of Fairy). I was hoping to get around to doing that during the weekend... I'll post once I have it done.
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #23 on: May 25th, 2006, 11:15pm » |
Quote Modify
|
on May 25th, 2006, 9:26pm, chessandgo wrote:| Is there any translation from chinese to english of this post ? |
|
Yes, the athlon XP averaged about 12 seconds, while the sempron 64 averaged about 8.5 seconds on analizing 10 steps from the move i gave them.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Board Representation
« Reply #24 on: May 27th, 2006, 8:10pm » |
Quote Modify
|
nbarriga, I'm looking forward to your results of testing a version of Fairy on the 32 and 64 bit cpu's
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #25 on: May 28th, 2006, 1:05pm » |
Quote Modify
|
Ok, i run Fairy_light, with the same position as the earlier test:
XP:
real 0m44.878s
user 0m43.911s
sys 0m0.824s
real 0m44.707s
user 0m43.791s
sys 0m0.748s
real 0m45.078s
user 0m43.819s
sys 0m0.792s
Sempron64:
real 0m42.045s
user 0m40.383s
sys 0m0.420s
real 0m43.482s
user 0m41.447s
sys 0m0.524s
real 0m42.849s
user 0m41.307s
sys 0m0.476s
|
|
IP Logged |
|
|
|
nbarriga
Forum Guru
Almost retired Bot Developer
Gender:
Posts: 119
|
|
Re: Board Representation
« Reply #26 on: May 28th, 2006, 1:09pm » |
Quote Modify
|
If someone has a bot that uses many threads or processes, i can test it in an athlon 64 dual-core i have access to.
|
|
IP Logged |
|
|
|
Swynndla
Forum Guru
Arimaa player #1821
Posts: 235
|
|
Re: Board Representation
« Reply #27 on: May 28th, 2006, 9:23pm » |
Quote Modify
|
So this is hard proof of the theory that 64 bit cpu's are free speed upgrades for bitboards, while not doing a lot for non-bitboards! ...
http://www.cis.uab.edu/hyatt/bitmaps.html ... Quote:| for new 64 bit architectures such as the Intel Merced processor, bitmaps make a great deal of sense, because bitmaps take maximum advantage of internal processor register and bus size. For example, most of the normal bitmap operations (AND, OR, XOR, shift, and so forth) take at least two instructions on a 32 bit machine, one for each half of the 64 bit bitmap. On a 64 bit architecture, with no clock speed change at all, these operations run twice as fast, because they now require only one instruction to perform them. That is a performance gain that can not be overlooked, because it is completely free. |
|
and http://www.cis.uab.edu/hyatt/boardrep.html ... Quote:| It will see immediate improvement on 64-bit machines while the offset programs will not, because they have no need for 64-bit integers. |
|
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Board Representation
« Reply #28 on: Aug 14th, 2006, 10:34pm » |
Quote Modify
|
bomb uses bitboads. bmap is a 64-bit bitmap class with many member functions for and, or, set-bit, find-first-bit, etc.
Here is the code:
// the basic core data of a board, must be copied to new board - change DATASIZE when add to this
bmap p[NUMBITMAPS]; // locations of pieces, by PIECE NAMES
bmap frozen; // bit set if that piece is frozen
char pieces[64]; // piece on each point, 0 is upper left (black side of board )
char strongest[2][64]; // strongest piece next to each square, by color (or EMPTY)
unsigned int hashindex, hashkey1; // transposition table values
int material; // material balance, 1000 per pawn, positive for gold
int bestmateval; // best pawn matestep value
char bestmateloc; // best mate location
char tm; // side to move (0-white, 1-black)
char phase; // phase of the the move, 0-3
char wtotmat, btotmat; // white and black total material, 1, 2, 3, 5, 9, 11
unsigned char pullsquare, pullpiece; // last move's pulling square (empty square where piece was)
// and piece doing the pulling - unless pullpiece is empty
unsigned char pushsquare, pushpiece; // last move pushed square (empty point where piece was)
// and enemy piece that was pushed -
// unless pushpiece is empty - next step is forced
unsigned char pawncount[2]; // how many pawns left by color
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Board Representation
« Reply #29 on: Aug 15th, 2006, 2:08pm » |
Quote Modify
|
on Aug 14th, 2006, 10:34pm, fotland wrote:| char wtotmat, btotmat; // white and black total material, 1, 2, 3, 5, 9, 11 |
|
If you ever get motivated to work on Bomb some more, consider changing the material values to 1, 1.5, 2, 3, 5, 10. We've had a lot of experience with uneven trades since the old days, and it turns out camels and horses are not worth as many little pieces as we used to think. (Yes, I realize that many other parameters would have to change as well to correspond, but Bomb's overvaluation of camels and horses is actually an exploitable bug. Indeed, overvaluing the camel may have caused Bomb its one loss in the 2006 CC.)
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print