low hanging fruit

[flok]

Hi,

I'm writing a chess program. Got the move generator from an other chess engine of mine. Alpha/beta works, transposition table works, quiescence ok, null move is fine.

Now what is the next step in speeding up the search?

Thanks.

[Henk]

Passed pawns are important. But I should not give advice for my engine is still crap.

[JVMerlino]

Hi,

I'm writing a chess program. Got the move generator from an other chess engine of mine. Alpha/beta works, transposition table works, quiescence ok, null move is fine.

Now what is the next step in speeding up the search?

Thanks.

Such a simple question, and yet it can be interpreted multiple ways. Do you mean nodes per second or time to depth? Do you JUST want this speedup or, more likely, would you like a strength increase as well?

Probably the easiest way to increase time-to-depth and HOPEFULLY get a strength increase as well is to implement reductions and pruning. But be forewarned, because you'll be tuning them forever.

Good luck!

jm

[Ferdy]

Hi,

I'm writing a chess program. Got the move generator from an other chess engine of mine. Alpha/beta works, transposition table works, quiescence ok, null move is fine.

Now what is the next step in speeding up the search?

Thanks.

Probably test it first, try to establish a base line (short TC games, long TC games, test suites scores).

Tune null move pruning, not overtune, since you still have other features to implement and tune later.

LMR, then try adding eval features, there are eval features that can increase your speed. Even the simple bishop and pawn color scoring is a big help even without implementing the full bishop mobility.

Test at medium TC (5 to 10 minutes + 3 inc), review the games, there a lot of ideas you can get from it. Also obvious bugs can be detected using this method.

[matthewlai]

Hi,

I'm writing a chess program. Got the move generator from an other chess engine of mine. Alpha/beta works, transposition table works, quiescence ok, null move is fine.

Now what is the next step in speeding up the search?

Thanks.

Killer moves will give you significant speedup while still guaranteeing the same result (no tradeoff).

Most other things (extensions and prunnings) will be better for some situations and worse for some others, and you just have to gamble.

Sorting captures by SEE (and moving negative captures all the way to the end) will help as well, but SEE is not very easy to get right.

[Sery]

For alpha-beta algorithm it is important to do a beta cutoff at the earliest possible move. In case when move ordering is very bad and all beta cutoffs are made at the last move, the search tree of alpha-beta is similar to minimax tree.
So, the good method to test and improve the search will be to find all beta cutoffs made after second, third, etc move and make sure that all of them are not mistakes of move ordering. For quiescence search that's also true.

[brtzsnr]

Few easy (3 lines max) things that gave a huge boost to my engine:

1. Two fold repetition at non-root nodes (~40ELO).
2. Better time management. In its first tournament my engine used 30s out of 5m+1s total time.
3. Mate distance pruning: don't search to depth 20 if you already have a 10 ply mate on another branch.
4. Check extension, but don't extend everything.
5. Passed pawns.
6. Something a bit more complicated is phased move generation: return hash move (without generating the moves), return best move (without sorting the moves), then sort and return (this last step can be refined further).

[flok]

Such a simple question, and yet it can be interpreted multiple ways. Do you mean nodes per second or time to depth? Do you JUST want this speedup or, more likely, would you like a strength increase as well?

It currently does 500-750k nodes/s. Not bad I think for a non-bitboard engine. But it takes days to reach eg depth 20. Depth 10 takes 5,2 seconds. So that probably can be improved.

Probably the easiest way to increase time-to-depth and HOPEFULLY get a strength increase as well is to implement reductions and pruning. But be forewarned, because you'll be tuning them forever.

What kind of red/pru are you thinking of?

[flok]

Killer moves will give you significant speedup while still guaranteeing the same result (no tradeoff).

Do you mean https://chessprogramming.wikispaces.com ... +Heuristic ?
[/url]

[matthewlai]

Killer moves will give you significant speedup while still guaranteeing the same result (no tradeoff).

Do you mean https://chessprogramming.wikispaces.com ... +Heuristic ?
[/url]

Yeap!