Friday, November 12, 2010

ChessKISS code optimizations

I've lately been doing a lot of optimizations in the code that I want to share with you (although the main speed up always comes from reducing the tree size...)

class TKillers

Before:

FHits: array[0..63, 0..63, 0..63] of integer; //Depth,From,To


After:


FHits: array[0..63, 0..$ffff] of integer; //Depth,From&To

Since the index is already pack as 16 bits now we use that directly as index, so a new function was created in TMoveHelper:

class function TMoveHelper.GetIndex(aMove: TMove): integer;
begin
  //This function RETURNS 16 bits [0..65535] not 6 bits [0..63] as index
  //Max will be $4040 [63][63]
  Exit(aMove shr 16);
end;
The same rule applies to THistoric:
type
  THistoric = class
  private
    FHistory: array[0..$ffff] of integer; //$4040
  public
    constructor Create;
    procedure Add(aMove: TMove; aDepth: integer);
    function Get(aMove: TMove): integer; inline;
    procedure Clear;
  end;

procedure THistoric.Add(aMove: TMove; aDepth: integer);
begin
  if (aMove <> 0) and (not TMoveHelper.IsCaptureOrPromote(aMove)) then
    Inc(FHistory[TMoveHelper.GetIndex(aMove)], aDepth);
end;

function THistoric.Get(aMove: TMove): integer;
begin
  if aMove = 0 then
    Exit(0)
  else
    Exit(FHistory[TMoveHelper.GetIndex(aMove)]);
end;
In order to speed up the moves creation we have a few tables that helps checking 
when a move is outside the board without "if's". 
The function is TBoardchess.OutOfBoard(aIndex, aDir: TDir): boolean;
Before it was using a map of integers, now I've change it to booleans:
Map: array[0..143] of boolean =
  (
    True, True, True,  True,  True,  True,  True,  True,  True,  True,  True, True, //0
    True, True, True,  True,  True,  True,  True,  True,  True,  True,  True, True, //12
    True, True, False, False, False, False, False, False, False, False, True, True, //24
    True, True, False, False, False, False, False, False, False, False, True, True, //36
    True, True, False, False, False, False, False, False, False, False, True, True, //48
    True, True, False, False, False, False, False, False, False, False, True, True, //64
    True, True, False, False, False, False, False, False, False, False, True, True, //72
    True, True, False, False, False, False, False, False, False, False, True, True, //84
    True, True, False, False, False, False, False, False, False, False, True, True, //96
    True, True, False, False, False, False, False, False, False, False, True, True, //108
    True, True, True,  True,  True,  True,  True,  True,  True,  True,  True, True, //120
    True, True, True,  True,  True,  True,  True,  True,  True,  True,  True, True  //132
  );

Before outside was 0 and inside was 1, so the output assembler is now:
function OutOfBoard(aIndex: integer; aDir: TDir): boolean; inline; 
begin
  Exit(Map[MapLookup[aIndex] + Offsets12[aDir]]); 
end;

ASM:
004A68D0 8B049538054B00   mov eax,[edx*4+$4b0538]
004A68D7 0FB6D1           movzx edx,cl
004A68DA 03049538064B00   add eax,[edx*4+$4b0638]
004A68E1 0FB680A8044B00   movzx eax,[eax+$004b04a8]
Before it was:
Unit34.pas.593: Exit(Map[MapLookup[aIndex] + Offsets12[aDir]] = 0);
004A68D0 8B0495E8064B00   mov eax,[edx*4+$4b06e8]
004A68D7 0FB6D1           movzx edx,cl
004A68DA 030495E8074B00   add eax,[edx*4+$4b07e8]
004A68E1 833C85A8044B0000 cmp dword ptr [eax*4+$4b04a8],$00
004A68E9 0F94C0           setz al
So a line less and no branching millions times always count... ( I hope :-) )
Revisiting the move generation I could remove some extra lines in 
all move/capture functions:
procedure TChessboard.GenerateKingMoves(aPiece: TPiece; aIndex: integer; var aMoves: TMoveSet);
var
  i, dst, src: integer;

begin
  src := aPiece.Index;
  i := 7;
  while i >= 0 do
  begin
    if not OutOfBoard(src, TDir(i)) then
    begin
      dst := Offsets8Cols[TDir(i)] + src;
      if (GetPiece(dst) = nil) and ((aIndex = -1) or (dst = aIndex)) then
        aMoves.Add(TMoveHelper.Pack(ptKing, src, dst, actMove));
    end;

    Dec(i);
  end;
end;

No comments:

Post a Comment