Questions about chess programming from a newbie

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

mattbrah
Posts: 3
Joined: Sun Apr 12, 2015 7:33 pm

Questions about chess programming from a newbie

Post by mattbrah »

Hi all.

Last December I completed my very first chess engine as an introductory to C++. It's slower and weaker than I was hoping it would be, but I'm sure that I could optimize it quite a bit. Right now it probably plays at around a 1200-1300 Elo at depth 6 which is the deepest it can go comfortably.

Since all of you are basically chess engine gods, if anybody is up for it, I would love if somebody could skim through my code and point out any glaringly obvious mistakes (either with C++ or chess engine theory), I would much appreciate any kind of advice. I will admit that some parts of it is ugly and that I am very far from being proficient in C++ https://github.com/mp3259/Quokka

Here are a few questions I have based on the following information:
  • I am using C++
  • I am trying to get it to play at a respectable level (2000+)
  • Piece locations & Move generation in my program is based off of the 120 indexed array method
1. Is it worth using arrays instead of dynamic vectors in terms of speed?
Example: Move generation. using a empty preallocated 218 indexed array to store the generated moves, or just using a vector and dynamically adding moves.

2. How much of a speed difference does storing piece positions and movegen via bitboards make? Is the trade off in speed worth the time that it takes to understand and implement bitboards? What is the highest realistic level that it could play at using it's current method and instead focusing on optimizing the search/evaluation?

3. I'm trying to understand iterative deepening. Right now I have this kind of setup in my search function:

for (int i = 1; i <= depth; i++) {
do alpha beta algorithm to specified depth and assign it to score
print UCI info (score, depth, nodes, time)
print principal variation
}

Right now my engine does not follow the principal variation, which I'm pretty sure it needs to follow it in order to maximize speed when increasing the depth and redoing the alpha beta function.

Here is something kind of interesting which I noticed tinkering with the code above:

Running the search with the code above with the starting position, I can get to depth 7 in roughly 14 seconds. When I remove the for loop and just tell it to do alpha beta to depth 7 immediately, it takes the same amount of time if not more. What is the reasoning behind this? Shouldn't the looping method take longer because it's having to recalculate each time it increases the depth since it's not following the PV?
User avatar
Bloodbane
Posts: 154
Joined: Thu Oct 03, 2013 4:17 pm

Re: Questions about chess programming from a newbie

Post by Bloodbane »

Welcome to TalkChess, and good luck with your chess engine.

1. Yes, but the gain is not big, maybe 10% or so (at least for me). I wouldn't worry about this yet, you have easier ways to gain elo. More about that later.

2. I think you should understand bitboards even though you might not use them, as almost all other engines use them and if you do not know how they work you'll have a hard time reading the code. Also, nothing is stopping you from getting to at least 2700 or 2800 even though you might not use them. I'm pretty sure there was a 3000+ engine which used a non-bitboard architecture, I just can't remember the name. I'm not really sure about the speed difference as I've never used anything other than bitboards, somebody else has to answer that. They are probably faster than other options but not by a huge amount.

3. This is a combination of two factors. First, you update your history heuristic info during the lower depth searches (see line 126 of search.cpp). Second, due to the exponential nature of the tree the searches to depths 1, 2, 3, 4, 5, and 6 cost relatively little compared to the search to depth 7. So the small amount of time you spend in the lower depth searches gains enough information to order your moves better so that in the end you search faster overall. If you turn off your history heuristic updating then I'd expect the IID loop to be slower.

Also, I took a look at your engine and I didn't see any glaringly obvious bugs in the evaluation and the search. However, you have quite a few low-hanging fruits: using the PV-move (which you had already noticed), principal variation search, transposition table (and using the TT move) and null move would probably boost the strenght of your engine by 500 elo or so. That's quite a lot more than what you would get by optimizing the speed of your engine. So I suggest you focus your efforts there.
Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
https://github.com/mAarnos
PK
Posts: 893
Joined: Mon Jan 15, 2007 11:23 am
Location: Warsza

Re: Questions about chess programming from a newbie

Post by PK »

first of all, congratulations for creating a working chess engine!

as for iterative deepening, understand one thing: search at depth d-1 takes only a fraction of time needed for search at depth d. for that reason the worst case cost of iterative deepening is small when you compare it to fixed depth search. and the truth is that you gain a lot once you learn to recycle move ordering information from shallower searches.

start with the following: add to Your search function a variable "ply", incremented with each recursion. at the root of the search You have ply == 0, and each search call makes the ply = ply+1; then create a global variable to record each best move at ply == 0. finally, change your move ordering at ply 0, making sure that best root move is always searched first.

why? first of all, chances are that the best move will not change in the next iteration, and starting from it you improve move ordering. secondly, at some stage you will be going to implement a time control like move in n seconds. if the search terminates at the beginning of the new iteration, you don't want to be caught searching a move inferior to your best move (your first choice can be wrong, but let your search find it out; and you definately don't want to start each iteration with Queen takes defended pawn just because it is the only available capture and terminate search at -8 pawns).

if you implement what I describe, please read about triangular pv array, which is basically the extension of the above reasoning to ply 1, ply 2 etc.
Aleks Peshkov
Posts: 892
Joined: Sun Nov 19, 2006 9:16 pm
Location: Russia

