Problem with Negamax

[universecoder]

Thank You! How do I select the values of alpha and beta anyway, though?

[hgm]

In the root alpha starts as -INFINITE and beta = +INFINITE. But like in any other node alpha is not constant, but increases to the the best score found so far. Other obtain an alpha and beta from their parent, alpha = -parentBeta and beta = -parentAlpha.

[Sven]

Thank You! How do I select the values of alpha and beta anyway, though?

You can do it as described in the CPW.

[universecoder]

1. Moving the king can put it into check.
2. Moving when in check can miss to get out of check.
3. Capturing en passant can put the own king into check (if your king is on the same rank as both involved pawns, or if you start with a position that is unreachable from the initial opening position but has the enemy pawn that will be captured on the same diagonal as your king).
4. Moving a pinned piece can put your king into check.

The first and third are easily achievable. However, doing the second requires me to call isSquareAttacked on kingSquare(to check if the king is in check), making the entire thing redundant again! I thought this could be solved by calling isSquareAttacked() at the start in generateAllMoves(), is this True? If so, then isSquareAttacked will have to be called again for the entire LINE of moves.

The 4th seems to confuse me. To determine these pieces, I would have to loop in all directions emanating from the king, which take almost as much time as isSquareAttacked(). How does one overcome this problem. Do I maintain a list of pieces pinned to the king and update it incrementally?

Finally, I did perft without legality checking(to get an idea of the upper bound of speed I would get if I did the above) and I got ~ 1 million nps. Although you asked me not to worry about raw speed right now, are there any other optimizations possible? I implemented alphaBeta and I am not completely satisfied with the raw speed of perft. Still, are there any major improvements I can make(in perft)

A person on ##algorithms in freenode suggested that I incrementally maintain a list of attacked squares(I think this is unfeasible, since I would have to loop over and add constant amounts for various pieces, but I may be wrong).

[universecoder]

Also, my notebook is 10 years old(Core 2 Duo and 2 GB RAM), does this matter much?

[Sven]

1. Moving the king can put it into check.
2. Moving when in check can miss to get out of check.
3. Capturing en passant can put the own king into check (if your king is on the same rank as both involved pawns, or if you start with a position that is unreachable from the initial opening position but has the enemy pawn that will be captured on the same diagonal as your king).
4. Moving a pinned piece can put your king into check.

The first and third are easily achievable. However, doing the second requires me to call isSquareAttacked on kingSquare(to check if the king is in check), making the entire thing redundant again! I thought this could be solved by calling isSquareAttacked() at the start in generateAllMoves(), is this True? If so, then isSquareAttacked will have to be called again for the entire LINE of moves.

No, you simply save the result of isSquareAttacked(kingSquare) in a boolean variable and only pass that variable to the function that decides whether a particular move might be illegal.

The 4th seems to confuse me. To determine these pieces, I would have to loop in all directions emanating from the king, which take almost as much time as isSquareAttacked(). How does one overcome this problem. Do I maintain a list of pieces pinned to the king and update it incrementally?

You determine the set of pinned pieces once per node, at about the same time when calling isSquareAttacked(kingSquare). Then you pass that set to the function mentioned above. A 64 bit number would be a good choice as a representation of the set since it can be maintained and tested efficiently.

Finally, I did perft without legality checking(to get an idea of the upper bound of speed I would get if I did the above) and I got ~ 1 million nps. Although you asked me not to worry about raw speed right now, are there any other optimizations possible? I implemented alphaBeta and I am not completely satisfied with the raw speed of perft. Still, are there any major improvements I can make(in perft)

Once you have a legal move generator that uses the trick above, you can just return the number of legal moves at depth == 1 instead of making and unmaking all these moves at the last tree level. At that point it will make sense to report two different numbers: nodes per second (based on the number of nodes where perft() actually generated moves) and leaves per second (based on the number of leaves that are counted and form the result of perft()). NPS would then typically remain at a level of, say, 1 million (depending on CPU speed, compiler and settings of course) while LPS would go up significantly, maybe to 20 million. Of course LPS would decide about the time it takes to compute perft.

A person on ##algorithms in freenode suggested that I incrementally maintain a list of attacked squares(I think this is unfeasible, since I would have to loop over and add constant amounts for various pieces, but I may be wrong).

It can be done. People have done it. But it would be quite a different approach from what you currently have. So you could write another engine based on that approach. If I were you I would stick with the current approach that seems to be simple enough to build a working engine upon.

[hgm]

However, doing the second requires me to call isSquareAttacked on kingSquare(to check if the king is in check), making the entire thing redundant again! I thought this could be solved by calling isSquareAttacked() at the start in generateAllMoves(), is this True? If so, then isSquareAttacked will have to be called again for the entire LINE of moves.

Note that testing if there are pinned pieces is nearly the same thing as testing whether you are in check. If a ray scan away from your King hits a friendly piece, you just have to continue that ray scan a little bit further to see if there is an enemy slider behind it that looks your way. Or, in other words, when looking for pinned pieces, you get distant checks as a side effect for nearly free.

King moves are a pain, however. You would indeed have to test all of those for legality separately. But fortunately King moves make only a small fraction of your total number of moves.

When already in check, moves with non-royal pieces can be easily filtered. In case of a double check they will never be any good. And in case of a single checker they must land on the ray from king to (and including) the checker. This can be easily tested with the aid of an alignment and a distance table.