Please help with Plankton

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.
Post Reply
ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Please help with Plankton

Post by ianm » Sat Jun 27, 2020 6:13 am

Hi all

I've written a small chess engine (Plankton), the main aim being to have a fairly portable engine than can be ported to different microcontrollers. But I wanted to see how it would go with a hash table. I've been testing it against TSCP and the last round of 100 games Plankton won about 73% of the games. That's cool, but looking at game 13, Plankton returned a mate score in this position: k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31 with Bf3+. So occasionally it's making some pretty dumb moves. I suspect this is an issue with my hash table implementation. I'd really appreciate any insight into what could be wrong. Here is the AB search code:

Code: Select all

const int16_t absearch(int16_t alpha, int16_t beta, uint8_t depth, const uint8_t null_move)
{
   // if depth reached then return the score from quiesce
   if (!depth) return quiesce(alpha,beta);

   eo.nodes++;

   // check if search time up
   if ((eo.nodes&8191)==0 && millis()>eo.stop_time) eo.stop_search = true;

   pvl[ply] = ply;

   // if this isn't the root of the search tree (where we have
   // to pick a move and can't simply return 0) then check to
   // see if the position is a repeat if so, we can assume that
   // this line is a draw and return 0

   if (ply && reps()) return 0;

   // don't search too deep
   if (ply>=MAX_PLY-1) return eval();

   // if in check then keep searching
   const uint8_t in_check = king_attack(side);
   if (in_check)
   {
      depth++;
////?
//      if (eo.stop_search) printf("ignoring timeout!\r\n");
      eo.stop_search = false;
   }

   // false checkmate score
   //k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31 
   //fen 8/2r4k/p5p1/PP6/b2R1PPP/7r/3K4/6R1 b - - 0 46
   //fen rnb4N/p1p4Q/2k1p2p/1p1n4/1b4q1/8/PP3PPP/1RK4R b - - 5 23 ***
#if HASH_TABLE_ENABLE
   const uint32_t hi = hk%MAX_HASH_TABLE;
   if (ply)
   {
      if (ht[hi].key==hk && ht[hi].depth>=depth && (ht[hi].flag&FL_SIDE)==side)
      {
         int16_t s = ht[hi].score;
         if (s>MATE_VALUE) s -= ply; else if (s<-MATE_VALUE) s += ply;
         if (ht[hi].flag&HASH_EXACT) {stats.nhash++; return s;}
         else if ((ht[hi].flag&HASH_BETA) && s>=beta) {stats.nhash++; return beta;}
         else if ((ht[hi].flag&HASH_ALPHA) && s<=alpha) {stats.nhash++; return alpha;}
      }
   }
#endif

#if NULLMOVE_ENABLE
   if (null_move && !in_check && ply && depth>3)
   {
      int16_t nullmat = 0;
      uint8_t p = EMPTY;
      for (uint8_t i=0;i<64;i++)
      {
         if ((p=b[i]&0xf)==EMPTY) continue;
         if ((p&0x07)==PAWN) continue;
         if ((p&FL_SIDE)!=side) continue;
         nullmat += (white_scores[p]+black_scores[p]);
      }
      if (nullmat>1400)
      {
         donullmove();
         int16_t v = -absearch(-beta, -beta+1, depth - 1 - 2, false);
         undonullmove();
         if (eo.stop_search) return 0;
         if (v>=beta && abs(v)<MATE_VALUE)
         {
            return beta;
         }
      } 
   }
#endif

   // loop through the moves
   gen_all_moves(side);

#if HASH_TABLE_ENABLE
   if (ht[hi].key==hk)
   {
      const uint8_t origin = ht[hi].origin;
      const uint8_t target = ht[hi].target;
      for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
      {
         // don't replace the PV!
         if (ml[i].order==65535u) continue;
         if (origin==ml[i].m.origin && target==ml[i].m.target)
         {
            ml[i].order = 65000u;
            stats.hashorder++;
            break;
         }
      }
   }
#endif

   int16_t old_alpha = alpha;
   int16_t best_score = -MAX_VALUE;
   move_t best_move = {0};
   uint8_t legal_move = 0;
   uint8_t move_ordering = true;

   for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
   {
      if (move_ordering) order_next_move(i);
      move_ordering = ml[i].order>0;
      if (!domove(ml[i].m)) continue;
      
      legal_move++;

#if LMR_ENABLE
      int16_t v = 0;
      if (depth<4 || legal_move==1 || in_check || ml[i].order>60000u)
      {
         v = -absearch(-beta, -alpha, depth-1, true);
      }
      else
      {
         const uint8_t reduce = ml[i].order==0?2:1;
         //const uint8_t reduce = ml[i].order<60000?2:1;
         v = -absearch(-beta, -alpha, depth-1-reduce, false);
         if (v>alpha)
         {
            v = -absearch(-beta, -alpha, depth-1, true);
         }
      }
#else
      int16_t v = -absearch(-beta, -alpha, depth-1, true);
#endif
      undomove();
      if (eo.stop_search) return 0;
      if (v>best_score)
      {
         // update the PV
         ASSERT(ply+1<MAX_PLY);
         pv[ply][ply].m = ml[i].m;
         for (uint8_t j=ply+1;j<pvl[ply+1];j++) pv[ply][j] = pv[ply+1][j];
         pvl[ply] = pvl[ply+1];
         best_score = v;
         best_move = ml[i].m;
         if (v>alpha)
         {
            // since there was a cutoff increase the history or
            // "curiosity" heuristic (this is a low memory version
            // of the history heuristic which does a better job
            // than nothing but not as good as full history - the
            // difference in memory usage is significant!)
#if CURIOSITY_HEURISTIC
            if (depth>2 && ml[i].m.capture==EMPTY)
               curiosity[ml[i].m.target] += depth;
#elif HISTORY_HEURISTIC
            if (depth>2 && ml[i].m.capture==EMPTY)
               history[ml[i].m.origin][ml[i].m.target] += depth;
#endif
            if (v>=beta)
            {
               // record killers
               if (ml[i].m.capture==EMPTY)
               {
                  killers[2][ply] = killers[1][ply];
                  killers[1][ply] = killers[0][ply];
                  killers[0][ply] = ml[i].m;
               }
#if HASH_TABLE_ENABLE
               // store hash table entry
               ht[hi].key = hk;
               ht[hi].origin = best_move.origin;
               ht[hi].target = best_move.target;
               ht[hi].depth = depth;
               ht[hi].score = beta;
               ht[hi].flag = side|HASH_BETA;
#endif

               return beta;
            }
            alpha = v;
         }
      }
   }

   // if no legal moves then checkmate or stalemate
   if (!legal_move)
   {
      if (in_check)
         return -MAX_VALUE + ply;
      else
         return 0;
   }

#if HASH_TABLE_ENABLE
   ht[hi].key = hk;
   ht[hi].origin = best_move.origin;
   ht[hi].target = best_move.target;
   ht[hi].depth = depth;
   ht[hi].flag = side;
   if (alpha==old_alpha)
   {
      ht[hi].flag |= HASH_ALPHA;
      ht[hi].score = alpha;
   }
   else
   {
      ht[hi].flag |= HASH_EXACT;
      ht[hi].score = best_score;
   }
#endif

   return alpha;
}
Thanks again. Cheers, Ian

