Gk

Edit 0 6 …
Older Version Newer Version

GerdIsenberg GerdIsenberg Oct 9, 2017 

**[[Home]] * [[Engines]] * Gk**
|| <span style="font-family: 'Comic Sans MS', cursive;
font-size: 1000%;">Gk</span> ||~ || **Gk**, (GKJunior)
a [[Chess Engine Communication Protocol]] compliant [[Open Source Engines|open source chess engine]] under the [[Free Software Foundation#GPL|GNU General Public License]], written by [[Tijs van Dam]] in [[Cpp|C++]], first released in May 2003 <ref>[[http://wbec-ridderkerk.nl/html/details1/Gk.html|Gk]] from [[WBEC|WBEC Ridderkerk]]</ref>, while its private forerunner GKJunior already played at [[Internet Chess Club]] in the late 90s <ref>[[http://www.stmintz.com/ccc/index.php?id=79887|ICC Green List - Nov 29]] by [[Will Singleton]], [[CCC]], November 29, 1999</ref> <ref>[[http://www.stmintz.com/ccc/index.php?id=85701|ICC Green List - Jan 3]] by [[Will Singleton]], [[CCC]], January 03, 2000</ref>. ||
[[toc]]
=Description=
==Bitboard Infrastructure==
As [[Bitboards|bitboard]] engine, Gk [[Move Generation|generates moves]] with the typical [[Bitboard Serialization|serialization loops]] on move target sets, and uses [[Population Count#BrianKernighansway|Brian Kernighan's population count]] to determine the cardinality of sets.
[[#SlidingAttacks]]
===Rotated Indices===
Gk applies [[Rotated Indices|rotated indices]] with 1/2 MiB pre-initialized lookup tables to determine [[Sliding Piece Attacks|sliding piece attacks]], indexed by square and [[Occupancy of any Line|8-bit line occupancy]] <ref>[[http://tijsvd.home.xs4all.nl/old_software/|Tijs van Dam - Software]], gk-0.90.tar.gz / global.cpp</ref>: 
[[code format="cpp"]]
BitBoard diag_h1_attack[64][256];
BitBoard diag_a1_attack[64][256];
BitBoard diag_file_attack[64][256];
BitBoard diag_rank_attack[64][256];
[[code]]
Rather than keeping the [[Flipping Mirroring and Rotating|rotated]] [[Occupancy|occupancies]] inside [[Rotated Bitboards|rotated bitboards]], a deconcentrated data structure of unsigned integer arrays is used keeping 8-bit occupancies for each enumerated line of either 8 [[Ranks|ranks]] / [[Files|files]] or 15 [[Diagonals|diagonals]] / [[Anti-Diagonals|anti-diagonals]], [[Incremental Updates|incrementally updated]] during [[Make Move|make]] and [[Unmake Move|unmake move]] <ref>[[http://tijsvd.home.xs4all.nl/old_software/|Tijs van Dam - Software]], gk-0.90.tar.gz / position.h</ref>: 
[[code format="cpp"]]
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);
}
[[code]]
[[#BitScan]]
===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 <ref>[[http://tijsvd.home.xs4all.nl/old_software/|Tijs van Dam - Software]], gk-0.90.tar.gz / bitboard.h</ref>:
[[code format="cpp"]]
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
}
[[code]]

==Search==
The [[Search|search]] is [[Principal Variation Search|PVS]] [[Alpha-Beta|alpha-beta]] with [[Transposition Table|transposition table]] inside an [[Iterative Deepening|iterative deepening]] framework without [[Aspiration Windows|aspiration]], maintaining the [[Principal variation|principal variations]] inside a "quadratic" [[Triangular PV-Table|PV-table]]. [[Selectivity|Selectivity]] is realized by [[Null Move Pruning|null move Pruning]], [[Check Extensions|check extensions]], and [[Delta Pruning|delta pruning]] in [[Quiescence Search|quiescence search]]. [[History Heuristic|History heuristic]], [[Internal Iterative Deepening|IID]], [[MVV-LVA]] in conjunction with a [[SEE - The Swap Algorithm|SEE swap routine]] improve [[Move Ordering|move ordering]] and delta pruning.

==Evaluation==
Gk's [[Evaluation|evaluation]] is rudimentary and restricts positional [[Score|scores]] in the range of plus-minus one [[Pawn|pawn]] [[Point Value|value]] - at least it is very [[Lazy Evaluation|lazy]] if the [[Material#Balance|material balance]] is outside the [[Window|alpha-beta window]] by that margin. It considers [[Center Control|center control]], [[Mobility|mobility]], [[Development|development]] and  [[Evaluation of pieces#Queen|too early queen]], and some [[King Safety#PawnShield|pawn shield]] and [[Castling rights|castling right]] related [[King Safety|king safety]] stuff. The [[Pawn Hash Table|cached]] [[Pawn Structure|pawn structure]] evaluation takes [[Passed Pawn|passers]], [[Doubled Pawn|doubled]] and [[Isolated Pawn|isolated pawns]], and [[Defended Pawns (Bitboards)|pawns protecting each other]] into account.

=See also=
* [[Fortress (Engine)|Fortress]]
* [[GK 2100]]
* [[PK]]

=Forum Posts=
* [[http://www.stmintz.com/ccc/index.php?id=85839|Re: ICC Green List - Jan 3]] by [[Tijs van Dam]], [[CCC]], January 04, 2000
* [[http://www.stmintz.com/ccc/index.php?id=93810|Re: Can we use hash table at root?]] by [[Tijs van Dam]], [[CCC]], February 01, 2000 ยป [[Transposition Table]], [[Root]]
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=45776#p173920|Re: More programs added to my tournament]] by Sergio Martinez, [[Computer Chess Forums|Winboard Forum]], December 27, 2003

=External Links=
==Chess Engine==
* [[http://tijsvd.home.xs4all.nl/old_software/|Tijs van Dam - Software]]
* [[http://wbec-ridderkerk.nl/html/details1/Gk.html|Gk]] from [[WBEC|WBEC Ridderkerk]]
==Misc==
* [[http://en.wikipedia.org/wiki/GK|GK (disambiguation) from Wikipedia]]
* [[http://en.wikipedia.org/wiki/Garry_Kasparov|Garry Kasparov from Wikipedia]]

=References= 
<references />
=What links here?= 
[[include page="Gk" component="backlinks" limit="20" ]]
**[[Engines|Up one level]]**