Problem with Negamax

[Sven]

https://github.com/universecoder/Horus- ... oard.debug

Code: Select all

10653 <first &#58; terminate called after throwing an instance of 'std&#58;&#58;out_of_range'
10653 <first &#58; what&#40;)&#58; basic_string&#58;&#58;substr&#58; __pos &#40;which is 2&#41; > this->size&#40;) &#40;which is 1&#41;

means that (as HGM stated) your engine crashed in a string operation. You need to figure out where that happens. Maybe something with squareMapping? printMove()?

[universecoder]

Cleared the segfault. Am I applying the Chess Engine Communication Protocol incorrectly?

[Sven]

Cleared the segfault. Am I applying the Chess Engine Communication Protocol incorrectly?

I can't decide about that so quickly. I just saw that you fixed the crash by introducing "usermove".

But the overall structure of your xboard command loop is deeply nested so it is a bit hard to follow. A flat structure would be much better and also less redundant, as currently you handle "new" and "go" at more than one place and you also have three places where the engine starts thinking and then plays its move.

When supporting more than the most basic commands, it will be necessary to split the command line into words in order to be able to handle parameters, e.g. for setboard, ping, level, time, ... That will require even more changes to your move loop, so you'd better make a good structure right from the beginning than sticking to the "hack" and extend it even further.

[Sven]

At engine startup and after "new" the engine color should be set to black according to CECP. The reason is that with a "normal" command loop structure the engine would automatically start to play a move for white otherwise. You initialize the engine color to white, and you don't reset it on "new" (at one of two places ...).

[Sven]

When playing the engine's move, you need to send "move " followed by the move string. I can't see where you do that, I only see that you call printMove() which prints the move string itself.

In your reaction to "force" you still have the same problem that you already solved elsewhere by introducing "usermove". That's what I meant with "redundancy", you forget to do a necessary change at all places if there is more than one place for it.

[Sven]

Cleared the segfault. Am I applying the Chess Engine Communication Protocol incorrectly?

Please check your PM.

[universecoder]

Thanks a lot for your help, I had no idea of how to parse these commands. Now I'll modify the engine structure (and a few more variables and methods for various things) so that I can use more of the Chess Engine Communication Protocol. I am reading this page right now: https://www.gnu.org/software/xboard/engine-intf.html
I am also reading up on move ordering right, iterative deepening, alpha beta pruning and so on.
I was also wondering how does Fairy-Max send the output it is 'thinking' to Xboard?

Finally, last time you mentioned that the method chessboard::isSquareAttacked() is slowing me down, and recommended checking for 4 conditions:
1. If the king has moved
2. If the king is in check
3. EnPassant is involved
4. Pieces pinned to own king

Where do I find the theory for this.
My speed is at 250,000 nodes per second right now(measured with std::chrono), which I believe is quite slow. What other suggestions do you have(for perft speed-up or anything general), such as the enPassantSquare thing you mentioned.

[Sven]

Finally, last time you mentioned that the method chessboard::isSquareAttacked() is slowing me down, and recommended checking for 4 conditions:
1. If the king has moved
2. If the king is in check
3. EnPassant is involved
4. Pieces pinned to own king

Where do I find the theory for this.

I am not aware of some special theory for this, I think you can figure it out from the chess rules. The way how you, and everyone else, is generating pseudo-legal moves will already ensure that there are at most two ways how a pseudo-legal move can be illegal: either if it leaves or puts your king in check, or if you castle when currently being in check or moving your king through check. The latter can already be excluded when generating castling moves, so leaving or putting the king in check is the only remaining issue:
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.

I don't count how often this has been mentioned in this forum Maybe there should be a CPW page about this. The point is that restricting the makeMove() - isOwnKingInCheck() - unmakeMove() procedure to only those four cases above (which are statistically quite rare) saves a lot of effort. You can still decide whether you put the remaining effort for legality checking (for the four cases above) into the move generator, turning it into a legal move generator (like in your case) and getting code that is easier to read and maintain, or postpone legality checking until a move is actually about to be made (saving some redundant legality checking for moves that will never be tried due to getting an earlier cutoff). In the latter case you would do something like this:

Code: Select all

for (all pseudo-legal moves) {
    bool canBeIllegal = moveCanBeIllegal(move); // check the four conditions
    makeMove(move);
    if (canBeIllegal && wasKingLeftInCheck()) {
        unmakeMove(move);
        continue;
    }
    int score = // recursive search ...
    unmakeMove(move);
    ...
}

within each move loop. Currently I prefer the legal move generator style due to the way how it simplifies my search code.

A legal move generator could also be written differently by perfectly taking care about generating legal moves only and never having to check with make-unmake but that is really another kind of project.

My speed is at 250,000 nodes per second right now(measured with std::chrono), which I believe is quite slow. What other suggestions do you have(for perft speed-up or anything general), such as the enPassantSquare thing you mentioned.

My suggestion is that you do not care about raw speed too much at the moment. Algorithmic improvements are ok, as well as considerably huge speedups like the one mentioned above - provided you don't introduce new bugs or risks. Also getting rid of unusual, unsafe, or obviously redundant stuff is usually a good thing. But many "micro optimizations" do not really help and sometimes even do more harm, so better postpone optimizing until much later.

I suggest to concentrate on writing simple code that is easy to read and to change, ideally has no bugs, and does what you want it to do. Add new features (usually starting with tree search and possibly later with evaluation) slowly and step by step. Test a lot, reserve more than 50% of your chess programming time for testing. One of the most important things after having created an initial working alpha-beta engine is to establish a stable testing procedure that allows to measure the influence of your changes on the engine's playing strength. Many people do this by selecting a small, fixed set of opponents of roughly similar strength (some even play against the previous version of their own engine only) and by playing a lot (say, 1000 or more) of very fast games (like few seconds for the whole game) against these opponents. To avoid many repeated games while also excluding any random influence people usually also take a fixed set of opening positions. Finally Elo ratings can be computed from saved PGN files using one of the existing tools (BayesElo, Ordo).

Also do not expect to get an engine of GM strength within a few weeks. It will usually take considerably more than a year to get there, of course depending on the amount of time you can spend and also your computing and testing resources. Speaking about myself, I never got there up to now, still trying ...

Regarding your Makefile I'd suggest again to remove the *.hpp file names from the command line, and to add -Wall to show compiler warnings (which you should fix). Also I would maintain a debug build (with -g -O0) and a release build (with -O3). Regarding "perft", in my engine I have three commands "perft", "divide" (which prints the perft numbers for each root move) and "selftest" (which runs perft for a fixed set of positions and checks the results).

[universecoder]

I have three commands "perft", "divide" (which prints the perft numbers for each root move) and "selftest" (which runs perft for a fixed set of positions and checks the results).

I did a similar thing too:)

[hgm]

I was also wondering how does Fairy-Max send the output it is 'thinking' to Xboard?

In the root, after every iteration, it prints the depth, best score (= alpha), node counter and time elapsed (both cleared before the search), and then the PV. And then it flushes the output buffer, to make sure the GUI receives the data immediately.

The only non-trivial item is the PV. Fairy-max collects that in an array of moves, used as a stack:

At the beginning of every node it remembers where the top of the stack is, and pushes an invalid move code on it to demarcate the end of the PV for that node (which at that point thus has an empty PV). When it returns from the node it restores the stack pointer from the remembered value, but the PV of the returning node will still start directly behind it.

Every time a move scores between alpha and beta the PV of the current node is overwritten, first by the move, and then by copying the PV of the daughter directly behind the old PV behind that move. The last (invalid) move that demarcates the end of that new PV is then made the new stack top.