Stockfish 7 progress

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
clumma
Posts: 177
Joined: Fri Oct 10, 2014 8:05 pm
Location: Berkeley, CA

Re: Stockfish 7 progress

Post by clumma » Sun Jan 17, 2016 8:41 pm

lucasart wrote:Actually there is one idea worth mentionning: Counter Moves History. It was introduced by Stefan Geschwenter, and proved to be worth quite a bit of elo, as it was later fine tuned, and used in various places (thanks to VoyagerOne who managed to get quite a bit of elo out of this CMH).
Aha, VoyagerOne's commits on Oct 12 and Oct 21 could be responsible.
As far as I know, this idea did not exist in the "litterature", and is unique to SF. Although, I suppose every top engine has now copied it.
Is it the same as "countermove heuristic"
https://chessprogramming.wikispaces.com ... +Heuristic
?

-Carl

clumma
Posts: 177
Joined: Fri Oct 10, 2014 8:05 pm
Location: Berkeley, CA

Re: Stockfish 7 progress

Post by clumma » Sun Jan 17, 2016 8:51 pm

MikeB wrote:I am fairly certain over the last 7 months or so, since I have been following it, this was the largest single patch worth 8 Elo
Another SMP thing, so not related to Pohl's graph, but very interesting anyway- thanks!
I hope it continues - these are good times for those who enjoy chess engines.
Indeed!

-C.

User avatar
lucasart
Posts: 3106
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Stockfish 7 progress

Post by lucasart » Mon Jan 18, 2016 5:05 am

clumma wrote:
lucasart wrote:Actually there is one idea worth mentionning: Counter Moves History. It was introduced by Stefan Geschwenter, and proved to be worth quite a bit of elo, as it was later fine tuned, and used in various places (thanks to VoyagerOne who managed to get quite a bit of elo out of this CMH).
Aha, VoyagerOne's commits on Oct 12 and Oct 21 could be responsible.
As far as I know, this idea did not exist in the "litterature", and is unique to SF. Although, I suppose every top engine has now copied it.
Is it the same as "countermove heuristic"
https://chessprogramming.wikispaces.com ... +Heuristic
?

-Carl
No. It's not the Countermove heuristic, which SF also has.

CMH is quite different. Have a look at the code.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Stockfish 7 progress

Post by Evert » Mon Jan 18, 2016 9:12 am

lucasart wrote: No. It's not the Countermove heuristic, which SF also has.

