Chess Transposition Tables
Author
alvaro: Thanks for your help. My engine has finally started playing sensibly. I am still not able to reach 6 ply in under a minute, so I need to improve the search a bit. I think my move generation is very slow, and using lots of Java exceptions is not helping.
DpakoH: I am using Java to develop the chess engine. I call it Frittle, after the butterfly Frittillus that has chess-board like markings... You can download my first attempt at anything sensible. The current version has beaten amateur human players (like me) but fails against other engines even in easy mode. I still have a lot of things to improve. I just started this around 10 days ago. ..
DpakoH: I am using Java to develop the chess engine. I call it Frittle, after the butterfly Frittillus that has chess-board like markings... You can download my first attempt at anything sensible. The current version has beaten amateur human players (like me) but fails against other engines even in easy mode. I still have a lot of things to improve. I just started this around 10 days ago. ..
Congratulations on your progress!
You shouldn't be using exceptions in the middle of the search. In a chess engine exceptions can be useful for things like interrupting the search at the user's command, and little else.
The other thing you should avoid is dynamically allocating memory. You can organize everything with fixed-size arrays. Perhaps Java is not the best language for this? Why are you using Java in the first place?
Also, you haven't told us how many nodes per second your program is visiting.
You shouldn't be using exceptions in the middle of the search. In a chess engine exceptions can be useful for things like interrupting the search at the user's command, and little else.
The other thing you should avoid is dynamically allocating memory. You can organize everything with fixed-size arrays. Perhaps Java is not the best language for this? Why are you using Java in the first place?
Also, you haven't told us how many nodes per second your program is visiting.
Author
Quote:Original post by alvaro
Congratulations on your progress!
You shouldn't be using exceptions in the middle of the search. In a chess engine exceptions can be useful for things like interrupting the search at the user's command, and little else.
The other thing you should avoid is dynamically allocating memory. You can organize everything with fixed-size arrays. Perhaps Java is not the best language for this? Why are you using Java in the first place?
Also, you haven't told us how many nodes per second your program is visiting.
Hmmm.. I guessed as much. I know Java isn't the best language for chess, but I like Java and since I am just doing this as a hobby I thought I could afford the slight performance hit.
I feel my move handling is messed up. In my game, there are two different functions for move validation (given source and destination square, is the move valid? if yes, return the new position of the board) and legal move generation (which generates all the possible moves for all pieces on the board and validates them). Considering that the validation function takes decent time and throws an exception in case the move is not valid, I think I am spending most of my time in the search just generating/validating moves (there must be thousands of exceptions being thrown in every search). I need to be able to generate only legal moves so that I can skip the validation step.
My program is searching around 12,500 nodes per second, which I know is extremely sluggish. My whole move generation is based on the exception model, so refactoring that is going to be a big task. But I think it is really necessary to speed things up.
On the topic of fixed size arrays: How do you mean? The only dynamic data structure I am using is a vector when generating moves, because I don't know how many moves might be possible. Plus, they need to be re-ordered before searching. The transposition table and opening book use fixed size data structures.
Quote:Original post by Verminox
Hmmm.. I guessed as much. I know Java isn't the best language for chess, but I like Java and since I am just doing this as a hobby I thought I could afford the slight performance hit.
As long as the performance hit is reasonable, that's fine.
Quote:I feel my move handling is messed up. In my game, there are two different functions for move validation (given source and destination square, is the move valid? if yes, return the new position of the board) and legal move generation (which generates all the possible moves for all pieces on the board and validates them). Considering that the validation function takes decent time and throws an exception in case the move is not valid, I think I am spending most of my time in the search just generating/validating moves (there must be thousands of exceptions being thrown in every search). I need to be able to generate only legal moves so that I can skip the validation step.
You don't really need to validate every move. You can delay the validation to the point when you are about to try the move, instead of validating all the moves when you generate them. In an alpha-beta search there will be many nodes where you hopefully only have to consider a few moves, since you'll get a beta cut.
Quote:My program is searching around 12,500 nodes per second, which I know is extremely sluggish. My whole move generation is based on the exception model, so refactoring that is going to be a big task. But I think it is really necessary to speed things up.
Right now you are about two orders of magnitude slower than most programs. Most of that probably has nothing to do with Java, though.
Quote:On the topic of fixed size arrays: How do you mean? The only dynamic data structure I am using is a vector when generating moves, because I don't know how many moves might be possible. Plus, they need to be re-ordered before searching.
You can reorder a fixed-size array; that has nothing to do with it. If that's the only dynamic data structure you have, you are in decent shape. However, you did mention that you had a function that returned the new position of the board, so that sounds like more dynamic memory allocation right there.
Most programs have a single copy of the board (or one per thread, if you go parallel), where you do and undo moves. You basically never need to make a copy of the board, which is expensive.
I hope some of that helps.
Author
Quote:Original post by alvaro
You don't really need to validate every move. You can delay the validation to the point when you are about to try the move, instead of validating all the moves when you generate them. In an alpha-beta search there will be many nodes where you hopefully only have to consider a few moves, since you'll get a beta cut.
In my program the 'validation' is synonymous to generating the new board position after the move (which in turn, lets me retreive information from the transposition table), so without that, I would not be able to order by moves for the alpha-beta search.
Quote:Original post by alvaro
Most programs have a single copy of the board (or one per thread, if you go parallel), where you do and undo moves. You basically never need to make a copy of the board, which is expensive.
I hope some of that helps.
Oh, well, in that case, yeah I have a lot of dynamic memory allocation. A lot of GameState (position) objects being copied and each creating their own evaluation results and generating their own move list... You think using only one copy of the board will help improve speed? I had thought of doing this earlier but I wasn't able to implement undo-ing the move. That would require storing a lot of information about the move (like which piece was captured and if there was a promotion involved)... and what about if you had to undo 5-6 places back (coming out of the depth first search)?
Gah! I now feel like my entire code has been approached wrongly...
[Edited by - Verminox on April 25, 2009 12:00:17 AM]
Quote:Original post by Verminox
You think using only one copy of the board will help improve speed? I had thought of doing this earlier but I wasn't able to implement undo-ing the move. That would require storing a lot of information about the move (like which piece was captured and if there was a promotion involved)... and what about if you had to undo 5-6 places back (coming out of the depth first search)?t, I would not be able to order by moves for the alpha-beta search.
Yes, I expect keeping a single copy of the board will improve speed a lot.
For the `undo' part, you need to remember:
* The move
* The piece captured
* The castlings that were allowed before the move (4 bits)
* How many non-pawn, non-capture moves had been played before the move (for the 50-move rule)
Undoing multiple levels is not a problem if you organize your code right. In the loop that goes through moves in your alpha-beta search, you'll have a call to do the move, a recursive call to search the resulting board and then a call to undo the move. You'll leave things the way they were when you are done, so you don't make any messes.
I don't understand the last part about not being "able to order by moves"...
Author
Quote:I don't understand the last part about not being "able to order by moves"...
Sorry about that, wrote that in the wrong place. That was for your first suggestion (about move validation). What I was trying to say was that my validation part occurs while I try to create the new board state. It is only after the new state is formed can I lookup the hashtable for a score from a shallower search which will help my move ordering. So my move 'validation' has to occur before I decide to start searching. I can't validate them as I search, because I won't know their tentative score (from shallower searches) and hence won't be able to order them.
Anyway, I'll try to use only one copy of the board. But that would probably take some time. Thanks a lot for your help.
PS: How do you get your engine to be rated (ELO)? I know WinBoard doesn't have a rating system but I think Arena does... How many tests wold I have to go through to get an approximate rating? (I know it won't be very accurate unless thousands of games are played).
PPS: Which chess engine have you worked on? Is it freely available?
Edit: I performed some Perft tests on my move generation and indeed it is the generation of moves itself that is hampering my search speed. In opening positions with lots of pieces I can barely generate 30,000 nodes per second, and in the endgame with few pieces I can generate about 75,000 nodes per second. Either way, I suppose until I improve my move generation there is no scope for search speeding...
[Edited by - Verminox on April 25, 2009 5:55:16 AM]
Quote:Original post by VerminoxQuote:I don't understand the last part about not being "able to order by moves"...
Sorry about that, wrote that in the wrong place. That was for your first suggestion (about move validation). What I was trying to say was that my validation part occurs while I try to create the new board state. It is only after the new state is formed can I lookup the hashtable for a score from a shallower search which will help my move ordering. So my move 'validation' has to occur before I decide to start searching. I can't validate them as I search, because I won't know their tentative score (from shallower searches) and hence won't be able to order them.
That sounds too expensive for move ordering. Look up `history heuristic' and `killer heuristic': Those are some very old tricks to sort the moves without having to actually play them.
Quote:PS: How do you get your engine to be rated (ELO)? I know WinBoard doesn't have a rating system but I think Arena does... How many tests wold I have to go through to get an approximate rating? (I know it won't be very accurate unless thousands of games are played).
I'm not sure. There used to be people that would run many games among freely available engines and that would publish the results as a rating list, but I haven't been following the scene in years.
Quote:PPS: Which chess engine have you worked on? Is it freely available?
I worked primarily on Ruy-Lopez, which is not freely available and which is very outdated by now. Four years ago I made an attempt to start a new engine with help from some people that were trying to learn. They ended up not helping much and I got too busy with other things. So the project is abandoned, but you can still find what I did here: https://opensvn.csie.org/traccgi/cpphome_chess/. I tried to keep the code clean, so you might find it useful. Feel free to ask questions about it.
EDIT: If nothing else in that project's site seems useful, at least you might benefit from the links page.
i just tested your engine, it played better in the begining than in the end :) probably you are using an opening book.. the results is : i won quite easily and i am rated around 2000 elo points. however, i will play some more games with it later and get it out of normal openings and see how it handles the situation. but all i can do is to congratulate you. well done so far and keep going.
please keep us updated with your project status. i am always happy to test chess engines :D
please keep us updated with your project status. i am always happy to test chess engines :D
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement