Beating Fairy-Max 4.8

[velmarin]

A new record.
How many teachers were abducted by the Ghost with fewer posts.

Big Henk!! You're my Idol

[hgm]

Do you think you could write a super simple engine that beats Fairy-Max easily ?

That depends on how you define 'super simple'. Adding true move sorting (i.e. first store the moves you generate in an array before you start searching any), rather than searching them as soon as the roll out of the move generator, and sorting killers amongst the first should certainly shrink the search tree for the same depth a lot.


[qoute]Nodes per second of Fairy-Max is at least five times more than Skipper2.

Skipper uses killer moves and non captures are sorted.[/quote]
I would expect that those techniques alone should already compensate for the lower node rate, at a reasonable time control (say 5 min/game).

Also King safety is more complicated.

At this moment Skipper searches two plies less deep than Fairy-Max. For instance it doesn't reduce depth at all when in check.

Two ply sounds like a lot, but you should realize that Fairy-Max' plies are a bit exaggerated, because it applies LMR to all non-captures, except the hash move. (There are no killer or good-history moves to exempt.)


So a very basic engine can already be some 400 Elo stronger than Fairy-Max. If it would be weaker, than this is really a strong indication that it is either grossly mistuned, or contains some crippling bugs. But, like I said, it is really useful to analyze a game where it loses, to see why it lost that game.

[bob]

This is sort of like trying to fix a car problem by randomly replacing parts, rather than doing some basic diagnostic work to determine what is wrong first...

Every loss can tell you something about a program, but you have to examine the loss to see what it is saying.

[hgm]

I guess that Fairy Max has advanced, but Olithink is almost surely the stronger engine.

Fairy-Max still uses the same search and evaluation, this is why the number is still at 4.8. Over time there have been some changes in the move generation, to make it more general (allow castling where the King moves 3 squares, finite-range sliders that move maximally 3, 4 or 5 squares, initial moves on non-pawns, bent sliders, which turn a corner, collider pieces that change direction on the square before an obstacle, instead of at the obstacle as hoppers do). And it supports Seirawan-Chess-style gating to introduce new pieces from the hand, multiple royalty (both absolute and extinction type), and a different promotion type for white and black. And an alternate winning condition for the royal reaching a certain area.

If anything, the extra branch instructions needed to test for these additional move types should have made it a bit slower, nodes/sec-wise. Fairy-Max also keeps track of the PV through a variant of the tri-angular-array method, and supports a multi-PV mode by keeping the root window (more) open.

Other changes have been in the interface part, to make the protocol driver co-evolve with XBoard: allowing variants of arbitrary names ('engine-defined variants'), and emitting setup commands to reconfigure the GUI's move generator, participating pieces and initial setup. And adding some engine-defined options to set a resign threshold, or to specify minor rule variations.

These changes allow it to play a much wider variety of Chess variants, and the repertoire of pre-configured variants with which it comes reflects this. (Seirawan Chess, Spartan Chess, Cambodian Chess, the Clobberers, Nutters and Rookies armies for Chess with differnt armies, Team-Mate Chess, Bifurcator Chess, King of the Hill, Charge of the Light Brigade were added.)

But for normal Chess Fairy-Max is still essentially (a slow compile of) the micro-Max 4.8 that appears in the CCRL list.

[Rein Halbersma]

If it is a bug it won't be a trivial one for all perfts and mate searches seams to go well.

By the way my visual studio express versions have no profilers so it makes it difficult to find computational bottlenecks.

Visual Studio 2015 Community Edtition does have free PGO, and for profiling you can use VerySleepy. Or go to Linux and use Valgrind.

[Henk]

Best result in days

[pgn]
[Event "Computer Chess Game"]
[Site "HP"]
[Date "2015.08.15"]
[Round "-"]
[White "Fairy-Max 4.8S"]
[Black "SkipperWinb"]
[Result "1/2-1/2"]
[TimeControl "60"]
[Annotator "1. +0.16 1... +0.00"]