CMH is quite different. Have a look at the code.
I for one find source code eminently unsuitable to explain ideas. I prefer human languages for that (not to say that source code isn't useful in addition, but as a primary source of information...). At the very least it helps to not be confused by implementation details.

So if I understand correctly, the idea is to have a second history table (say H') that is indexed by the previous move rather than the current move. This is updated in a similar way to the usual history table (say H), and the history score for a move is calculated as H[this move] + H'[previous move]?

User avatar
lucasart
Posts: 3106
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Stockfish 7 progress

Post by lucasart » Mon Jan 18, 2016 9:35 am

Evert wrote:
lucasart wrote: No. It's not the Countermove heuristic, which SF also has.

CMH is quite different. Have a look at the code.
I for one find source code eminently unsuitable to explain ideas. I prefer human languages for that (not to say that source code isn't useful in addition, but as a primary source of information...). At the very least it helps to not be confused by implementation details.

So if I understand correctly, the idea is to have a second history table (say H') that is indexed by the previous move rather than the current move. This is updated in a similar way to the usual history table (say H), and the history score for a move is calculated as H[this move] + H'[previous move]?
No. CMH is a history table of history tables.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Stockfish 7 progress

Post by Gerd Isenberg » Mon Jan 18, 2016 10:06 am

Evert wrote:
lucasart wrote: No. It's not the Countermove heuristic, which SF also has.

CMH is quite different. Have a look at the code.
I for one find source code eminently unsuitable to explain ideas. I prefer human languages for that (not to say that source code isn't useful in addition, but as a primary source of information...). At the very least it helps to not be confused by implementation details.

So if I understand correctly, the idea is to have a second history table (say H') that is indexed by the previous move rather than the current move. This is updated in a similar way to the usual history table (say H), and the history score for a move is calculated as H[this move] + H'[previous move]?
The Datastructure is a countertable[piece][toSq] of countertables[piece][toSq], indexed by a pair of move and countermove which occured two and one ply before:

Code: Select all

typedef Stats<Value, true> CounterMoveStats;
typedef Stats<CounterMoveStats> CounterMoveHistoryStats;

 // Bonus for prior countermove that caused the fail low
    else if (    depth >= 3 * ONE_PLY
             && !bestMove
             && !inCheck
             && !pos.captured_piece_type&#40;)
             && is_ok&#40;&#40;ss - 1&#41;->currentMove&#41;
             && is_ok&#40;&#40;ss - 2&#41;->currentMove&#41;)
    &#123;
        Value bonus = Value&#40;&#40;depth / ONE_PLY&#41; * &#40;depth / ONE_PLY&#41; + depth / ONE_PLY - 1&#41;;
        Square prevPrevSq = to_sq&#40;&#40;ss - 2&#41;->currentMove&#41;;
        CounterMoveStats& prevCmh = CounterMoveHistory&#91;pos.piece_on&#40;prevPrevSq&#41;&#93;&#91;prevPrevSq&#93;;
        prevCmh.update&#40;pos.piece_on&#40;prevSq&#41;, prevSq, bonus&#41;;
    &#125;
Also mentioned in Crafty 25.0 readme (Added a follow-up idea).
* Added the "counter-move" heuristic for move ordering (Jos Uiterwijk, JICCA) which simply remembers a fail high move and the move at the previous ply. If the hash, captures or killer moves don't result in a fail high, this move is tried next. No significant cost, seems to reduce tree size noticeably. Added a follow-up idea based on the same idea, except we pair a move that fails high with the move two plies back, introducing a sort of "connection" between them. This is a sort of "plan" idea where the first move of the pair enables the second move to fail high. The benefit is that this introduces yet another pair of good moves that get ordered before history moves, and is therefore not subject to reduction. I have been unable to come up with a reference for this idea, but I believe I first saw it somewhere around the time Fruit showed up, I am thinking perhaps in the JICCA/JICGA. Any reference would be appreciated.
I also read about the idea some time ago, but can't actually remember what it was ...

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Stockfish 7 progress

Post by Evert » Mon Jan 18, 2016 10:36 am

Gerd Isenberg wrote:
Evert wrote:
lucasart wrote: No. It's not the Countermove heuristic, which SF also has.

CMH is quite different. Have a look at the code.
I for one find source code eminently unsuitable to explain ideas. I prefer human languages for that (not to say that source code isn't useful in addition, but as a primary source of information...). At the very least it helps to not be confused by implementation details.

So if I understand correctly, the idea is to have a second history table (say H') that is indexed by the previous move rather than the current move. This is updated in a similar way to the usual history table (say H), and the history score for a move is calculated as H[this move] + H'[previous move]?
The Datastructure is a countertable[piece][toSq] of countertables[piece][toSq], indexed by a pair of move and countermove which occured two and one ply before:

Code: Select all

typedef Stats<Value, true> CounterMoveStats;
typedef Stats<CounterMoveStats> CounterMoveHistoryStats;

 // Bonus for prior countermove that caused the fail low
    else if (    depth >= 3 * ONE_PLY
             && !bestMove
             && !inCheck
             && !pos.captured_piece_type&#40;)
             && is_ok&#40;&#40;ss - 1&#41;->currentMove&#41;
             && is_ok&#40;&#40;ss - 2&#41;->currentMove&#41;)
    &#123;
        Value bonus = Value&#40;&#40;depth / ONE_PLY&#41; * &#40;depth / ONE_PLY&#41; + depth / ONE_PLY - 1&#41;;
        Square prevPrevSq = to_sq&#40;&#40;ss - 2&#41;->currentMove&#41;;
        CounterMoveStats& prevCmh = CounterMoveHistory&#91;pos.piece_on&#40;prevPrevSq&#41;&#93;&#91;prevPrevSq&#93;;
        prevCmh.update&#40;pos.piece_on&#40;prevSq&#41;, prevSq, bonus&#41;;
    &#125;
Ok, so that's basically history[prev_move][move] then?
Also mentioned in Crafty 25.0 readme (Added a follow-up idea).
* Added the "counter-move" heuristic for move ordering (Jos Uiterwijk, JICCA) which simply remembers a fail high move and the move at the previous ply. If the hash, captures or killer moves don't result in a fail high, this move is tried next. No significant cost, seems to reduce tree size noticeably. Added a follow-up idea based on the same idea, except we pair a move that fails high with the move two plies back, introducing a sort of "connection" between them. This is a sort of "plan" idea where the first move of the pair enables the second move to fail high. The benefit is that this introduces yet another pair of good moves that get ordered before history moves, and is therefore not subject to reduction. I have been unable to come up with a reference for this idea, but I believe I first saw it somewhere around the time Fruit showed up, I am thinking perhaps in the JICCA/JICGA. Any reference would be appreciated.
I also read about the idea some time ago, but can't actually remember what it was ...
Isn't that a "continuation"? Same indexing as a counter move, except you use your own last move (ante-previous move) instead of the last move?
I wouldn't be surprised if that has been thought of independently several times.

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Stockfish 7 progress

Post by Gerd Isenberg » Mon Jan 18, 2016 2:10 pm

Evert wrote: Ok, so that's basically history[prev_move][move] then?
Yes
Evert wrote: Isn't that a "continuation"? Same indexing as a counter move, except you use your own last move (ante-previous move) instead of the last move?
I wouldn't be surprised if that has been thought of independently several times.
Yes, you are right. After looking to the sources, things in Crafty are quite different. It has counter_move[4096] and move_pair[4096] to associate best moves as counter1,2 of move[ply - 1] and pair1,2 of move[ply - 2] (in history.c), while Stockfish maintains the mentioned array of history tables (with counters), indexed by two consecutive moves of both sides, that is move and counter-move.

voyagerOne
Posts: 154
Joined: Tue May 17, 2011 6:12 pm

Re: Stockfish 7 progress

Post by voyagerOne » Mon Jan 18, 2016 4:36 pm


Post Reply