User avatar
hgm
Posts: 24607
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Please help with Plankton

Post by hgm » Sat Jun 27, 2020 1:26 pm

Staring at the code is usually not an efficient way for solving problems like this, if it solves anything at all. Better is to equip your program with the infra-structure necessary to resolve problems like this. What I always do is have the engine keep track of the path to the current node, and put diagnostic print statements that are only executed if that path satisfied a certain condition (usually that its first N moves must be equal to something). That way I can control in which nodes it prints.

It is then very useful to print move, score and best score so far (and possibly alpha and beta) after the recursive call; from this it is usually obvious which move has a wrong score, and by adding that to the path where you print you then get the same thing in the daughter, etc., until you zoomed in on the node where the error is generated.

If the erroneous score comes from a hash hit you let it print the hash key. You can put a print statement at the hash store that prints the path to the node when a store occured (plus what was stored); by following up that path you can then continue to search for the origin of the wrong score. (And check whether the position that stored the hash entry was indeed the same as the one that retrieved it.)

Ras
Posts: 1393
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Please help with Plankton

Post by Ras » Sat Jun 27, 2020 4:43 pm

ianm wrote:
Sat Jun 27, 2020 6:13 am
a fairly portable engine than can be ported to different microcontrollers.
Cool - my CT800 is running on a Cortex-M4!
So occasionally it's making some pretty dumb moves. I suspect this is an issue with my hash table implementation.
Try to disable the hash and see whether the problem goes away.

