Low hanging fruit?

[AndrewShort]

I would love some pointers on what to work on next...

Here is what I have implemented:

* alphabeta, negamax style
* 2 killer slots
* hash table, hash-best move used
* move ordering, including mvv/lva for captures
* principal variation search (PVS)
* null-move heuristic
* basic iterative deepening with aspiration window
* each iteration tries PV from previous iteration first
* piece-square tables for positional material bonus

My move generation is slow - believe it or not I use an 8x8 2d board array to store the board and generate legal moves. I have not looked into bitboards... I have focused on getting the tree smaller, rather than making move generation faster, since obviously I had higher payoff with smaller search trees...

My eval is very basic - I incrementally track material, using piece-square tables for positional bonuses. Castling is given a bonus. That's it.

I do not have any kind of Quiescent Search or Static Exchange Evaluator either. (for this reason, the PV often has the last move showing a hanging piece, but at depth 9 and more, the engine still plays surprisingly well without QS and SEE).

I have no pondering.

I have nothing else (e.g. Razoring, Internal Iterative Deepening, etc etc).

What is my low hanging fruit? (in terms of making th engine faster and/or better)

[Uri Blass]

My guess is that implementing qsearch is the most important thing that can help your program to become better.

Uri

[bob]

I would love some pointers on what to work on next...

Here is what I have implemented:

* alphabeta, negamax style
* 2 killer slots
* hash table, hash-best move used
* move ordering, including mvv/lva for captures
* principal variation search (PVS)
* null-move heuristic
* basic iterative deepening with aspiration window
* each iteration tries PV from previous iteration first
* piece-square tables for positional material bonus

My move generation is slow - believe it or not I use an 8x8 2d board array to store the board and generate legal moves. I have not looked into bitboards... I have focused on getting the tree smaller, rather than making move generation faster, since obviously I had higher payoff with smaller search trees...

My eval is very basic - I incrementally track material, using piece-square tables for positional bonuses. Castling is given a bonus. That's it.

I do not have any kind of Quiescent Search or Static Exchange Evaluator either. (for this reason, the PV often has the last move showing a hanging piece, but at depth 9 and more, the engine still plays surprisingly well without QS and SEE).

I have no pondering.

I have nothing else (e.g. Razoring, Internal Iterative Deepening, etc etc).

What is my low hanging fruit? (in terms of making th engine faster and/or better)

I would next do a SEE, so that you can get better capture ordering, and you can also eliminate many losing captures from the q-search... SEE is not hard to write, and you can use Crafty as a pattern there...

Then you have two ways to go... more evaluation, or more informed search. Search additions would include extensions for things like check, one reply to check, etc, and reductions that have been discussed here many times. Evaluation is probably harder overall unless you are a pretty strong chess player.

[hgm]

Quiescence Search is absolutely essential to get reasonable play. (Searching recaptures is the absolute minimum, but it is better to search all captures.)

Then you need rep-draw detection, even if only at game level. Without it, you will hardly win any game, no matter how much better you are than the opponent. Without rep-draw detection it is also almost impossible to test your progres: huge improvements often result in a zero score increase in the test gauntlets.

In the evaluation King safety is extremely important (e.g. Pawn shield). Some Pawn-structure evaluation also helps, to prevent the program losing early by scattering its Pawns so they become undefendable. (The most important term being one that penalizes Pawn moves if the Pawn two files left or right from the fromSquare is missing.) Be sure the score for pushing Pawns is sufficiently positive in the end-game.

It is very important to have some form of check extension (e.g. extend all check evasions). Without it, you will often be surprised by deep mates in positions with a winning material advantage.