ChessKISS and memory

This engine is a memory hunter, trying to reduce the memory I've created two new entries in the .ini which are the maximum amount of memory that the transposition tables can use expressed in megabytes:


[cache]
EvaluationHashSize=16
TranspositionTableSize=256

(also it is needed for the winboard protocol, but I haven't implemented yet)

Before I was using a simple TDictionary<int64, TInfo> (key/value)

Now I use an intermediate class called TCache which internally uses a TDictionary AND a TLinkedList, but why?

Because we must delete entries once we have reach the maximum amount of memory allowed, how we do it?, just adding the key to the LinkedList and deleting always the first item (first item is always the oldest one)

procedure TCache<TKey, TValue>.Add(aKey: TKey; aValue: TValue);
begin
  FItems.Add(aKey, aValue);
  AddPointer(aKey, aValue);
end;

procedure TCache<Key, Value>.AddPointer(const aKey: Key; const aValue: Value);
begin
  FPointers.Enqueue(aKey);
  Inc(FCurrentSize, Length(aValue));

  case FType of
    ctPerEntries:
      begin
        if Count > FMaxSize then
          DeleteOldest;
      end;

    ctPerSize:
      begin
        while FCurrentSize > FMaxSize do
          DeleteOldest;
      end;
  end;
end;

function TCache<Key, Value>.Length(const aValue: Value): integer;
var
  v: TValue;

begin
  v := TValue.From<Value>(aValue);
  if v.Kind in [tkLString, tkWString, tkUString] then
    Exit(System.Length(v.AsString) * SizeOf(char))
  else
    Exit(v.DataSize);
end;
procedure TCache<TKey, TValue>.DeleteOldest;
begin
  Remove(FPointers[0]);
end;

procedure TCache<TKey, TValue>.Remove(aKey: TKey);
var
  i: integer;

begin
  FItems.Remove(aKey);
  FPointers.Delete(aKey);
end;

Why a LinkedList, because is the best collection once you want to remove the initital item, is just a matter of freeze the node and update the head node, for example with list or arrays the WHOLE list has to be moved to the left.

LinkedList:

procedure TLinkedList<T>.Delete(aItem: T);
var
  current, prior, next: TNodeList;

begin
  current := InternalFind(aItem);
  if current = nil then
    raise Exception.Create('Item not found');

  prior := current.Prior;
  next := current.Next;

  TryFreeObject(current.Item);

  //Update head
  if FHead = current then
  begin
    if next <> nil then
      FHead := next
    else
      FHead := nil;
  end;

  //Update tail
  if FTail = current then
  begin
    if prior <> nil then
      FTail := prior
    else
      FTail := nil;
  end;

  //Update sides
  if prior <> nil then
    prior.Next := next;

  if next <> nil then
    next.Prior := prior;

  current.Free;
  Dec(FCount);
end;

A fast delete..., now a typical array approach:

procedure TArrayEx<T>.Delete(aIndex: integer);
var
  i: integer;

begin
  if aIndex < FCount - 1 then
  begin
    for i := aIndex to FCount - 1 do
      FArray[i] := FArray[i + 1];
    FArray[FCount] := Default(T);
  end;

  Dec(FCount);
end;
The more elements the worst...
So now we do:
constructor TTranspositionTable.Create;
begin
  //In MB!
  FData := TCache<int64, TInfo>.Create(ctPerSize, 
TSettings.Instance.Transposition TableSize * 1024 * 1024);
FHits := 0;
  FMisses := 0;
end;
And voila! (of course the own LinkedList also consumes memory...)
But the engine still consumes too much memory, I've to find out why and where...

Out of memory, the fallen and the rise of a programmer

As an average developer would do, I started creating classes and interfaces like hell for the chess project, as long as my search depth levels kept low, there was no problem at all, but as some optimizations and bugs fixing were deployed the memory was increasing rapidly, now in some positions the program can easily go to depth15, 20, etc (it depends in the amount of time and position, of course), so I had to do something that dramatically reduce the amount of memory and the code changes at a minimal level:

Before (simplistic version)

TMove = class
public
 function ToString: string; override;

 property FromIdx: integer read FFrom;
 property ToIdx: integer read FTo;
 property PieceType: TPieceType read FPieceType;
 property Action: TAction read FAction;
end;

Currently

TMove = integer;
 
  TMoveHelper = class
  { TODO : promotion type }
  {
  upper 16 bits  |lower 16 bits
  upper 8|lower 8|upper 6|middle 6|lower 4
  from   |to     |piece  |action  |promotion
  }
  public
    class function Pack(aPiece: TPieceType; aFrom, aTo: integer; aAction: TAction; aPromotion: TPromotion = pQueen): TMove; inline;
    class procedure Unpack(aMove: TMove; out aPiece: TPieceType; out aFrom, aTo: integer; out aAction: TAction);
    class function GetPiece(aMove: TMove): TPieceType; inline;
    class function GetFrom(aMove: TMove): integer; inline;
    class function GetTo(aMove: TMove): integer; inline;
    class function GetAction(aMove: TMove): TAction; inline;
    class function ToString(aMove: TMove): string; reintroduce;
  end;
The trick is packing all the class information into a single 32 bits integer and create a helper class that easily pack and unpack all the necessary information.
board[move.FromIdx] := move.PieceType ;
becomes 
board[TMoveHelper.GetFrom(move)] := TMoveHelper.GetPiece(move);
With the online options the code generated is quite fast, for the changes, a few replaces was enough.
Albeit the code now is a bit "obscure"

{ TMoveHelper }

class function TMoveHelper.GetAction(aMove: TMove): TAction;
begin
  Exit(TAction(aMove and $3f0 shr 4));
end;

class function TMoveHelper.GetFrom(aMove: TMove): integer;
begin
  Exit(aMove shr 24);
end;

class function TMoveHelper.GetPiece(aMove: TMove): TPieceType;
begin
  Exit(TPieceType(aMove and $ffff shr 10))
end;

class function TMoveHelper.GetTo(aMove: TMove): integer;
begin
  Exit(aMove and $ff0000 shr 16);
end;

class function TMoveHelper.Pack(aPiece: TPieceType; aFrom, aTo: integer; aAction: TAction; aPromotion: TPromotion = pQueen): TMove;
begin
  Exit((aFrom shl 24) + (aTo shl 16) + (integer(aPiece) shl 10) + (integer(aAction) shl 4) + integer(aPromotion));
end;

class function TMoveHelper.ToString(aMove: TMove): string;
var
  piece: TPieceType;
  action: TAction;
  FromIdx, ToIdx: integer;

begin
  Unpack(aMove, piece, FromIdx, ToIdx, action);
  Exit('xxx');  //+
end;

class procedure TMoveHelper.Unpack(aMove: TMove; out aPiece: TPieceType; out aFrom, aTo: integer; out aAction: TAction);
begin
  aPiece := TPieceType(aMove and $ffff shr 10);
  aAction := TAction(aMove and f0 shr 4);
  aFrom := aMove shr 24;
  aTo := aMove and $ff0000 shr 16;
  //+ aPromote := aMove and $f;
end;
Have fun