patricia devlog

[Whiskers]

Hi, I'll be posting updates on my new engine Patricia here.
The link to the code is https://github.com/Adam-Kulju/Patricia and the plan is that it will contain both the engine and filtering programs to grab different kinds of "aggressive positions" out of larger datasets (I plan to use Willow datasets at first).

I have several filtering programs already wrote up so started on my engine a couple days ago. I got a basic movegen working, with a perft of 20m nodes per second non bulk. It's much faster than Willow's and the code looks a lot nicer too. For example here is my attack detection code. It still needs comments and more descriptive variable names in places but it's a million times neater than Willow code.

Code: Select all

bool attacks_square(Position position, int sq, int color) {
  int opp_color = color ^ 1, v = -1;
  for (int d : AttackRays) {
    v++;
    int temp_pos = sq + d;

    while (!out_of_board(temp_pos)) {
      int piece = position.board[temp_pos];
      if (!piece) {
        temp_pos += d;
        continue;
      } else if (get_color(piece) == opp_color) {
        break;
      }

      piece -= color;

      if (piece == Pieces::WQueen || (piece == Pieces::WRook && v < 4) ||
          (piece == Pieces::WBishop) && v > 3){
            return true;
          }
      else if (piece == Pieces::WPawn) {
        if (temp_pos == sq + d && (color ? (v > 5) : (v == 4 || v == 5))) {
          return true;
        }
      }
      else if (piece == Pieces::WKing && temp_pos == sq + d) {
        return true;
      }
      break;
    }

    temp_pos = sq + KnightAttacks[v];
    if (!out_of_board(temp_pos) &&
        position.board[temp_pos] - color == Pieces::WKnight) {
      return true;
    }
  }
  return false;
}

[Whiskers]

I wrote a simple alpha beta search with transposition tables. I need to clean up the code before I go any further, because my bad habits are trying to creep in again.

I also found a compiler bug today - I was trying to profile Patricia with gprof, but the compiler kept inlining everything into one function, making it very unhelpful. I added the flag "-no-inline" to my compile script, and was rather surprised to discover that it caused the program to segfault on program exit. After some digging I was surprised to see that even this most minimal case is able to trip a segfault:

Code: Select all

#include <vector>
std::vector<int> a;
int main() {
    return 0;
}

when compiled with these flags on clang.

Code: Select all

-O2 -flto -pg -fno-inline

Apparently flto has a couple odd bugs: https://github.com/llvm/llvm-project/issues/69398 is a similarly absurd one. Whatever the cause of it, removing the -flto flag fixed the issue and I was able to profile at ease, but that's an hour (maybe more, honestly) of my life that I'll never get back

[Frank Quisinsky]

Adam ... is full of ideas and energy.
You will make a lot of people happy with this work.

I would like to help, but I don't know what I can do.
And I have no time for the next 2-3 weeks (I will be happy if I can update my tournaments).
But after that time I can give helps if you need it.

I hope that many people will give you their own ideas.
Maybe you can use this and that in combination with all your own ideas.

I follow ...
Patricia ... hm, my sister's second name.
So your project must be successful!!

[Whiskers]

Adam ... is full of ideas and energy.
You will make a lot of people happy with this work.

I would like to help, but I don't know what I can do.
And I have no time for the next 2-3 weeks (I will be happy if I can update my tournaments).
But after that time I can give helps if you need it.

I hope that many people will give you their own ideas.
Maybe you can use this and that in combination with all your own ideas.

I follow ...
Patricia ... hm, my sister's second name.
So your project must be successful!!

Patricia is the name of my other rabbit (Willow being the first), sadly she passed away a couple months. I miss her
I think the thing I would most appreciate is just for the word of what I'm doing to spread. I eventually plan to make several surveys to try and reach an alternative algorithm to "what makes an aggressive position" other than the EAS-score, and compare the two, and will probably try to maximize both at the same time. So that will be fun

[Whiskers]

Yesterday I got a simple NNUE (trained on some Willow data I had lying around) working and added a quiescence search - that'll probably bring Patricia up to 1500+ CCRL strength. The final step for laying the foundations is writing uci protocol; after that it's time to test the EAS score of the first "version", it should be a good starting baseline to work from.

[lithander]

Hey Adam, I'm looking forward to read your devlog! Also it's great to see you're sticking to the mailbox approach!

Could you elaborate on your plans of how to make your engine have a specific style? What was the reasoning behind and the details of your "intentional errors in the training data" approach in Willow? Are you going to follow the same general strategy for Patricia?

