Starting with quiescence search

[Luis Babboni]

Thanks Sven for your time!!
I need sometime to analyze your detailed answer!

[Sven]

Thanks Sven for your time!!
I need sometime to analyze your detailed answer!

Take your time. In the meantime I also have to fix a bug in my "iterative minimax-based alpha-beta" code, maybe someone else has found it as well: after making a new move, alpha and beta need to be initialized for the next ply, this was missing, see the two additional lines following the comment "traverse its subtree" below.

Code: Select all

int AlphaBeta_Iterative_Minimax(Position pos, int maxDepth)
{
            // ...
            case MAKE:
            {
                if (moveIndex[ply] < numberOfMoves[ply]) {
                    // try next move from move list
                    MakeMove(pos, moveList[ply][moveIndex[ply]]);
                    // traverse its subtree
                    alpha[ply + 1] = alpha[ply];
                    beta [ply + 1] = beta [ply];
                    ++ply;
                    --depth;
                    op = GENERATE;
                } else {
                    // ...
                }
                break;
            }
            // ...
}

[Luis Babboni]

I just could start reading your last helps Sven.

First question, you said:
"...and you do not store generated moves in a move list but immediately make each move that you just generated..."
For me, "generate" and "make" a move is exactly the same!!
I do not know how it works with bitboards, but in the way I did it, to know if any move is possible, I need to do it. I do not have more than one board and I use it to move and unmove on it all the time.
Where is my wrong point here?

Thanks again!

[Luis Babboni]

In fact you seems to have two differents subroutines:
GenerateMoves(pos) and MakeMove(pos,move)

GenerateMoves(pos); // store moves in move list
for (all moves in move list) {
MakeMove(pos, move);
int score = -AlphaBeta(pos, -beta, -alpha, depth - 1);
UnmakeMove(pos, move);

Do this seems to me like do the same things twice, first to make the list and later to start the main search.
May be cause after the first time you did all moves, you could order it before start search, at last you win time.
But scared me the fact to do it twice.

[Sven]

In fact you seems to have two differents subroutines:
GenerateMoves(pos) and MakeMove(pos,move)

GenerateMoves(pos); // store moves in move list
for (all moves in move list) {
MakeMove(pos, move);
int score = -AlphaBeta(pos, -beta, -alpha, depth - 1);
UnmakeMove(pos, move);

Do this seems to me like do the same things twice, first to make the list and later to start the main search.
May be cause after the first time you did all moves, you could order it before start search, at last you win time.
But scared me the fact to do it twice.

Generating moves is not the same as making them on the board. Generating means, you create (and usually store) information about possible moves in the current position, essentially the "from" and "to" square for each move (and possibly other information, like the promotion piece, castling type, maybe some flags, a move type, or whatever). It is not necessary to make a move on the board only to see whether it is possible, you can see that by looking onto the board. Take a knight, for instance. You know all possible directions to which a knight can move, and for each direction you calculate the corresponding "to" square, check whether it is valid, and if it is, check whether it is occupied by a friendly piece or not. If "to" does not contain a friendly piece then you have a pseudo-legal move "from" => "to" which is either a capture ("to" square occupied by enemy piece) or a quiet move. This pseudo-legal move may actually be legal or not, depending on other conditions, but there are efficient ways to avoid making and unmaking each pseudo-legal move only to test whether it is legal. (In fact the only pseudo-legal moves that can be illegal are check evasions, king moves including castling moves, moves of pinned pieces, and en passant captures, all others are legal.) Legality testing can be done in various ways:

- Some people prefer the "king capture" principle where illegal moves are found by capturing the enemy king.

- Some people prefer to encapsulate all legality checking within the move generator so that they get 100% legal moves stored in the move list. Today I belong to this group.

- And others (maybe the majority today - don't know) prefer to do it the classical way, e.g.:

Code: Select all

MakeMove(...);
if (LastMoveWasIllegal(...)) {
    UnmakeMove(...);
} else {
    int score = -AlphaBeta(...);
    UnmakeMove(...);
    if (score >= beta) ...
    ...
}

where "LastMoveWasIllegal()" is essentially testing whether the king was left in check, with the optimization I mentioned in brackets above to save this legality test for most pseudo-legal moves.

So GenerateMoves() just creates data and stores it in a move list while MakeMove() updates all relevant board information to make the move on the board. This is not a duplication of effort.

[Luis Babboni]

Mmmm..... I could see a difference now thinking in the need of move ordering... the no need of "unmove".

Actually I make/generate a move, check if it is valid (if no puts side to move in check) and start the search till depth desired making/generating and checking moves and then return by as many unmoves as necesary to the actual board and just then make/generate the next* move.

Now I think I could make/generate a move on a secundary board using the main board as a "starting point", check if it is valid (if no puts side to move in check), store it.
Copy main board in secundary board. Seems easier that unmove!
Make/generate the next* move in the secundary using again the main board as "starting point", check if it is valid (if no puts side to move in check), store it.
An so on!
*: I said "next" cause not with knights, pawns (except when advance 2 squares) or king but with rooks, bishops and queens I need first to "travel" by empty squares to know if some saquare is reachable.

It could be this the idea or I´m still wrong in the difference between make and move?

[Sven]

Mmmm..... I could see a difference now thinking in the need of move ordering... the no need of "unmove".

Actually I make/generate a move, check if it is valid (if no puts side to move in check) and start the search till depth desired making/generating and checking moves and then return by as many unmoves as necesary to the actual board and just then make/generate the next* move.

Now I think I could make/generate a move on a secundary board using the main board as a "starting point", check if it is valid (if no puts side to move in check), store it.
Copy main board in secundary board. Seems easier that unmove!
Make/generate the next* move in the secundary using again the main board as "starting point", check if it is valid (if no puts side to move in check), store it.
An so on!
*: I said "next" cause not with knights, pawns (except when advance 2 squares) or king but with rooks, bishops and queens I need first to "travel" by empty squares to know if some saquare is reachable.

It could be this the idea or I´m still wrong in the difference between make and move?

No, you don't need a second board, and I also think you shouldn't try, it just makes everything even more complex.

Once again: "generating moves" means "generating information units about possible moves". Just forget the legality checking for a moment (see below where it comes into play). You simply go through your representation of the board (e.g. you might have a list of all pieces, or ...), and without changing the contents of the board you look which moves are possible ("pseudo-legal"), and store this information in a move list. It is never necessary to move pieces across the board only to see whether certain moves are possible, it is simply a matter of looking onto the board "the right way".

Then you do your move ordering, for instance by assigning an ordering score to each move in the move list and then sorting the list so that the move with the highest ordering score is at first position. Board itself still unchanged! Only now you start actually making moves on the board, beginning with the first move.

Legality testing can be added in one of three ways I described in my previous post. As I mentioned, one example would be to do legality checking at this point: after MakeMove() you could test if the move might possibly have been illegal and, if so, if it left the king in check. If the move was illegal then you Unmake() it immediately (and ignore it), otherwise you continue searching the subtree of the move and Unmake() it after returning from there.

[Luis Babboni]

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.

[Sven]

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.

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]

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.

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.

I still think is too much time consumig if I do again as I did for make moves.
I´m starting learning about bitboards, my idea now is that may be I could generate moves using bitboards that till now I just thought to add to my engine for 1.xx.x versions after end my fights with principal implementations.
Is possible the idea or just a nosense?