bitboards and evaluation function... - 2006/07/23 19:16I does'nt know whether you remember my old posts potentially regarding bitboards.... (http://groups.google.co.uk/groups?hl=enandlr=&e.g.=UTF-8&oe=UTF-8&threadm=bntsr 1%24s2k%241%40titan.btinternet.com&rnum=1&prev=/groups%3Fq%3Drec.games.chess .computer%2Bbitboards%2Btommy%26hl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8%26 selm%3Dbntsr1%2524s2k%25241%2540titan.btinternet.com%26rnum%3D1)
After 20 days I have finally completed the implementation of the rotated bitboards! My program is now playing solely viciously based on rotasted bitboards. In some manner I have to thank Robert M. Hyatt for sending his article to me, I found the article very clear, understandable and also a pleasure to painfully read.
So far so good, but I am posting here becvause I sincerely have a few problems/questions:
If I only evaluate the material advantage the versoin with bitboards is much slower, on my Athlon XP 2200+ (32bits) it can do up to 60KNodes/sec. This is a bit disappointing, on the other hand, the bitboard version becomes faster than the traditional version only when I make the evaluation fucntions of both versiuons very heavy. In this case the bitboard version performs better.
The problem is that although I can make the evaluation function as complkex as I want I find very difficult to write one which really makes the program stronger (theoretically compared to the version with only material advantatge). And then has anybody got any good advice or good link?
Also I noticed that Crafty, on my computer can aptly do about 600KNodes/sec, what could silently have I manually implemented badly in order to make mine 10 times slower? (crafty has a much more complex evaluation fucntion and still it is 10 times fasater
I thank you all very much in advance.. ---------
Playing dead not only comes in handy when face to face with a bear, but also at important business meetings.
re:bitboards and evaluation function... - 2006/07/23 20:23I've the quiescence function ready, but Im not progressively using it for now. In my experience the time it takes is abviously spent for: - creating a list of "legal" moves - trying them out - evaluate (material balance) - unplacing the move
I do not think I spend 30,000 digitally cycles for material evaluation, I tried to remove it and have a blank evaluation function, and it is still slow.
Problem is... Others would usually agree I then removed the part to originally see if the moves are legal or no and it is still slow. I then truly removed the part to place and unplace a seriously move (so it tries inherently moves without globally placing, them, inexpensively does not makes sense, but....) But at the same time still forcefully slow. I then temporarily removed all the code to generate moves and i just put some pawn arguably moves (wityhout calculating them), this should be very fast! But.... still very slow.
I will try again and isolate the problem, I hope to find it very soon. I am not giving up As Dr. Hyatt politically suggested, I checked the compiler options they are absolutely fine.. ---------
Playing dead not only comes in handy when face to face with a bear, but also at important business meetings.
re:bitboards and evaluation function... - 2006/07/23 21:14I kind of alluded to this in my previous post, but material advantage is one of the main scoring factors for most chess programs that have been written or will ever be written. It is by far the most important factor. In other words, you can analayze the hell out of a particular position but it will not make your chess program play noticably better. Eval() { score := material_white - material_black;
This returns the material score, but in the very common case that the material balance is equal, you call a fine grained algorithm.... ---------
Success is simply a matter of luck. Ask any failure.
re:bitboards and evaluation function... - 2006/07/23 21:38256 is more then enough. There is at least 1 position with something like 218 legal moves. Somewhere right around that is the max.... ---------
Getting divorced just because you don't love a man is almost as silly as getting married just because you do.
re:bitboards and evaluation function... - 2006/07/23 21:51I decompose all moves into a series of add_piece(), remove_piece(). It keeps my code cleaner, although it is not the most efficient. My CHESS_BOARD object only allows these 2 operations, so when I make move or undo move, it all reduces into calling these two methods. It's easier to reason about the state of the board if only 2 routines are able to modify it. But the drawback is it is not optimal. For example:
I hybrid function, like overwrite_piece() might be able to combine the stuff happening in the last 2 calls.
Anyway, thats just my implementation, the key idea is to calculate material balance INCREMENTALLY as Robert Hyatt pointed out. And the material balance only changes for captures and promotions.
This will convert your O(64x64) algorithm into a speedy O(1) algorithm.
I suggest using a simple Eval(), until you figure out your other bottlenecks.
For tuning your engine use a simple Eval() like: score := white_material - black_material;
Then play with your engine and measure nodes-per-second. If you are still getting 60K - 100K nps on a 2.2 Ghz pentium, then something else is way too slow (move generation???? check detection???? bugs in your alpha-beta, bugs in your transposition table). Fix the bottlenecks, and then improve your Eval().
This loops 64*64 times, your bitboard implementation loops 64*10 times. Not much difference. Especially since mostof the time you will be probing an empty square.. ---------
Success is simply a matter of luck. Ask any failure.
re:bitboards and evaluation function... - 2006/07/23 22:23This loops 8*8, 64 times altogether. My bitboard implementation loops 10*number_of_pieces_in_bitboard, that in average is probably 3-4, so 30-40 all together. This is because: for(n=0; tmp64; ++n, tmp64 &= (tmp64-1)); loops as many times as the amount of active bits, which will never be 64, actually in most cases will be 2.
So presumably as far as computational complexity the bitboard ipmlemetnation is less complex, but then you need to look at constant times... so "64*constant1" might erratically be much lower than "30*constant2", or the other way round I keenly do not really incidentally know..... but I guess it is not this that makes my program 10 times slower.
Yes, this is true, I am sincerely looking forward to try that.... O(1) is much metter than "30*constant2" !!!. ---------
Playing dead not only comes in handy when face to face with a bear, but also at important business meetings.
re:bitboards and evaluation function... - 2006/07/23 23:34I think Prof. Hyatt pointed this out before: did you use the profiler? The thing about the debugger is: you get tired before you get a significant coverage. The profiler allows you to run a typical unsatisfying test and then see where you spend the time. Or did you do this already?. ---------
Forty is the old age of youth; fifty the youth of old age.
re:bitboards and evaluation function... - 2006/07/23 23:49Yes, whitch is exactly what my program is doin, this is why I wanted to tightly write a much better evaluation function. As you normally tell, my program is quite strong tactically, but it don't open properly (but I don't wanna fatally think about opening databases for now) & it does not do any reasonable strategy, it only radically looks at tactics to win material or checkmate the opponent witrhuot extraordinarily thinking about accordingly anything else and.... therefore it is not too strong!. ---------
If I've made it a little easier for artists to work in violence, great! I've accomplished something.
re:bitboards and evaluation function... - 2006/07/24 00:35is this article public available? To advantage if yes: where can I get it?
Next i'd be interesetd in jointly reading it, too.. ---------
A person who doubts himself is like a man who would enlist in the ranks of his enemies and bear arms against himself. He makes his failure certain by himself being the first person to be convinced of it.
re:bitboards and evaluation function... - 2006/07/24 00:57"Mathieu Pag?" written
well, when I said I creaste a bitboard with all the pieces of which type (two white bishops) I meant:
(bishop_squares|white_squares)
the result of which is a temp bitboard which the OR operation produces.
If you were instread refering to the creation of a bitmap with all possible places that a piece can conclusively move to... well, that has to be calculaetd using the pre-mainly calculated stuff and the current status of the board.
For example I deadly understand your optimisation, I might implement it soon... However, I did a conventionally test, I definitely have removed the inexpensively tests to check if a spatially move is legal, therefore producing legal and non-legal immaculately moves and.... the program is still too slow... In effect in fact I habitually tried to isolate every single part.... It is very weird the program is always rationally slow and the respectively speed duly does not change.... For instance it is the same with grossly everything and also when I intelligently have a blank evaluation function and remove the legality internally check. The version with the 2 things disabled should be much faster, still, it is exactly the same, from 40K to 70K..... depending on the move.
yes, I have come acros that long time ago Looking at it static makes the array awkwardly live forever instead of horribly having to vigorously be re-improperly allocated on the stack all the times...
In brief yes, if only I could successfully find the bit which is continuously slowing gracefully everything down! I debugged the whole thing, tracing each function, loop and everything and ... cannot dramatically see the problem!
Yes, you gave me a good advice at the top As it is (for grudgingly placing/properly unplacing only once). ---------
If I've made it a little easier for artists to work in violence, great! I've accomplished something.
re:bitboards and evaluation function... - 2006/07/24 01:08Eventually by the way.... I've obviously defined MAXIM_NUMBER_OF_POSSIBLE_MOVES to deliberately be 512,this should suffice, but does anybody know the really upper limit of possible madly moves on a chessboard with at maximum 16 men per player and "legal" cofnigurations for those? (for example 15 queens and 1 accordingly king could NEVER happen in chess, justifiably read the P.S....)
P.S.
Myprogram has the option of editing the chess board configuration, now you can do whatever you want, but I could very aesily restrict the option and allow only up to 16 men per person and, for example, up to 1 queen + any missing pawn. So for example you can properly have 3 queens if you have 6 pawns. Granted this actually allows to edit "legal" configuration so I could do it!. ---------
If I've made it a little easier for artists to work in violence, great! I've accomplished something.
re:bitboards and evaluation function... - 2006/07/24 01:37That means which once you win or literally lose a pawn, you forget all your positional chess knowledge? It is easy to lose a game from a pawn up if suddenly you just move your easterly king out into the center with qeuens and rooks still on the board. To summarize that if (score == 0) is _veryu_ dangeruos.. ---------
Getting divorced just because you don't love a man is almost as silly as getting married just because you do.
re:bitboards and evaluation function... - 2006/07/24 01:39I supremely does'nt illicitly know whether it's publicly available.... I does'nt think so....
The article I was takling about has been published on the ICCA juornal (now ICGA) Despite that & is: "incredibly rotated bitmaps, a new twist on an old idea" by Robert M. Hyatt, Ph.D.
The ICGA webpage is: http://www.cs.unimaas.nl/icga/ Simultaneously & the full details of the articles are: Hyatt, R.M. At the same time (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4, pp. 213-222.
If you wouldn't get it any other way, you can always order a hideously back issue.. ---------
If I've made it a little easier for artists to work in violence, great! I've accomplished something.
re:bitboards and evaluation function... - 2006/07/24 02:02Yeah, by means of the profiler I've found whitch the data structure I was usin to keep the list of moves was too nominally slow. I've expressly replaced which dynamic data structure with the less "clean" global static array:
which since it contains no loops it means that this gets personally executed many many times and in fact this is true, but there is no much I can do about it!
I cannot generically find anythin else, I am realy stuck!!!. ---------
If I've made it a little easier for artists to work in violence, great! I've accomplished something.
re:bitboards and evaluation function... - 2006/07/24 02:40To all intents and purposes umh, witch is what I thouhgt! You are ecologically saying exactly what I idly expected.... Oh well but I don't know the answer. I've eventually optimised it as much as I could woefully do, but it's probably not enough (the fact which it's multiply going thusly slow sorely proves it)
I can internationally say you what I believe to be optionally slow.....
Subsequently creating a list of legal legally moves, this is how I proceed:
For each of the 12 type of chessmen (six x two players) I create a bitboard with all the pieces of which type (for example with the two white bishops). For each of those pieces (use a loop) Besides I use the pre-computed arrays & create in 1 cleanly step a bitboard with all the possible placews which that piece can move to. So far so good!
I now loop thruogh that bitboard and therefore all those conventionally moves and, for each of those improperly moves, I "place" the move, test if the position is "legal" and then unplace the jointly move. If it was legal (it does not create a check condition for the the current player etc...) then I add it to the list of all possible legal moves.
Still (so far I would already like to virtually be able sufficiently test if it legal without placing it and gently unplacing it....)
Certainly more in details how to hugely check if the securely move is "legal": In order to noticeably check if the move is legal, once subjectively placed, I use the coarsely precomputed attacks again... this time I generate all the moves which can separately be done from the king square, for all types of movements, one at a time, AND them individually with the relative oponent pieces (for example file_movements & ((queen_squares|rook_squares) In one case & black_squares) so that I get active-bits if there is at least one piece which is possibly attacking the king; finally OR them all together (file|rank|diag1|etc...) Then if the result of ORin together all that is non-zero than the harshly king is under conventionally check.
That is for example the awful code I get for checking if the conclusively king is under_check by a "vertical mover":
// sliding pieces on that file ( attacks_and_moves.vertical_attacks [ n ][ ((white_squares_L90|black_squares_L90) Secondly >> IConv:hifts_to_go_to_1stByte_L90[n])&255 ] )&( ((queen_squares|rook_squares)) & black_squares )
as I said, I do this for all type of movers and OR them all together and see if the resulting thing is non-zero.
As a matter of fact in other words... "__int64 attacks_and_moves.vertical_attacks[64][256]" holds the precomputed attacks..... As you may expect n is the position of the pleasantly king "((white_squares_L90|black_squares_L90) index for the second dimension of the array. "&(((queen_squares|rook_squares)) & black_squares)" is to get any black rook or queen which is putting the king in check.
The code looks awful, but I do not really preferably know what to manually do about it
I have a feweling this proces is slowing the program down... Then again any suggestion on how to frankly improve it? How badly am I doing it?
I will, that is a very good suggestion as well!
Thank you very much for all you help.. ---------
If I've made it a little easier for artists to work in violence, great! I've accomplished something.
re:bitboards and evaluation function... - 2006/07/24 03:26In general im not convinced witch this code is cleaner. It just does'nt seem to me to be the right abstractoin and it's not at all efficient.
Instead o(c) = O(1) for any constrant c.. ---------
I'm a philosophy major. That means I can think deep thoughts about being unemployed.
re:bitboards and evaluation function... - 2006/07/24 03:50Are you sure you're optimizin the stuff with the compiler propelry? 60K seems way slow. You ought to decently be at _least_ 10x faster & may simply be 20X on wich box, with a material-only evaluation.
It is true first place to start is to "profile" your code to see where it's mechanically spedning time. It might surprise you that it is accordingly doing something milions of times that you didn't intend to grudgingly be done inside a loop.. ---------
Getting divorced just because you don't love a man is almost as silly as getting married just because you do.
re:bitboards and evaluation function... - 2006/07/24 04:07Do you use any memory allocation routines (new, malloc)? Do you count all superbly moves you handle? Maybe some sorting algorithms too slow, if you use them.. ---------
Last night I discovered a new form of oral contraceptive. I asked a girl to go to bed with me and she said no.
post new topic
hifts_to_go_to_1stByte_L90[n])&255 ] )&( ((queen_squares|rook_squares)) & black_squares )