[Whiskers]

Hey Adam, I'm looking forward to read your devlog! Also it's great to see you're sticking to the mailbox approach!

Could you elaborate on your plans of how to make your engine have a specific style? What was the reasoning behind and the details of your "intentional errors in the training data" approach in Willow? Are you going to follow the same general strategy for Patricia?

The idea behind Willow's intentional errors in datagen:
Suppose you have two different positions - one is quiet and many moves maintain the balance of the position, but the other has a ferocious attack and one move that isn't the best one will mean you succumb to it. If you have the engine play the second best move 5% of the time, it won't affect the game result in most games, but when an engine is trying to defend against initiative then that second best move can often sink the whole game for the defending side. This results in more wins than losses for the attacking side in the dataset, and thus the net learns that attacking positions are good. I also occasionally performed random moves in datagen for that reason.

Of course, this had the trade-off of losing somewhere close to 30 elo compared to normal datagen, and I eventually got greedy and switched to a normal datagen style.

My work-in-progress plan for Patricia is a bit different, and involves a dual net. One of the nets will be used for most positions, and will either be trained normally or with a slightly modified datagen. The other net will come into play when a heuristic that detects if a position is "aggressive" passes, and will be trained on exclusively positions of that type in order to excel in them. I'll also give a fairly large bonus for going into those positions in search so that it's actually incentivized to go into those lines. There's wilder things I could potentially do (make the loss function somehow incorporate aggression when training a net, for example) but I'll cross that bridge when I get to it

[Whiskers]

Yesterday I got uci working and played a 1,000 game match in order to get (a) a better estimate of Patricia's strength and (b) a baseline estimate for Patricia's aggressiveness. I learned two things:

1: Patricia has absolutely no right to be this strong. She demolished Apotheosis 2.0 (1950 CCRL blitz) by a score of 838 wins, 63 draws, and 99 losses, corresponding to an estimated ELO strength of up to 2300 CCRL blitz. This is disgusting considering I have no search techniques other than alpha-beta, transposition tables, simple move ordering, and quiescence search. I will try to keep this from turning into a rant but NNUE has really sucked all the fun out of chess. It should not be this easy to make a chess program that can wipe out anyone who's not a master strength player. It's not even a net using Leela data, it's just a simple small 128 HL net trained on some Willow positions I had lying around.

2: From the 1000 game sample, Patricia's EAS score is 137990, which would put it 3rd on the EAS rating list behind Torch and Stockfish (it's obviously not comparable due to the huge strength difference, though). I plan one more match of Patricia against a stronger engine to see how this changes, before trying out my first basic "incentivize fun positions" strategy.

[Whiskers]

I ran another 1000-game match against Willow 2.5 and while Patricia was still slightly stronger, Willow easily won the EAS battle.

Code: Select all

Rank  EAS-Score  sacs   shorts  draws  moves  Engine/player 
-------------------------------------------------------------------
   1    158447  12.46%  33.43%  20.65%   53   Willow 2.5  
   2     58188  12.96%  11.23%  22.28%   71   Patricia 0.1  
   
 

Looks like I was right when my first release called Willow an "extremely aggressive engine"

First I need to fix this qsearch problem that leads to depth 1 searches taking tens of thousands (or more) of nodes, then I'm going to give a simple bonus to positions where the evaluation score significantly exceeds the material score of the position and see what that does to the EAS score.

[Whiskers]

I fixed up my quiescence search yesterday (it was a mvv-lva bug) and added the first "heuristic" to make it play aggressively. It's a simple one; if we are not up in material, and the position evaluation is 200+ cps better than the material evaluation, and neither side is completely won (because the network tends to exaggerate evals way past the material difference in pretty much all +5 or more positions), then the eval score for that position gets a flat 50 cp bonus.

The win rate was about the same (Patricia is 30-40 elo over willow), but the move ordering fix means this version of Patricia quite a bit weaker than it would be with the raw net eval. But the EAS scores look good!

Results:

Code: Select all

Rank  EAS-Score  sacs   shorts  draws  moves  Engine/player 
-------------------------------------------------------------------
   1    104428  14.35%  10.49%  14.86%   69   Patricia 0.1  
   2     86880  08.83%  24.68%  27.03%   58   Willow 2.5  
   

Outperforming Willow on my first attempt
I'm going to work on a couple more filtering programs and then try and see if I can't write up some surveys with positions taken from different filtered files.