Another common bug in mid-range engines is wrong stalemate or even mate detection: if the position is so good or so bad that ALL moves are pruned away, the loop over the available moves is wrongly evaluated to "no legal move", i.e. mate or stalemate. The symptom is that the engine does something totally stupid and even thinks the eval is OK. The eval then drops once the position is on the board.
Rasmus Althoff
https://www.ct800.net

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

Re: Please help with Plankton

Post by lucasart » Mon Jun 29, 2020 4:44 am

Another common bug in mid-range engines is wrong stalemate or even mate detection: if the position is so good or so bad that ALL moves are pruned away, the loop over the available moves is wrongly evaluated to "no legal move", i.e. mate or stalemate. The symptom is that the engine does something totally stupid and even thinks the eval is OK. The eval then drops once the position is on the board.
indeed. I got fed up with that. issues like this arise anytime you experience with pruning mechanism. it's so easy to break things in subtle ways that mating bugs will occur rarely in peculiar conditions (not caught by testing which focuses on game results and large number statistics).

I coded a radical solution to this problem in Demolito:

Code: Select all

// Return worst possible score when all moves are pruned
if (bestScore <= -MATE) {
    assert(bestScore == -MATE);
    return max(alpha, mated_in(ply + 1));
}
I also put assert in score to/from hash score conversion (ply adjust) to verify that I never store or retrieve an impossible mate score (give current ply).

Double seatbelt!
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
hgm
Posts: 24607
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Please help with Plankton

Post by hgm » Mon Jun 29, 2020 5:18 am

This apparently supposes that you detect true stalemates somewhere earlier.

I just had a problem like this in the tiny AI of the Interactive Diagram. After I added a stalemate detection, which corrects bestScore to 0 when it was left at -MATE, and an additional null move searched for the purpose scores better than that, it saw many false stalemates. It turned out I had inadvertantly pruned away the stand-pat when eval <= alpha, i.e. this didn't update bestScore to eval (or alpha).

I now made sure that every move that is pruned is treated like it has score alpha. And I still had to be careful that other losing conditions that it is not illegal to expose yourself to (such as King baring or allowingthe opponent King to reach a goal square), and thus are no reason for claiming stalemate, do not return -MATE but -MATE+1. And then correct all bestScore <= -MATE+1 for the ply level, after correctimg only bestScore == -MATE for stalemate.

ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Re: Please help with Plankton

Post by ianm » Mon Jun 29, 2020 5:35 am

OK, I might have found the issue (or maybe a new one). I wasn't explicitly storing the mate score. I can't verify this is a fix for the actual position since the issue isn't reproducible. Anyway, here is the code:

Code: Select all

