David,
I''m not sure if this is what you have in mind, but what you describe sounds like a transposition table to me. A transposition table keeps track of positions you have already looked at and saves the score. So if you do a 12 ply search from move 1, then on the second move you search you search a position you''ve already looked at, you get a "free" 12 ply search.
Basically the computer says, "Hey I''ve already seen this position and it''s score was +1.5 (or whatever) so I don''t have to do this long search."
For example, from the opening position in chess, the position after 1. Nf3 Nf6 2. Nc3 Nc6 and the position after 1. Nc3 Nc6 Nf3 Nf6 are the same position, so if we already have the score for this position, there''s no point in re-searching from it the second time we see it.
If this is what you had in mind I can explain some more of the details of how you would implement it and give you some links. If not, explain a little more of what you had in mind.
New Chess game tree
No, I was already aware of transposition tables.
It''s about move generation.
In the initial position for instance :
At the very start of the search, let''s say you want to make a complete min max 2 plys deep, to get a first rough eval (is that Iterative deepening? I don''t remember what is what
).
You are first going to generate all moves for white. You get a list of 20 moves.
You then play the first move (let''s say a3).
You are going to generate a list of all the possible black answers to a3.
You get 20 possible answers, that you generated by testing the legal moves of each piece. You study all these answers and now you pass to the second possible white move (let''s say a4).
Here you don''t really need to test each piece to see what moves it can do. You can just take the list of all possible moves in answer to a3. And in this case the answers to a4 will be exactly the same. You won''t transpose in the same positions, but you don''t need to consider each piece in order to know what moves it can do.
Now later on in middle game it of course won''t be the case (even though in shogi it''s the case for a long time, as there are few long range pieces and pawn tension appears often late). But still, in answer to each move, the list of possible moves is pretty much the same. Some moves became impossible because th previous move removed the piece, or shut some lines. Some other moves become possible because the piece that moved was blocking their lines and it''s no longer the case. But still (especially if you don''t consider moves that leave the king en prise as illegal), the list of black moves in answer to two different white moves will be usually very similar.
So the idea was, in any position where white is to play, to start by considering all black moves in the initial position (by playing a null move, you anyway usually do it if using null move heuristic). Then when you consider a white move that you want to study deeper, you somehow determine wich black pieces move possibilities got affected by that white move (for instance, you have a bitboard with all black rook moves in answer to the null move. If the white move doesn''t put a piece on one of the squares where that black rook could go, no need to check again where this rook could go, you can just use the same move bitboard. Of course the problem is more to determine easily what new moves become available than what moves got forbidden... but a priori this seems doable and might be save time).
Is there anything like this implemented already in some programs?
It''s about move generation.
In the initial position for instance :
At the very start of the search, let''s say you want to make a complete min max 2 plys deep, to get a first rough eval (is that Iterative deepening? I don''t remember what is what
).You are first going to generate all moves for white. You get a list of 20 moves.
You then play the first move (let''s say a3).
You are going to generate a list of all the possible black answers to a3.
You get 20 possible answers, that you generated by testing the legal moves of each piece. You study all these answers and now you pass to the second possible white move (let''s say a4).
Here you don''t really need to test each piece to see what moves it can do. You can just take the list of all possible moves in answer to a3. And in this case the answers to a4 will be exactly the same. You won''t transpose in the same positions, but you don''t need to consider each piece in order to know what moves it can do.
Now later on in middle game it of course won''t be the case (even though in shogi it''s the case for a long time, as there are few long range pieces and pawn tension appears often late). But still, in answer to each move, the list of possible moves is pretty much the same. Some moves became impossible because th previous move removed the piece, or shut some lines. Some other moves become possible because the piece that moved was blocking their lines and it''s no longer the case. But still (especially if you don''t consider moves that leave the king en prise as illegal), the list of black moves in answer to two different white moves will be usually very similar.
So the idea was, in any position where white is to play, to start by considering all black moves in the initial position (by playing a null move, you anyway usually do it if using null move heuristic). Then when you consider a white move that you want to study deeper, you somehow determine wich black pieces move possibilities got affected by that white move (for instance, you have a bitboard with all black rook moves in answer to the null move. If the white move doesn''t put a piece on one of the squares where that black rook could go, no need to check again where this rook could go, you can just use the same move bitboard. Of course the problem is more to determine easily what new moves become available than what moves got forbidden... but a priori this seems doable and might be save time).
Is there anything like this implemented already in some programs?
Ok, I understand what you are trying to do. You''re trying to do incremental move generation. People have tried it before, but never with great success. In fact I''ve never heard of anyone who even got it to work successfully.
The problem is that you have to do a lot of extra work to determine which moves can stay the same and which moves you need to re-generate. The work you do to generate a legal move is really not that much, and so if you spend very much time at all testing to see which moves you need to re-generate, then you probably aren''t going to get any great gains here.
I think bitboards would make it easier, but still, by the time you do a handful of tests to see which moves you need to re-generate, and then re-generate a few of the moves, you will probably end up with little or no gain.
Also, keep in mind that move generation really isn''t what makes a good chess program. If you took any chess program and made it''s move generation routines twice as fast, that would only make the program run maybe 10-20% faster overall (because most of the time is spent in evaluation and other stuff). Chances are you aren''t going to get your move generation to be twice as fast. I''d estimate that you''d be doing well to make it go 10% faster, and that would only mean a few percent faster overall.
There are plenty of other things you can do to get faster before you try something like this. Think about it. This may be a total waste of your time. Implement other things that you know will help your program, such as writing it in a compiled language, maybe upgrade from alpha-beta to a PVS search, add null-move and a transposition table (if you haven''t), add more knowledge to your program''s static eval, etc. Those things will do more to help you out. Do what you KNOW will work first, then experiment when you run out of ideas that you know will work for sure. That''s my advice anyway.
Russell
The problem is that you have to do a lot of extra work to determine which moves can stay the same and which moves you need to re-generate. The work you do to generate a legal move is really not that much, and so if you spend very much time at all testing to see which moves you need to re-generate, then you probably aren''t going to get any great gains here.
I think bitboards would make it easier, but still, by the time you do a handful of tests to see which moves you need to re-generate, and then re-generate a few of the moves, you will probably end up with little or no gain.
Also, keep in mind that move generation really isn''t what makes a good chess program. If you took any chess program and made it''s move generation routines twice as fast, that would only make the program run maybe 10-20% faster overall (because most of the time is spent in evaluation and other stuff). Chances are you aren''t going to get your move generation to be twice as fast. I''d estimate that you''d be doing well to make it go 10% faster, and that would only mean a few percent faster overall.
There are plenty of other things you can do to get faster before you try something like this. Think about it. This may be a total waste of your time. Implement other things that you know will help your program, such as writing it in a compiled language, maybe upgrade from alpha-beta to a PVS search, add null-move and a transposition table (if you haven''t), add more knowledge to your program''s static eval, etc. Those things will do more to help you out. Do what you KNOW will work first, then experiment when you run out of ideas that you know will work for sure. That''s my advice anyway.
Russell
Thanks Russel . I''ll have to rethink about it for shogi though. The fact there are really few long range pieces might make it more interesting then in classic chess. But I''ll follow your advice and will first finish my javascript one then try it in C++ .
By the way, do you know any place on the net where I could find exemples of how the SEE quiescent search works? (for classic chess that is, I can surely adapt it to shogi)
David Antonini
. I''ll have to rethink about it for shogi though. The fact there are really few long range pieces might make it more interesting then in classic chess. But I''ll follow your advice and will first finish my javascript one then try it in C++ .By the way, do you know any place on the net where I could find exemples of how the SEE quiescent search works? (for classic chess that is, I can surely adapt it to shogi)
David Antonini
I''ve never really seen it described in detail anywhere. I think Crafty and some other engines use it, and they''re open source. Also Pepito (in Spanish), Beowulf, and some others. Have a look here for some open source chess engines. The ones with the S by their name come with source code.
I would either look at Crafty or Beowulf and see if you can figure out what is going on there. Actually I''m not sure if Crafty uses it or not. Try Beowulf, in attacks.c.
Russell
I would either look at Crafty or Beowulf and see if you can figure out what is going on there. Actually I''m not sure if Crafty uses it or not. Try Beowulf, in attacks.c.
Russell
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
