Home * Engines * Gk
Gk

Gk, (GKJunior)
a Chess Engine Communication Protocol compliant open source chess engine under the GNU General Public License, written by Tijs van Dam in C++, first released in May 2003 [1], while its private forerunner GKJunior already played at Internet Chess Club in the late 90s [2] [3].

Description

Bitboard Infrastructure

As bitboard engine, Gk generates moves with the typical serialization loops on move target sets, and uses Brian Kernighan's population count to determine the cardinality of sets.

Rotated Indices

Gk applies rotated indices with 1/2 MiB pre-initialized lookup tables to determine sliding piece attacks, indexed by square and 8-bit line occupancy [4]:
BitBoard diag_h1_attack[64][256];
BitBoard diag_a1_attack[64][256];
BitBoard diag_file_attack[64][256];
BitBoard diag_rank_attack[64][256];
Rather than keeping the rotated occupancies inside rotated bitboards, a deconcentrated data structure of unsigned integer arrays is used keeping 8-bit occupancies for each enumerated line of either 8 ranks / files or 15 diagonals / anti-diagonals, incrementally updated during make and unmake move [5]:
unsigned diag_h1_occ[15];
unsigned diag_a1_occ[15];
unsigned diag_file_occ[8];
unsigned diag_rank_occ[8];
 
INLINE BitBoard AttacksDiagA1(int square) {
  return diag_a1_attack[square][diag_a1_occ[DiagA1DiagNum(square)]];
}
 
INLINE int DiagA1DiagNum(int square) {
  return 7-Rank(square)+File(square);
}

BitScan

BitScan is either implemented in 32-bit x86 Assembly, or with 16-bit indexed, 64K int lookup tables of 1/2 MiB and conditions for other architectures. FirstOne scans reverse, LastOne forward [6]:
int first_ones[65536];
int last_ones[65536];
 
INLINE int FirstOne(BitBoard b) {
#ifdef USE_ASM
ASM {
   bsr     edx, dword ptr b+4 // is there a 1 in the high word?
   mov     eax, 32
   jnz     l1                 // return FirstOne(hiword(b))+32
   bsr     edx, dword ptr b   // else return FirstOne(loword(b))
   xor     eax, eax
l1:add     eax, edx
  }
#else
  register U16 *x=(U16 *)(&b);
  if(x[3]) return first_ones[x[3]]+48;
  if(x[2]) return first_ones[x[2]]+32;
  if(x[1]) return first_ones[x[1]]+16;
  return first_ones[x[0]];
#endif
}
 
INLINE int LastOne(BitBoard b) {
#ifdef USE_ASM
__asm {
   bsf    eax, dword ptr b   // is there a 1 in the low word
   jnz    l1                 // then return LastOne(loword(b))
   bsf    eax, dword ptr b+4 // else return LastOne(hiword(b))+32
   add    eax,32
l1:
   }
#else
  register U16 *x=(U16 *)(&b);
  if(x[0]) return last_ones[x[0]];
  if(x[1]) return last_ones[x[1]]+16;
  if(x[2]) return last_ones[x[2]]+32;
  return last_ones[x[3]]+48;
#endif
}

Search

The search is PVS alpha-beta with transposition table inside an iterative deepening framework without aspiration, maintaining the principal variations inside a "quadratic" PV-table. Selectivity is realized by null move Pruning, check extensions, and delta pruning in quiescence search. History heuristic, IID, MVV-LVA in conjunction with a SEE swap routine improve move ordering and delta pruning.

Evaluation

Gk's evaluation is rudimentary and restricts positional scores in the range of plus-minus one pawn value - at least it is very lazy if the material balance is outside the alpha-beta window by that margin. It considers center control, mobility, development and too early queen, and some pawn shield and castling right related king safety stuff. The cached pawn structure evaluation takes passers, doubled and isolated pawns, and pawns protecting each other into account.

See also


Forum Posts


External Links

Chess Engine

Misc


References

  1. ^ Gk from WBEC Ridderkerk
  2. ^ ICC Green List - Nov 29 by Will Singleton, CCC, November 29, 1999
  3. ^ ICC Green List - Jan 3 by Will Singleton, CCC, January 03, 2000
  4. ^ Tijs van Dam - Software, gk-0.90.tar.gz / global.cpp
  5. ^ Tijs van Dam - Software, gk-0.90.tar.gz / position.h
  6. ^ Tijs van Dam - Software, gk-0.90.tar.gz / bitboard.h

What links here?


Up one level