25,161
edits
Changes
Gk
,Created page with "'''Home * Engines * Gk''' '''Gk''', (GKJunior) a Chess Engine Communication Protocol compliant open source chess engine under..."
'''[[Main Page|Home]] * [[Engines]] * Gk'''
'''Gk''', (GKJunior)
a [[Chess Engine Communication Protocol]] compliant [[:Category:Open Source|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, while its private forerunner GKJunior already played at [[Internet Chess Club]] in the late 90s <ref>[https://www.stmintz.com/ccc/index.php?id=79887 ICC Green List - Nov 29] by [[Will Singleton]], [[CCC]], November 29, 1999</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=85701 ICC Green List - Jan 3] by [[Will Singleton]], [[CCC]], January 03, 2000</ref>.
=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.
<span id="SlidingAttacks"></span>
===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>:
<pre>
BitBoard diag_h1_attack[64][256];
BitBoard diag_a1_attack[64][256];
BitBoard diag_file_attack[64][256];
BitBoard diag_rank_attack[64][256];
</pre>
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>:
<pre>
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);
}
</pre>
<span id="BitScan"></span>
===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>:
<pre>
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
}
</pre>
==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=
* [https://www.stmintz.com/ccc/index.php?id=85839 Re: ICC Green List - Jan 3] by [[Tijs van Dam]], [[CCC]], January 04, 2000
* [https://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]
==Misc==
* [https://en.wikipedia.org/wiki/GK GK (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Garry_Kasparov Garry Kasparov from Wikipedia]
=References=
<references />
'''[[Engines|Up one level]]'''
[[Category:Open Source]]
[[Category:GPL]]
[[Category:WinBoard]]
[[Category:XBoard]]
'''Gk''', (GKJunior)
a [[Chess Engine Communication Protocol]] compliant [[:Category:Open Source|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, while its private forerunner GKJunior already played at [[Internet Chess Club]] in the late 90s <ref>[https://www.stmintz.com/ccc/index.php?id=79887 ICC Green List - Nov 29] by [[Will Singleton]], [[CCC]], November 29, 1999</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=85701 ICC Green List - Jan 3] by [[Will Singleton]], [[CCC]], January 03, 2000</ref>.
=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.
<span id="SlidingAttacks"></span>
===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>:
<pre>
BitBoard diag_h1_attack[64][256];
BitBoard diag_a1_attack[64][256];
BitBoard diag_file_attack[64][256];
BitBoard diag_rank_attack[64][256];
</pre>
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>:
<pre>
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);
}
</pre>
<span id="BitScan"></span>
===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>:
<pre>
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
}
</pre>
==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=
* [https://www.stmintz.com/ccc/index.php?id=85839 Re: ICC Green List - Jan 3] by [[Tijs van Dam]], [[CCC]], January 04, 2000
* [https://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]
==Misc==
* [https://en.wikipedia.org/wiki/GK GK (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Garry_Kasparov Garry Kasparov from Wikipedia]
=References=
<references />
'''[[Engines|Up one level]]'''
[[Category:Open Source]]
[[Category:GPL]]
[[Category:WinBoard]]
[[Category:XBoard]]