Re: Questions about chess programming from a newbie

Post by Aleks Peshkov »

I suggest you to implement Perft (and then Perft with Transposition Table) before working with alpha-beta.

During quiescence search you will probably need only first capture and discard the rest. To get it you create a full list of pseudo-legal captures, make each of them on the board and test if any opponent piece can attack the king. You make about 100 times more work then necessary.

Position::generate_position_key()
1) why you visit 120 squares when you have piece lists?
2) why you call this slow function every move? Why not change previous key in add_piece() and remove_piece().
mattbrah
Posts: 3
Joined: Sun Apr 12, 2015 7:33 pm

Re: Questions about chess programming from a newbie

Post by mattbrah »

1) why you visit 120 squares when you have piece lists?
2) why you call this slow function every move? Why not change previous key in add_piece() and remove_piece().
I did this out of ignorance. I will certainly try and use your suggestions. It's easy to forget about small things like this when you are trying to complete an entire engine. It's these kinds of small details that I appreciate you guys pointing out. Thank you.
mattbrah
Posts: 3
Joined: Sun Apr 12, 2015 7:33 pm

Re: Questions about chess programming from a newbie

Post by mattbrah »

Thank you so much for your thorough reply! I will definitely try to implement all of your suggestions. I appreciate it a ton.
op12no2
Posts: 489
Joined: Tue Feb 04, 2014 12:25 pm
Full name: Colin Jenkins

Re: Questions about chess programming from a newbie

Post by op12no2 »

Hi Matt, writing a chess engine as an introduction to C++ is kinda awesome! I have a version of my engine that is very similar to yours - an alpha/beta searcher. It does however sort root moves and go down the previous PV. You may or may not find it useful to read (no TT): http://op12no2.me/toys/lozza/lozzaab.js
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Questions about chess programming from a newbie

Post by Sven »

mattbrah wrote:Thank you so much for your thorough reply! I will definitely try to implement all of your suggestions. I appreciate it a ton.
Hi Matt,

welcome to the forum, and congrats to writing a C++ engine!

I strongly suggest to concentrate on eliminating bugs and getting basic things right before you start any kind of optimization. Obvious algorithmic improvements are certainly good but I would not bother with questions like "array or vector?" until your engine has passed the ELO 2000+ level.

Apart from bug fixing (although currently I did not encounter any bug) and of course "perft", as already mentioned, I would consider basic move ordering to be one of the next things to realize for you.

Good luck!

Sven
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Questions about chess programming from a newbie

Post by Sven »

Sven Schüle wrote:
mattbrah wrote:Thank you so much for your thorough reply! I will definitely try to implement all of your suggestions. I appreciate it a ton.
Hi Matt,

welcome to the forum, and congrats to writing a C++ engine!

I strongly suggest to concentrate on eliminating bugs and getting basic things right before you start any kind of optimization. Obvious algorithmic improvements are certainly good but I would not bother with questions like "array or vector?" until your engine has passed the ELO 2000+ level.

Apart from bug fixing (although currently I did not encounter any bug) and of course "perft", as already mentioned, I would consider basic move ordering to be one of the next things to realize for you.

Good luck!

Sven
Position::generate_position_key() has already been mentioned. I recommend to rewrite this part, changing the implementation into an incremental one. Currently you recalculate the position key (hash key) from scratch within each single call of make_move(). Furthermore, since you call make_move() with save=true (default argument) during legality checking this key recalculation occurs K*N times per node where K is a small constant but N is the number of pseudo-legal moves at that node. I would change both: update the position key incrementally and call make_move() with save=false when only making/unmaking moves for legality testing.

This is the kind of algorithmic improvements that I meant above, which you definitely need to do, it is not "optimization" but like going from O(N^2) to O(N). I guess it should speed up your search by a factor of around 3 or 4 in the current state.

Legality check can be further improved algorithmically. There is only a small fraction of pseudo-legal moves that can actually be illegal:
- check evasions,
- king moves,
- moves of pinned pieces, and
- en passant captures.
Therefore the effort to calculate the set of all pinned pieces of the moving side can help to drastically reduce the number of make/unmake pairs that you need for legality checking. But there is also a second way (and certainly also the combination of both) to reduce that effort: you can decide to postpone legality checking until the move is actually made during search, and let alpha-beta drop most of the did-I-leave-my-king-in-check tests, like this:

Code: Select all

bool inCheck = is_in_check&#40;);
PinInfo pinInfo = find_all_pins&#40;);
generate_moves&#40;inCheck&#41;;
for &#40;all moves&#41; &#123;
    make_move&#40;);
    if &#40;last_move_was_illegal&#40;inCheck, pinInfo&#41;) &#123;
        unmake_move&#40;);
        continue;
    &#125;
    int score = -search&#40;...);
    unmake_move&#40;);
    // back up score, ...
&#125;
User avatar
hgm
Posts: 27772
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Questions about chess programming from a newbie

Post by hgm »

By sub-optimal programming techniques and algorithms for move generation can slow you down a factor 10. But a poor search algorithm (i.e. no smart reductions and extensions) can easily slow you down a factor 100, and poor move ordering more than a factor 1000.

So worry about move ordering first. Searching the PV of the previous iteration first, and capture of the highest piece next should get you in business.