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, while its private forerunner GKJunior already played at Internet Chess Club in the late 90s [1] [2].
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 [3]:
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 [4]:
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 [5]:
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
- Re: ICC Green List - Jan 3 by Tijs van Dam, CCC, January 04, 2000
- Re: Can we use hash table at root? by Tijs van Dam, CCC, February 01, 2000 » Transposition Table, Root
- Re: More programs added to my tournament by Sergio Martinez, Winboard Forum, December 27, 2003
External Links
Chess Engine
Misc
References
- ↑ ICC Green List - Nov 29 by Will Singleton, CCC, November 29, 1999
- ↑ ICC Green List - Jan 3 by Will Singleton, CCC, January 03, 2000
- ↑ Tijs van Dam - Software, gk-0.90.tar.gz / global.cpp
- ↑ Tijs van Dam - Software, gk-0.90.tar.gz / position.h
- ↑ Tijs van Dam - Software, gk-0.90.tar.gz / bitboard.h