const int16_t absearch(int16_t alpha, int16_t beta, uint8_t depth, const uint8_t null_move)
{
   // if depth reached then return the score from quiesce
   if (!depth) return quiesce(alpha,beta);

   eo.nodes++;

   // check if search time up
   if ((eo.nodes&8191)==0 && millis()>eo.stop_time) eo.stop_search = true;

   pvl[ply] = ply;

   // if this isn't the root of the search tree (where we have
   // to pick a move and can't simply return 0) then check to
   // see if the position is a repeat if so, we can assume that
   // this line is a draw and return 0

   if (ply && reps()) return 0;

   // don't search too deep
   if (ply>=MAX_PLY-1) return eval();

   // if in check then keep searching
   const uint8_t in_check = king_attack(side);
   if (in_check)
   {
      depth++;
      eo.stop_search = false;
   }

   ASSERT(hk==get_hash());
   // false checkmate score
   //fen k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31 
   //fen 8/2r4k/p5p1/PP6/b2R1PPP/7r/3K4/6R1 b - - 0 46
   //fen rnb4N/p1p4Q/2k1p2p/1p1n4/1b4q1/8/PP3PPP/1RK4R b - - 5 23 ***
#if HASH_TABLE_ENABLE
   const uint32_t hi = hk%MAX_HASH_TABLE;
   if (ply)
   {
      if (ht[hi].key==hk && ht[hi].depth>=depth && (ht[hi].flag&FL_SIDE)==side)
      {
         int16_t s = ht[hi].score;
         if (s>MATE_VALUE) s -= ply; else if (s<-MATE_VALUE) s += ply;
         if (ht[hi].flag&HASH_EXACT) {stats.nhash++; return s;}
         else if ((ht[hi].flag&HASH_BETA) && s>=beta) {stats.nhash++; return beta;}
         else if ((ht[hi].flag&HASH_ALPHA) && s<=alpha) {stats.nhash++; return alpha;}
      }
   }
#endif

#if NULLMOVE_ENABLE
   if (null_move && !in_check && ply && depth>3)
   {
      int16_t nullmat = 0;
      uint8_t p = EMPTY;
      for (uint8_t i=0;i<64;i++)
      {
         if ((p=b[i]&0xf)==EMPTY) continue;
         if ((p&0x07)==PAWN) continue;
         if ((p&FL_SIDE)!=side) continue;
         nullmat += (white_scores[p]+black_scores[p]);
      }
      if (nullmat>1400)
      {
         donullmove();
         int16_t v = -absearch(-beta, -beta+1, depth - 1 - 2, false);
         undonullmove();
         if (eo.stop_search) return 0;
         if (v>=beta && abs(v)<MATE_VALUE)
         {
            return beta;
         }
      } 
   }
#endif

   // loop through the moves
   gen_all_moves(side);

#if HASH_TABLE_ENABLE
   // if there is a good move in the hash table
   // order it highly (but below the PV)
   if (ht[hi].key==hk)
   {
      const uint8_t origin = ht[hi].origin;
      const uint8_t target = ht[hi].target;
      if (origin|target)
      {
         for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
         {
            // don't replace the PV!
            if (ml[i].order==65535u) continue;
            if (origin==ml[i].m.origin && target==ml[i].m.target)
            {
               ml[i].order = 65000u;
               stats.hashorder++;
               break;
            }
         }
      }
   }
#endif

   int16_t old_alpha = alpha;
   int16_t best_score = -MAX_VALUE;
   move_t best_move = {0};
   uint8_t legal_move = 0;
   uint8_t move_ordering = true;

   for (uint16_t i=ply?nm[ply-1]:0;i<nm[ply];i++)
   {
      if (move_ordering) order_next_move(i);
      move_ordering = ml[i].order>0;
      if (!domove(ml[i].m)) continue;
      
      legal_move++;

#if LMR_ENABLE
      int16_t v = 0;
      if (depth<4 || legal_move==1 || in_check || ml[i].order>60000u)
      {
         v = -absearch(-beta, -alpha, depth-1, true);
      }
      else
      {
         const uint8_t reduce = ml[i].order==0?2:1;
         v = -absearch(-beta, -alpha, depth-1-reduce, false);
         if (v>alpha)
         {
            v = -absearch(-beta, -alpha, depth-1, true);
         }
      }
#else
      int16_t v = -absearch(-beta, -alpha, depth-1, true);
#endif
      undomove();
      if (eo.stop_search) return 0;
      if (v>best_score)
      {
         // update the PV
         ASSERT(ply+1<MAX_PLY);
         pv[ply][ply].m = ml[i].m;
         for (uint8_t j=ply+1;j<pvl[ply+1];j++) pv[ply][j] = pv[ply+1][j];
         pvl[ply] = pvl[ply+1];
         best_score = v;
         best_move = ml[i].m;
         if (v>alpha)
         {
            // since there was a cutoff increase the history or
            // "curiosity" heuristic (this is a low memory version
            // of the history heuristic which does a better job
            // than nothing but not as good as full history - the
            // difference in memory usage is significant!)
#if CURIOSITY_HEURISTIC
            if (depth>2 && ml[i].m.capture==EMPTY)
               curiosity[ml[i].m.target] += depth;
#elif HISTORY_HEURISTIC
            if (depth>2 && ml[i].m.capture==EMPTY)
            {
               const uint16_t h = history[ml[i].m.origin][ml[i].m.target]+depth;
               history[ml[i].m.origin][ml[i].m.target] = min(h,60000u);
            }
#endif
            if (v>=beta)
            {
               // record killers
               if (ml[i].m.capture==EMPTY)
               {
                  killers[2][ply] = killers[1][ply];
                  killers[1][ply] = killers[0][ply];
                  killers[0][ply] = ml[i].m;
               }
#if HASH_TABLE_ENABLE
               // store hash table entry
               ht[hi].key = hk;
               ht[hi].origin = best_move.origin;
               ht[hi].target = best_move.target;
               ht[hi].depth = depth;
               ht[hi].score = beta;
               ht[hi].flag = side|HASH_BETA;
#endif

               return beta;
            }
            alpha = v;
         }
      }
   }

#if HASH_TABLE_ENABLE
   ht[hi].key = hk;
   ht[hi].origin = best_move.origin;
   ht[hi].target = best_move.target;
   ht[hi].depth = depth;
   ht[hi].flag = side|HASH_EXACT;
   ht[hi].score = 0;
   // if no legal moves then checkmate or stalemate
   if (!legal_move)
   {
      if (in_check)
         return (ht[hi].score = -MAX_VALUE + ply);
      else
         return 0;
   }
   if (alpha==old_alpha)
   {
      ht[hi].flag = side|HASH_ALPHA;
      ht[hi].score = alpha;
   }
   else
   {
      ht[hi].score = best_score;
   }
#else
   if (!legal_move)
   {
      if (in_check)
         return -MAX_VALUE + ply;
      else
         return 0;
   }
#endif

   return alpha;
}
The difference is, if there is a checkmate then the score is stored against the current position (wasn't before). Also, since there is no "best move" in this case I've added a check in the hash move ordering to ignore null moves (well it will anyway).

I have another problem with LMR and null moves now. I'll post about that soon!

Many thanks, Ian

ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Re: Please help with Plankton

Post by ianm » Mon Jun 29, 2020 6:17 am

I’m having an issue when both LMR and null moves are enabled. And not a problem when enabled independently. This is the test position:



The best move should be b6c6. With null moves and LMR enabled, here’s what happens:
Ian's Low Memory Chess Program (plankton)
Version 8.7.0, 29/06/2020
Copyright 2020 Ian Mitchell
With late move reductions!
With history heuristic!
With evaluation cache!
With null moves!
With hash table!

"help" displays a list of commands.

plankton> fen k2r4/5ppp/1Q3n2/5q2/3r4/6P1/P3BP1P/6KR w - - 3 31
A B C D E F G H
8 k . . r . . . . 8
7 . . . . .*p*p*p 7
6 . Q . . . n . . 6
5 . . . . . q . . 5
4 . . . r . . . . 4
3 . . . . . . P . 3
2*P . . . B*P .*P 2
1 . . . . . . K R 1
A B C D E F G H

White to move.
plankton> st 120
Search time: 120000ms
plankton> go
ply mv time nodes score pv
1 0 0 50 -323 4 a2a4
2 0 0 578 -333 6 b6c6 a8b8 (a2a4)
3 0 0 3539 -333 8 a2a4 f6e4 b6c6
4 0 16 9944 -333 11 b6c6 a8b8 c6b6 b8a8
5 0 31 15537 -333 11 b6c6 a8b8 c6b6 b8a8
6 0 94 66820 -333 16 b6c6 a8b8 c6b6 b8a8
7 0 344 278658 -333 17 b6c6 a8b8 c6b6 b8a8
8 0 984 830085 -333 19 b6c6 a8b8 c6b6 b8a8
9 0 2703 2347844 -333 21 b6c6 a8b8 c6b6 b8a8
10 0 107406 99722493 -1436 27 b6b3 f6e4 b3a3 a8b8 a3b2 c8b7 b2b7
nreps: 5361
nhash: 1995558
hashorder: 1865904
hist: 52934
curo: 0

Computer's move: b6b3
plankton>

With null moves only:
ply mv time nodes score pv
1 0 0 50 -323 4 a2a4
2 0 0 578 -333 6 b6c6 a8b8 (a2a4)
3 0 16 3539 -333 8 a2a4 f6e4 b6c6
4 0 31 20495 -333 11 b6c6 a8b8 c6b6 b8a8
5 0 141 112181 -333 14 b6c6 a8b8 c6b6 b8a8
6 0 375 297970 0 17 b6c6 a8a7 c6c7 a7a8 c7c6
7 0 1141 962119 0 18 b6c6 a8a7 c6c7 a7a8 c7c6
8 0 3860 3341456 0 22 b6c6 a8a7 c6c7 a7a8 c7c6
9 0 17766 15806175 0 23 b6c6 a8a7 c6c7 a7a8 c7c6
10 0 71453 65215134 0 26 b6c6 a8a7 c6c7 a7a8 c7c6
With LMR only:
ply mv time nodes score pv
1 0 0 50 -323 4 a2a4
2 0 0 578 -333 6 b6c6 a8b8 (a2a4)
3 0 15 3539 -333 8 a2a4 f6e4 b6c6
4 0 15 9944 -333 11 b6c6 a8b8 c6b6 b8a8
5 0 31 11915 -333 11 b6c6 a8b8 c6b6 b8a8
6 0 78 45353 -333 14 b6c6 a8b8 c6b6 b8a8
7 0 156 108566 -333 15 b6c6 a8b8 c6b6 b8a8
8 0 375 270520 -333 17 b6c6 a8b8 c6b6 b8a8
9 0 1265 921966 -333 19 b6c6 a8b8 c6b6 b8a8
10 0 4969 3652818 -333 23 b6c6 a8b8 c6b6 b8a8
11 0 31906 24199130 -333 25 b6c6 a8b8 c6b6 b8a8
LMR seems to be working the best. Any ideas why combining them causes the completely wrong score and move at ply 10 when both are enabled?

Cheers, Ian

Ras
Posts: 1393
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Please help with Plankton

Post by Ras » Mon Jun 29, 2020 6:20 am

lucasart wrote:
Mon Jun 29, 2020 4:44 am
I coded a radical solution to this problem in Demolito:
I fixed that issue by having a "legal move was pruned" flag, initialised to false. After the node move loop, I both check whether the legal main move counter (pseudo legal move generator used) is still at 0 AND the flag is false. Only in that case, I return -MATE or 0 depending on whether it's in-check or not. If the main move counter is 0 but not the flag, no move has improved alpha, so I just return alpha, which results in a fail-low, which is a fail-high one level above, and that isn't harmful.
Rasmus Althoff
https://www.ct800.net

Sven
Posts: 3853
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Please help with Plankton

Post by Sven » Mon Jun 29, 2020 7:32 am

If pruning is disabled when being in check and returning a mate score is restricted to being in check as well then I do not see how this could ever go wrong.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
hgm
Posts: 24607
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Please help with Plankton

Post by hgm » Mon Jun 29, 2020 9:05 am

But setting a flag might be a lot cheaper than searching moves that deserve to be pruned (e.g. because of futility).

I don't think that false mate scores are really a problem here, as long as you only prune moves that would fail low. It doesn't matter much whether you fail low because of a mate score or poor evaluation. In a soft-fail scheme, at least. Of course with hard fail it is another matter; when you prune because you are confident the move will score below alpha, you must make sure that bestScore is increased to a reasonable estimate of what the move would give you. Or you might later retreave a completely unrealistic upper bound from the TT, which makes the node fail low compared to a now much lower alpha, while in fact the pruned move would have made it fail high in that case. E.g. when you futility prune because currentEval + victimValue < alpha - MARGIN you should set bestScore = currentEval + victimValue + MARGIN. This isn't really related to mate scores; if you don't do this things could go vary wrong in other situations as well.

The big problem is false stalemates. Which could make the node fail high when in fact it was arbitrarily poor (and not stalemate).

An additional problem in my tiny AI is that it really has no idea whether it is in check, and that figuring that out through a null move is rather expensive.

Post Reply