I'd say that switching to bitboards in the current situation would be like teaching your engine to serve two aces in a row without knowing whether it can even hit the ball ...
What I mean is, the advanced bitboard stuff requires a good understanding of the basics.
Maybe my current problem is to understand better what your problem is, regarding move generation, making moves, and how tree search works.
Starting with quiescence search
Moderators: hgm, Rebel, chrisw
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Starting with quiescence search
Just to make sure your statement above will not be ignored:Luis Babboni wrote:I still think is too much time consumig if I do again as I did for make moves.Sven Schüle wrote:Re move generation: you will find the key if you simply know how you detect that a square is empty or contains some piece of some color, and how you reach the next square in a given direction.Luis Babboni wrote:May be this " looking onto the board "the right way". " is where is the key.
Let me know if I could find it.
Thanks Sven!
BTW: I still do not see why two bounds are necesary in "alpha beta"*!!
But giveme some more time.
*: I mean, I could see why doing alpha beta, but I still think my way without alpha and beta, even could being more complicated, is as good as alpha-beta.
There is nothing you do *again* here. You do two completely different things when generating moves or when making moves on the board. How can I help you to understand this essential point?
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with quiescence search
LOL, I´m afraid you are right!Sven Schüle wrote:I'd say that switching to bitboards in the current situation would be like teaching your engine to serve two aces in a row without knowing whether it can even hit the ball ...
Sven Schüle wrote: ...
There is nothing you do *again* here. You do two completely different things when generating moves or when making moves on the board. How can I help you to understand this essential point?
Yes, I still do not see the difference.
Well, I saw a difference when I imagine the option to got a second board and in this way not need to make unmoves, but you said it will be complicated without reason.
Imagine whites have the king in H1 and a pawn in B3 and blacks the king in H8 and is white turn.
Actually Soberango, with whites, gives to thats pawn the number 2 and to the king the number 13.
I started a walk through pieces from 1 to 16 and movements from 1 to some number relative to the value the piece have.
Well, piece number 1 not exists so jump to piece number 2. The value of piece number 2 is +1 (a white pawn) so the move 1 is push it one square ahead. I check in my actual board there is no other piece in B4, then I change the coordinates of the piece 1 from (2,3) to (2,4), actualize the board with piece 1 in (2,4) and no piece in (2,3) and check that my king do not be in check with this new board state, check the 3rd repetition rule do not be reach (cause is a pawn move there is no increase in the 50 moves rule counter) and take care of possible en passant pawn if exists.
I call this "make b4 move".
What will be "generate b4 move"? The same without delete the piece in B3 and add a piece in B4; check 50 moves rule; 3rd repetition, en passant stuff, and even in check king or something even different?
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Starting with quiescence search
Generating moves refers to making a list of available moves. Making a move refers to computing the state of the game after the move has been performed.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with quiescence search
The point not clear for me is how to make that list without make the moves.AlvaroBegue wrote:Generating moves refers to making a list of available moves. Making a move refers to computing the state of the game after the move has been performed.
Could be this the difference: the making of a move is the generate of the move plus the updates of the board, en passant pawns, 50 moves rule, 3rd repetition rule, etc.?
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Starting with quiescence search
No, the making of the move does not include the generation of the move. You would normally have the moves generated already.Luis Babboni wrote:The point not clear for me is how to make that list without make a move.AlvaroBegue wrote:Generating moves refers to making a list of available moves. Making a move refers to computing the state of the game after the move has been performed.
Could be this the difference: the making of a move is the generate of the move plus the updates of the board, en passant pawns, 50 moves rule, 3rd repetition rule, etc.?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Starting with quiescence search
"Generate b4 move" means: you keep a table, or list, of possible moves, and in that table you store the information "from=B3 (coordinates (2,3) in your case)" and "to=B4 (coordinates (2,4))", and possibly other information that you would need later on when you will actually "make" that move on the board. That additional information could be the piece number 2, the piece type "Pawn" (+1), maybe also the color of the piece, ... But essential is "from" and "to", since these describe a move uniquely given the current position, with promotions being the only exception (here you also need the type of the promotion piece). You just store this information, nothing else, you do not change the board state, you do none of the steps that belong to "make move" (see further down for a list what belongs where). The same move list will then also contain all king moves that are possible from H1. Let's further assume that you generate information about king moves prior to that for pawn moves. Then the move list will contain these four moves:Luis Babboni wrote:LOL, I´m afraid you are right!Sven Schüle wrote:I'd say that switching to bitboards in the current situation would be like teaching your engine to serve two aces in a row without knowing whether it can even hit the ball ...
Sven Schüle wrote: ...
There is nothing you do *again* here. You do two completely different things when generating moves or when making moves on the board. How can I help you to understand this essential point?
Yes, I still do not see the difference.
Well, I saw a difference when I imagine the option to got a second board and in this way not need to make unmoves, but you said it will be complicated without reason.
Imagine whites have the king in H1 and a pawn in B3 and blacks the king in H8 and is white turn.
Actually Soberango, with whites, gives to thats pawn the number 2 and to the king the number 13.
I started a walk through pieces from 1 to 16 and movements from 1 to some number relative to the value the piece have.
Well, piece number 1 not exists so jump to piece number 2. The value of piece number 2 is +1 (a white pawn) so the move 1 is push it one square ahead. I check in my actual board there is no other piece in B4, then I change the coordinates of the piece 1 from (2,3) to (2,4), actualize the board with piece 1 in (2,4) and no piece in (2,3) and check that my king do not be in check with this new board state, check the 3rd repetition rule do not be reach (cause is a pawn move there is no increase in the 50 moves rule counter) and take care of possible en passant pawn if exists.
I call this "make b4 move".
What will be "generate b4 move"? The same without delete the piece in B3 and add a piece in B4; check 50 moves rule; 3rd repetition, en passant stuff, and even in check king or something even different?
1) "from=H1, to=H2" (coordinates (8,1) to (8,2), I guess)
2) "from=H1, to=G1" ((8,1) to (7,1))
3) "from=H1, to=G2" ((8,1) to (7,2))
4) "from=B3, to=B4" ((2,3) to (2,4))
Now you can decide about the order in which the tree search should try these moves. Since there are no captures in the list the resulting order might be arbitrary. Let's say for some reason your ordering strategy assigns the highest score to move number 4, then 3, then 1, then 2. You can now sort the move list based on these ordering scores so that the move B3-B4 will now sit at position 1 of the move list. Note that the state of the chess board has not been changed!
GenerateMoves() is done, so you start searching the generated moves in the order in which they now appear in the move list. You take the first element of the list. There you find the information how to update the board state: from the current position a piece on B3 shall be moved to B4. You make the move, changing the board state at coordinates (2,3) and (2,4) (and what else you need to update). Now you have reached a new node, and you do the same stuff for the new node, unless you hit a leaf node. At some point you have completed searching all moves for the new node (which means, you have generated a new move list for the next level - you need one move list per depth during search - containing the black moves H8-H7, H8-G8, H8-G7, and you have finished searching these moves, maybe only a part of them due to a cutoff). So now you unmake the pawn move B3-B4, and you check whether the score that you got back from its subtree is sufficient for a cutoff, or at least if it is an improvement over the best score so far. If you don't do a cutoff then it is now time for the next move from the move list which is H1-G2. You make the move, search its subtree, unmake the move, check the score, and so on. At each depth (level) you remember the index of the current move in your move list for that level.
- Now let's see which of the steps you described above belong where.
That belongs to "generate moves". "Walk through pieces" relates to the outermost loop of the move generator, and "movements from 1 to some number ..." sounds a bit like you maintain a huge table of ever possible moves in any arbitrary position, which is ok. But in any case, it is still "infrastructure of the move generator". What you do for a specific piece type (here: Pawn) belongs to the move generator as well, here you find that the current piece (a Pawn) has the ability to move one square ahead, provided that square is empty.I started a walk through pieces from 1 to 16 and movements from 1 to some number relative to the value the piece have.
Well, piece number 1 not exists so jump to piece number 2. The value of piece number 2 is +1 (a white pawn) so the move 1 is push it one square ahead. I check in my actual board there is no other piece in B4,
This is "make move B3-B4" ...then I change the coordinates of the piece 1 from (2,3) to (2,4), actualize the board with piece 1 in (2,4) and no piece in (2,3)
This is not strictly necessary during MakeMove(), I already wrote something about different ways of legality checking. It can be done here, though (and I also wrote in an earlier post that it is possible to avoid testing this condition at all for most moves since only few moves can actually be illegal).and check that my king do not be in check with this new board state,
Not sure what you mean exactly. 50 moves rule and threefold repetition rule are two different rules. The 50 moves counter must be reset to zero for a pawn move. Checking for repetition is usually done in the context of the search, since the check may result in the statement that the position is draw, so you want to return a score representing a draw (usually 0), but MakeMove() does not deal with scores for the current position, so it seems the wrong place to do it there.check the 3rd repetition rule do not be reach (cause is a pawn move there is no increase in the 50 moves rule counter)
That is perfectly a necessary part of "make move".and take care of possible en passant pawn if exists.
I hope things get a little bit clearer now
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with quiescence search
Yes! Seems it is!Sven Schüle wrote: ....
I hope things get a little bit clearer now
I think now that cause in the way I programmed the engine for make a move I need to generate it first, not all but the move I will do, and I did both things together, I thought both things are the same.
Now I see I could split all what I did in two parts.
Note: here I did a not clear way to explain me:
"check the 3rd repetition rule do not be reach (cause is a pawn move there is no increase in the 50 moves rule counter)"
Must be:
"Check the 3rd repetition rule do not be reach.
Cause is a pawn move, there is no need to increase the 50 moves rule counter."
And in fact I need to reset the 50 moves counter to zero as you said.
Thanks Sven and Álvaro for your time!!
This weekend I think I need to redo part of the code just did it if I want to add move ordering.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with quiescence search
I have 18 posssible moves for pawns (include all possible promotions being after a capture or a push one square ahead), 8 for knights; 28 for bishops, 28 for rooks, 56 for queens and 10 for kings. How many of them are avaiable dependes on the board state.Sven Schüle wrote: ...
"movements from 1 to some number ..." sounds a bit like you maintain a huge table of ever possible moves in any arbitrary position
...
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with quiescence search
Time ago I went first to add quiescence search to my engine and it seems I did it but the performance was worst than without it and the reason seems it was that its not have move ordering.
So I went to add move ordering but for that first I need to add a moves generator that my engine did not have (directly make moves and analize them one by one without a previous generation of all).
So I went to add a moves generator...
Well, now my engine have a moves generator, an ordering moves and quiescence search!
Its performance is far better than previous version with QS without move ordering.... but still worst than version without QS!!!
For the moment I did not found any bug, it seems the reason is that with QS, its reach less number of plies in depth. Not in QS search, but in general.
Could be possible or I must did the QS in a wrong way?
Thanks!
So I went to add move ordering but for that first I need to add a moves generator that my engine did not have (directly make moves and analize them one by one without a previous generation of all).
So I went to add a moves generator...
Well, now my engine have a moves generator, an ordering moves and quiescence search!
Its performance is far better than previous version with QS without move ordering.... but still worst than version without QS!!!
For the moment I did not found any bug, it seems the reason is that with QS, its reach less number of plies in depth. Not in QS search, but in general.
Could be possible or I must did the QS in a wrong way?
Thanks!