1. c4 {+0.16/8} e6 {+0.00/8 1.3} 2. d4 {+0.11/8 4} c5 {+0.00/8 1.2} 3. Nc3
{+0.16/7 0.8} cxd4 {+0.00/8 1.2} 4. Qxd4 {-0.25/8 0.8} Nc6 {+0.00/9 1.2} 5.
Qf4 {-0.11/8 2.8} Nb4 {+0.00/8 1.1} 6. Nb5 {-0.17/7 1.7} Nc2+ {-0.02/9 1.1}
7. Kd1 {-0.13/9 1.5} Nxa1 {-0.01/10 1.1} 8. Nc7+ {-0.14/9 0.9} Ke7
{-0.01/10 1.1} 9. Nd5+ {-0.02/10 3} Ke8 {+0.00/12 1.0} 10. Nc7+
{-0.01/12 0.7} Ke7 {+0.00/14 1.0} 11. Nd5+ {-0.01/11 1.8} Ke8
{+0.00/14 1.0} 12. Nc7+ {-0.01/13 2.0} Ke7 {+0.00/15 1.0}
{XBoard adjudication: repetition draw} 1/2-1/2
[/pgn]

[hgm]

Do you think you could write a super simple engine that beats Fairy-Max easily ?

I got a bit carried away by this question. (I know, unwise...) So last week I spent writing a new engine for orthodox Chess, as a response to this challenge (and to relieve the 'after-ICGA blues). I started on Sunday night, got a bit carried away (so that I added lots of not-yet-used code to it that perhaps goes beyond 'super-simple'), and only made a first attempt to compile it on Thursday morning. (Took me all morning to solve all the typos...) Once I could run it I had to cure some 30 bugs, about 5 of which were design flaws. But last Sunday it could finally play a game without 'exiting unexpectedly' or making 'False illegal-move claims'. And in the 3rd full game it played it did score a win against Fairy-Max! I let ran a match last night, and it scored some 50%, with still a fair amount illegal-moves. (Another design flaw: when in check, I try to limit move generation to potential evasions, but I forgot the most important evasion of all, namely capturing the opponent King, so that it could move pinned pieces to deliver check.)

I am using only the piece-square evaluation part, interpolated between an end-game and opening score. No Pawn structure (passers, backward/isolated, doubled), King safety (pawn shield and near-attacks), mobility, patterns, drawishness, end-game (PKP, KBPK) recognizers (for which the code is all there, but not yet enabled, tested or debugged). Nothing was tuned; the PST elements were just 'pulled from the air'. It does not even evaluate a Bishop pair, (so it plays virtually every game with 2N vs 2B), and does not know KBK etc. is a draw. I am running another match against Fairy-Max now, and it leads by 77+/20=/52-. (Hmm, one false illegal-move claim, though, on a double-push interposition to a Bishop check...) Not exactly a land-slide victory, but it still forfeits some games in won positions, due to its rudimentary time management (always finishing iterations), and use of a TC that is rather sensitive to that (40 moves/min).

My plan is to release (after debugging the currently disabled features) the source code of it as a 'model engine' in the category 'very basic'. The source contains lots of comments (micro-Max style). Perhaps I will call it 'Simple'. (Or is that name already taken? As an alternative I could call it 'Kludgy'.) It will have options to switch the various evaluation features (drawishness, on or off.

[Henk]

Or call it Fairy-Simple.

By the way Skipper has no piece square table anymore. Perhaps that's why elo dropped with 100 points or more last months.

[hgm]

Or call it Fairy-Simple.

Cool!

It is not set up to do many fairy variants, however. The board is limited to 8x8 (I use the classical 0x88 test to see if moves stray off board), the number of piece types to 7, no provisions for hoppers or arbitrary finite-range moves.

I did design it to allow any move to make an e.p. capture on the side. Or to promote any piece to an arbitrary other. So perhaps I could put it to some real use as well, as engine for Mighty Lion Chess or Werewolf Chess, with some minor code changes.

By the way Skipper has no piece square table anymore. Perhaps that's why elo dropped with 100 points or more last months.

Why did you do that? Piece-square tables are almost free. In 'Simple' I store not only positional scores, but also the piece base value in these tables.

This is the header comment to the Search() routine

Code: Select all

/**************************************************************************************/
/* Search routine that does about everything in-line. Its structure is:               */
/* 1) Probe hash table                                                                */
/* 2) Determine if the preceding (non-null) move checked us (if hash did not tell us) */
/* 3) Apply (check-)extension and reductions (passed to us from from parent)          */
/* 4) Take hash cutoff if draft allows it                                             */
/* 5) (Lazy) evaluation of position (mobility and King safety guessed from parent)    */
/* 6) QS: Stand pat on lazy-eval score if good enough (with margin)                   */
/* 7) Generate moves; In QS only keep captures. Return +INF instantly on King capture */
/* 8) Search null move, for accepting its fail high or as dummy (see below)           */
/* 9) Calculate mobility and King safety (side effect of move gen and null move)      */
/* 10) QS: Try to stand pat again on precise evaluation                               */
/* 11) Validate hash move, and put it in front of move list                           */
/* 12) Store draw in hash entry for current position, to get rep-draws along branch   */
/* 13) Search moves, using IID starting at depth from hash probe (if valid) or d=1    */
/*     A) Loop over moves:                                                            */
/*         a) Move sort: extract best capture, or validate killers (if not yet done)  */
/*         b) Decode and make move                                                    */
/*         c) Recursion with self-deepening (fail-highs always will have full depth)  */ 
/*         d) In root: we can exit here for a chosen move, leaving it performed       */
/*         e) Unmake the move                                                         */
/*         f) Process the returned score (possibly cutting off move- and IID loop)    */
/*     B) Decide on continuation of self-deepening                                    */
/*     C) Stalemate correction on ultimate fail low (i.e. when all moves illegal)     */
/* 14) Hash store                                                                     */
/* 15) Delayed-loss bonus                                                             */
/*                                                                                    */
/* KLUDGE: Search can also be used for calculating one-sided mobility, by calling it  */
/* with trheshold argument set to INF+10. This suppresses the hash probe, and passing */
/* previousPly = 0 (null move) suppresses the check test, while depth > 0 suppresses  */
/* evaluation and stand-pat, so that we directly go into move generation. It then     */
/* returns with the mobility that is calculated during it.                            */
/**************************************************************************************/

int
Search (int startAlpha, int beta, int threshold, int mobilityGuess, int previousPly, int reduction, int depth, int extraDepth)
{
...
}

[matthewlai]

Do you think you could write a super simple engine that beats Fairy-Max easily ?


Nodes per second of Fairy-Max is at least five times more than Skipper2.

Skipper uses killer moves and non captures are sorted. Also King safety is more complicated.

At this moment Skipper searches two plies less deep than Fairy-Max. For instance it doesn't reduce depth at all when in check.

Giraffe can beat Fairy-Max pretty easily

Code: Select all

Rank Name                   Elo    +    - games score oppo. draws 
   1 Giraffe 63f71c3eb204   101   60   52    38   75%  -101    3% 
   2 Fairy-Max 4.8S        -101   52   60    38   25%   101    3% 

It also searches at about 1/5 the speed of Fairy-Max. However, it does have a world-class evaluation function.

Also, that means Skipper is searching at the same speed as Giraffe... which means there is something seriously wrong with Skipper performance-wise. Giraffe does a deep neural network evaluation for each position, which involves multiple large matrix-vector multiplications.

You should definitely find a profiler (several have been suggested in this thread) and see what Skipper is spending all its time on. Also, remember to turn on compiler optimizations.