KPK bitbase

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Maarten

KPK bitbase

Post by Maarten » Wed Jan 16, 2013 3:06 pm

Following Ed's post (http://www.talkchess.com/forum/viewtopic.php?t=46651) on KPK, I decided to replace my KPK evaluation function with a KPK bitbase. What a fun, a load of bugs introduced (using shr in stead of shl, missing parenthesis), found a bug in my IDD implementation (!?), searching for correct set of rules, but here I would like present the final sets of rules giving a 100% (?) working result.
Using Stockfish bitbase.cpp from stockfish-23-ja as a start, I've created a pascal unit generating the kpk bitbase at start up.
In total 196608 (2 * 24 * 64 * 64; // stm * wpsq * wksq * bksq = 196608) positions are classified in the bitbase as either won or draw. Only 24 squares for the white pawn (A2..D2..D7..A7) are considered by mirroring the position when the pawn is on E to H file.
The bitbase is generated in less than 55 ms at startup of the engine.

The basic algorithm of the kpk bitbase generation is:
1. Initial evaluation of all 196608 positions, using the set of rules below, resulting in following classification:
After static eval:
Total WIN: 42524
Total DRAW: 12240
Total INVALID: 30932
Total UNKNOWN: 110912
TIME: 8

Rules implemented:

Code: Select all

{Check for INVALID positions}
{1.1. Check if two pieces are on the same square or if king are adjacent
      or psq of RANK_1 or RANK_8}
  if (wksq=psq) or
     (wksq=bksq) or
     (bksq=psq) or
     &#40;psq<A2&#41; or &#40;psq>H7&#41; or
     &#40;distance64&#40;wksq,bksq&#41;<2&#41;
  then exit&#40;INVALID&#41;;
&#123;1.2. Check if black king can be captured by pawn&#125;
  if wtm then
    begin
      if (&#40;file_of&#40;psq&#41;>FILE_A&#41; and &#40;psq+DELTA_NW=bksq&#41;) or
         (&#40;file_of&#40;psq&#41;<FILE_H&#41; and &#40;psq+DELTA_NE=bksq&#41;)
      then exit&#40;INVALID&#41;;
    end;
&#123;Check for DRAW positions&#125;
  lsq&#58;=psq+DELTA_N; //stop square
&#123;2.1. Stalemate&#125;
  if &#40;not wtm&#41;
  then
    begin
      if &#40;bksq=A8&#41; and &#40;psq=C7&#41; and (&#40;wksq=A6&#41; or &#40;wksq=B6&#41;) then exit&#40;DRAW&#41;;
      if &#40;bksq=A8&#41; and &#40;psq=A7&#41; and (&#40;wksq=A6&#41; or &#40;wksq=B6&#41;) then exit&#40;DRAW&#41;;
      if &#40;bksq=A8&#41; and &#40;psq=B6&#41; and (&#40;wksq=C7&#41; or &#40;wksq=C8&#41;) then exit&#40;DRAW&#41;;
      if &#40;bksq=B8&#41; and &#40;psq=B7&#41; and &#40;wksq=B6&#41; then exit&#40;DRAW&#41;;
      if &#40;bksq=C8&#41; and &#40;psq=C7&#41; and &#40;wksq=C6&#41; then exit&#40;DRAW&#41;;
      if &#40;bksq=D8&#41; and &#40;psq=D7&#41; and &#40;wksq=D6&#41; then exit&#40;DRAW&#41;;
    end;
&#123;2.2. Black king can capture undefended pawn&#125;
  if &#40;not wtm&#41; and
     &#40;distance64&#40;bksq,psq&#41;=1&#41; and
     &#40;distance64&#40;wksq,psq&#41;>1&#41;
  then exit&#40;DRAW&#41;;
&#123;2.3. Black king in front of white pawn, black king not on 8th rank&#125;
  if &#40;bksq=lsq&#41; and
     &#40;psq<A7&#41;               //&#40;rank_of&#40;psq&#41;<RANK_7&#41;
  then exit&#40;DRAW&#41;;
&#123;2.4. White king in front of pawn and black has opposition, i.e white to move
      and pawn is not a rook pawn, black king not on 8th rank&#125;
  if wtm and
     &#40;wksq=lsq&#41; and
     &#40;file_of&#40;psq&#41;<>FILE_A&#41; and
     &#40;psq<A6&#41; and               //&#40;rank_of&#40;psq&#41;<=RANK_5&#41;
     &#40;bksq<A8&#41; and              //&#40;rank_of&#40;bksq&#41;<=RANK_7&#41;???
     &#40;bksq=wksq+DELTA_N+DELTA_N&#41;
  then exit&#40;DRAW&#41;;
&#123;2.5. Stalemate with rook pawn&#125;
  if &#40;bksq=A8&#41; and
     &#40;file_of&#40;psq&#41;=FILE_A&#41;
  then exit&#40;DRAW&#41;;
&#123;2.6. White pawn on A file and Black King on B7 or B8 is always draw&#125;
  if &#40;bksq in &#91;B7,B8&#93;) and
     &#40;file_of&#40;psq&#41;=FILE_A&#41;
  then exit&#40;DRAW&#41;;
&#123;2.7. White king trapped on A8&#125;
  if wtm and
     &#40;wksq=A8&#41; and
     &#40;psq=A7&#41; and
     (&#40;bksq=C8&#41; or &#40;bksq=C7&#41;)
  then exit&#40;DRAW&#41;;
&#123;2.8. White king trapped on the rook file&#125;
  if &#40;wksq>psq&#41; and
     &#40;file_of&#40;wksq&#41;=FILE_A&#41; and
     &#40;file_of&#40;psq&#41;=FILE_A&#41; and
     &#40;bksq=wksq+DELTA_E+DELTA_E&#41;
  then exit&#40;DRAW&#41;;
&#123;2.9. Black king as above, the White king diagonally behind the pawn,
       white side to move&#125;
  if wtm and
     &#40;bksq=lsq&#41; and
     (
      (&#40;file_of&#40;psq&#41;>FILE_A&#41; and &#40;wksq=psq+DELTA_SW&#41;) or
      (&#40;file_of&#40;psq&#41;<FILE_H&#41; and &#40;wksq=psq+DELTA_SE&#41;)
     )
  then exit&#40;DRAW&#41;;
&#123;2.10. Kings stand in the vertical opposition and
       the pawn is on the right/left side of the white king,
       white to move&#125;
  if wtm and
     &#40;wksq<A6&#41; and &#40;bksq=wksq+DELTA_N+DELTA_N&#41; and
     (
      (&#40;file_of&#40;wksq&#41;<FILE_H&#41; and &#40;psq=wksq+DELTA_E&#41;) or //pawn right to king
      (&#40;file_of&#40;wksq&#41;>FILE_A&#41; and &#40;psq=wksq+DELTA_W&#41;)    //pawn left of king
     )
  then exit&#40;DRAW&#41;;
&#123;2.11. In the above position the white pawn moves, giving check&#125;
  if not wtm and
     &#40;wksq<A6&#41; and &#40;bksq=wksq+DELTA_N+DELTA_N&#41; and
     (
      (&#40;file_of&#40;wksq&#41;<FILE_H&#41; and &#40;psq=wksq+DELTA_NE&#41;) or
      (&#40;file_of&#40;wksq&#41;>FILE_A&#41; and &#40;psq=wksq+DELTA_NW&#41;)
     )
  then exit&#40;DRAW&#41;;
&#123;2.12. The following code marks positions as drawn,    http&#58;//chessprogramming.wikispaces.com/KPK
       Black king not on 8th rank, 2 squares in front of pawn,
       White king behind pawn, pawn on 5th rank or lower, white to move&#125;
  if wtm and
     &#40;bksq<A8&#41; and //BK not on 8th rank
     &#40;psq<A6&#41; and  //WP on fifth rank or lower
     &#40;wksq<A5&#41; and //WK on fourth rank or lower
     (
      (&#40;file_of&#40;psq&#41;>FILE_A&#41; and &#40;bksq=lsq+DELTA_NW&#41;) or
      (&#40;bksq=lsq+DELTA_N&#41;) or
      (&#40;file_of&#40;psq&#41;<FILE_H&#41; and &#40;bksq=lsq+DELTA_NE&#41;)
     ) and
     (
      (&#40;file_of&#40;psq&#41;>FILE_A&#41; and &#40;wksq=psq+DELTA_SW&#41;) or
      (&#40;wksq=psq+DELTA_S&#41;) or
      (&#40;file_of&#40;psq&#41;<FILE_H&#41; and &#40;wksq=psq+DELTA_SE&#41;)
     )
  then exit&#40;DRAW&#41;;
&#123;2.13. Rook pawn, white king A6 black king on A8&#125;
  if &#40;wksq=A6&#41; and
     &#40;bksq=A8&#41; and
     &#40;psq<A6&#41; and
     &#40;file_of&#40;psq&#41;=FILE_A&#41;
  then exit&#40;DRAW&#41;;
&#123;If the white king is in front of the pawn and neither of the other two conditions is met,
&#40;b&#41; he has the opposition
&#40;c&#41; his king is on the sixth rank,
so black king is not on wksq+DELTA_NN or wtm; and
white king is not on 6th rank&#125;
&#123;2.14 a. white in front of pawn, black king on same file DELTA_N+DELTA_N+DELTA_N, black to move&#125;
  if not wtm and
     &#40;wksq=lsq&#41; and
     &#40;wksq<A6&#41; and
     &#40;bksq=wksq+DELTA_N+DELTA_N+DELTA_N&#41;
  then exit&#40;DRAW&#41;;
&#123;Check WIN positions&#125;
&#123;3.1. The position is an immediate win if it is white to move and
      the white pawn can be promoted without getting captured.&#125;
  if wtm and
     &#40;psq>H6&#41; and                //&#40;rank_of&#40;psq&#41;=RANK_7&#41;
     &#40;wksq<>lsq&#41; and
     (&#40;distance64&#40;bksq,lsq&#41;>1&#41; or &#40;distance64&#40;wksq,lsq&#41;=1&#41;)
   then exit&#40;WIN&#41;;
&#123;3.2. Immediate win if pawn is advanced and has free path&#125;
  if wtm and
     &#40;psq>bksq&#41; and
     &#40;rank_of&#40;psq&#41;>rank_of&#40;bksq&#41;) and
     (&#40;psq>wksq&#41; or &#40;file_of&#40;psq&#41;<>file_of&#40;wksq&#41;))
  then exit&#40;WIN&#41;;
&#123;3.3. Win if pawn is on 6th rank and White King is adjacent on 7th rank&#125;
  if &#40;rank_of&#40;psq&#41;=RANK_6&#41; and
     (
      (&#40;file_of&#40;psq&#41;>FILE_A&#41; and &#40;wksq=psq+DELTA_NW&#41;) or
      (&#40;file_of&#40;psq&#41;<FILE_H&#41; and &#40;wksq=psq+DELTA_NE&#41;)
     )
  then exit&#40;WIN&#41;;
&#123;3.4. White king in front of pawn and white has opposition, i.e black to move
      and pawn is not a rook pawn&#125;
  if not wtm and
     &#40;wksq=lsq&#41; and
     &#40;file_of&#40;psq&#41;<>FILE_A&#41; and
     &#40;psq<A6&#41; and               //&#40;rank_of&#40;psq&#41;<=RANK_5&#41;
//     &#40;bksq<A8&#41; and              //&#40;rank_of&#40;bksq&#41;<=RANK_7&#41;???
     &#40;bksq=wksq+DELTA_N+DELTA_N&#41;
  then exit&#40;WIN&#41;;
&#123;3.5. White king in front of pawn and white king on sixth rank,
       either side to move and pawn is not a rook pawn&#125;
  if &#40;wksq=lsq&#41; and
     &#40;rank_of&#40;wksq&#41;=RANK_6&#41; and
     &#40;file_of&#40;psq&#41;<>FILE_A&#41;
  then exit&#40;WIN&#41;;
&#123;3.6. White king on sixth rank, and has opposition, i.e. black to move,
       pawn is not a rook pawn and not on seventh rank&#125;
  if not wtm and
    &#40;rank_of&#40;wksq&#41;=RANK_6&#41; and
     &#40;bksq=wksq+DELTA_N+DELTA_N&#41; and
     &#40;psq<A7&#41; and
     &#40;file_of&#40;psq&#41;<>FILE_A&#41;
  then exit&#40;WIN&#41;;
&#123;3.7 White king on key sqare DELTA_N+&#40;DELTA_NW,DELTA_N,DELTA_NE&#41;,
      pawn on 2nd 3rd or 4th rank, not a rook pawn&#125;
  if &#40;file_of&#40;psq&#41;<>FILE_A&#41; and
     &#40;psq<A5&#41; and
     (
      &#40;wksq=lsq+DELTA_NW&#41; or
      &#40;wksq=lsq+DELTA_N&#41; or
      &#40;wksq=lsq+DELTA_NE&#41;
     )
  then exit&#40;WIN&#41;;
&#123;3.8. White king on key square &#40;DELTA_NW,DELTA_N,DELTA_NE&#41; or DELTA_N+&#40;DELTA_NW,DELTA_N,DELTA_NE&#41;,
      pawn on 5th rank, not a rook pawn&#125;
  if &#40;file_of&#40;psq&#41;<>FILE_A&#41; and
     &#40;rank_of&#40;psq&#41;=RANK_5&#41; and
     (
      &#40;wksq=psq+DELTA_NW&#41; or
      &#40;wksq=lsq&#41; or
      &#40;wksq=psq+DELTA_NE&#41; or
      &#40;wksq=lsq+DELTA_NW&#41; or
      &#40;wksq=lsq+DELTA_N&#41; or
      &#40;wksq=lsq+DELTA_NE&#41;
     )
  then exit&#40;WIN&#41;;
2. Until there are no more positions classified do classify unknown positions through retrograde analysis:

A. if white to move then generate all white king and pawn moves. If one move leads to a WIN position then the current position is a WIN; if all moves lead to a DRAW then the position is a DRAW; else the position remains UNKNOWN.

B. if black to move then generate all black king moves. If one move leads to a DRAW position then the current position is a DRAW; if all moves lead to a WIN then the position is a WIN; else the position remains UNKNOWN.
In total 18 iterations are required to classify all 196608 positions, as:
WIN: 111282
DRAW: 54394
INVALID: 30932
UNKNOWN: 0
TIME: 55

C. Map all positions to the bitbase, an array of 196608 bits grouped in 32bit unsigned integers (total 6144 integers), where 1 indicates a WIN and 0 is a DRAW/INVALID/UNKNOWN position.

Not all of above rules are required to obtain a correct result. Without rules 2.5, 2.6, 2.9-2.14, 3.2-3.8 the WIN positions are correctly identified, however some (1546) position remain classified as UNKNOWN, but in the final bitbase these are encoded as draw positions. Furthermore without these rules the retrograde analysis requires more iterations and thus more time, 88 ms.

In Stockfish a subset of above rules have been implemented, and a comment in the source states that "30 cycles needed" to classify all positions. When I implement the SF subset of rules then the 196608 positions are classified as:
Iter: 24
WIN: 111282
DRAW: 54004
INVALID: 30932
UNKNOWN: 390
TIME: 84
requiring 24 iterations in 60% more time: 84 ms. So all WIN positions are correctly classified, the final bitbase will thus correctly classify all positions.

The implementation of the KPK bitbase in my engine Troy (formerly known as Hector, http://chessprogramming.wikispaces.com/Hector), replacing the KPK evaluation function did hardly increase its playing strength, at least not beyond the level I can measure.

Unfortunately I could not find any source to confirm my statistics on the number WON/DRAW/INVALID positions, can anyone confirm my findings/statistics?

Regards, Maarten

jdart
Posts: 3803
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: KPK bitbase

Post by jdart » Wed Jan 16, 2013 3:28 pm

I just have an embedded bitmap (const array, built at compile time). It is about 48k in size. I generated it from the Nalimov tablebases.

--Jon

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: KPK bitbase

Post by mar » Wed Jan 16, 2013 3:43 pm

I have a bitmap too, just that currently it's only 24kb instead of 48 (using horizontal mirroring). The new probing code is completely branchless too.
I rewrote it and found bugs in my old implementation where the generation classified some rare positions wrong (like king on A8 with pawn on A7 and opponent king on C8 or C7).
I verified all the wins with search this time.
My generation is around 100ms on slow hardware using full and complex rules, I consider it too much and I bet whatever Stockfish does it's much faster with a simpler set of rules.
But nothing can beat precomputed table of course - sure you have longer executable and one extra (long) include source file but no extra code (except for probing).
Anyway KPK is only up to about 10 elo according to my quick tests, perhaps less if you already have unstoppable passer logic.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: KPK bitbase

Post by Don » Wed Jan 16, 2013 4:05 pm

Komodo has a bitbase I created 25 or 30 years ago and is fully debugged. It is simply linked in to the program as a constant array.

It is public domain to anyway who asks for it. You can use to check your implementation for correctness.

It is a 24,576 byte table. John Stanback helped me to debug it and as far as I know he still uses it too.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

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

Re: KPK bitbase

Post by Gerd Isenberg » Wed Jan 16, 2013 5:20 pm

Hi Maarten,

welcome to CCC and Thanks for sharing your beautiful Pascal code. I'll hope to write a small bio about you and a page about your new program Troy soon in cpw. Sorry, I can't help with your WDL statistics on KPK on the fly.

Cheers,
Gerd

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: KPK bitbase

Post by Don » Wed Jan 16, 2013 5:39 pm

mar wrote:I have a bitmap too, just that currently it's only 24kb instead of 48 (using horizontal mirroring). The new probing code is completely branchless too.
I rewrote it and found bugs in my old implementation where the generation classified some rare positions wrong (like king on A8 with pawn on A7 and opponent king on C8 or C7).
I verified all the wins with search this time.
My generation is around 100ms on slow hardware using full and complex rules, I consider it too much and I bet whatever Stockfish does it's much faster with a simpler set of rules.
But nothing can beat precomputed table of course - sure you have longer executable and one extra (long) include source file but no extra code (except for probing).
Anyway KPK is only up to about 10 elo according to my quick tests, perhaps less if you already have unstoppable passer logic.
The KPK is great to have in a chess program, but its ELO contribution is very close to zero. Maybe it is 1/4 ELO. It's very strange to me that it does not contribute more.

Today's programs are so strong that they play these endings perfectly, without any help. Still, you would think that it could still help at end nodes where these positions are beyond the computers horizon.

I think with end-game databases in general the situation is that most games are already won, lost, or drawn before the database can make any difference. Of the fraction that remain, only a fraction of those are likely to be misplayed.
The ELO contribution is thus based on just 1 out of many games and if there is any slowdown whatsoever in accessing a database, it probably more than cancels any benefit.

With THIS database it's actually a speedup for Komodo. It's a tiny bit-base and I combine it will a very simplistic evaluation to make sure the pawn moves up the board and the kings head in the right direction. In this way it will play the ending perfectly with a 1 ply search.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: KPK bitbase

Post by mar » Wed Jan 16, 2013 5:55 pm

Don wrote: The KPK is great to have in a chess program, but its ELO contribution is very close to zero. Maybe it is 1/4 ELO. It's very strange to me that it does not contribute more.
Which only shows how much I suck at testing. But I tested without unstoppable passer knowledge.
Don wrote: With THIS database it's actually a speedup for Komodo. It's a tiny bit-base and I combine it will a very simplistic evaluation to make sure the pawn moves up the board and the kings head in the right direction. In this way it will play the ending perfectly with a 1 ply search.
Yes I thought about that, makes perfect sense. Right now I apply it on top of everything else so I don't get any speedup at all, I will probably change it.
(raw nps was never my concern because I have lousy search anyway).
EG recognizers will be tried first, perhaps depending on np material so that I only try them in endgame.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: KPK bitbase

Post by Don » Wed Jan 16, 2013 6:05 pm

mar wrote:
Don wrote: The KPK is great to have in a chess program, but its ELO contribution is very close to zero. Maybe it is 1/4 ELO. It's very strange to me that it does not contribute more.
Which only shows how much I suck at testing. But I tested without unstoppable passer knowledge.
Don wrote: With THIS database it's actually a speedup for Komodo. It's a tiny bit-base and I combine it will a very simplistic evaluation to make sure the pawn moves up the board and the kings head in the right direction. In this way it will play the ending perfectly with a 1 ply search.
Yes I thought about that, makes perfect sense. Right now I apply it on top of everything else so I don't get any speedup at all, I will probably change it.
(raw nps was never my concern because I have lousy search anyway).
EG recognizers will be tried first, perhaps depending on np material so that I only try them in endgame.
The vast majority of endgame bitbases are lop-side, meaning that it's usually a win for one side or the other. This actually makes them a lot easier to compress. The hardest to compress would be where the wins/lose/draw would be equally distributed.

A project I tried years ago was to apply knowledge to the few endgames that really matter 95% of the time, such as KRPvsKR - to produce a bit-base or win/loss/draw type of database. It would be wonderful if this could be distilled into a decision tree, or some hybrid combination of data combined with knowledge. The idea would be to encapsulate a lot of knowledge into a very tiny space.

I suspect the "Kolmogorov complexity" of KRPvsKR is very small. If so, and if it's small enough, you have some pretty awesome.

For anyone who doesn't know what "Kolmogorov complexity" it is part of information theory and the wikipedia sums it up nicely:

http://en.wikipedia.org/wiki/Kolmogorov_complexity

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: KPK bitbase

Post by Don » Wed Jan 16, 2013 6:07 pm

P.S. Years ago someone produced a set of rules that perfectly determine if any KPvsK is a win or draw. A simple bit-base takes 24 bits, but I suspect these rules are much more compact, at least in compiled form.

Don wrote:
mar wrote:
Don wrote: The KPK is great to have in a chess program, but its ELO contribution is very close to zero. Maybe it is 1/4 ELO. It's very strange to me that it does not contribute more.
Which only shows how much I suck at testing. But I tested without unstoppable passer knowledge.
Don wrote: With THIS database it's actually a speedup for Komodo. It's a tiny bit-base and I combine it will a very simplistic evaluation to make sure the pawn moves up the board and the kings head in the right direction. In this way it will play the ending perfectly with a 1 ply search.
Yes I thought about that, makes perfect sense. Right now I apply it on top of everything else so I don't get any speedup at all, I will probably change it.
(raw nps was never my concern because I have lousy search anyway).
EG recognizers will be tried first, perhaps depending on np material so that I only try them in endgame.
The vast majority of endgame bitbases are lop-side, meaning that it's usually a win for one side or the other. This actually makes them a lot easier to compress. The hardest to compress would be where the wins/lose/draw would be equally distributed.

A project I tried years ago was to apply knowledge to the few endgames that really matter 95% of the time, such as KRPvsKR - to produce a bit-base or win/loss/draw type of database. It would be wonderful if this could be distilled into a decision tree, or some hybrid combination of data combined with knowledge. The idea would be to encapsulate a lot of knowledge into a very tiny space.

I suspect the "Kolmogorov complexity" of KRPvsKR is very small. If so, and if it's small enough, you have some pretty awesome.

For anyone who doesn't know what "Kolmogorov complexity" it is part of information theory and the wikipedia sums it up nicely:

http://en.wikipedia.org/wiki/Kolmogorov_complexity

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: KPK bitbase

Post by mar » Wed Jan 16, 2013 6:17 pm

Don wrote:P.S. Years ago someone produced a set of rules that perfectly determine if any KPvsK is a win or draw. A simple bit-base takes 24 bits, but I suspect these rules are much more compact, at least in compiled form.
Yes, having set of rules instead of storing giga or terabytes of data would be awesome. Even if these wouldn't be perfect and only hold in say 95% cases.
Knowledge would be best compression.
I don't know how complicated these rules were though.

Post Reply