Changes

Jump to: navigation, search

RedQueen

11,422 bytes added, 22:43, 4 December 2018
Created page with "'''Home * Engines * RedQueen''' border|right|thumb| The Red Queen lecturing [[Alice <ref>Illustration by :Catego..."
'''[[Main Page|Home]] * [[Engines]] * RedQueen'''

[[FILE:Tenniel red queen with alice.jpg|border|right|thumb| The Red Queen lecturing [[Alice]] <ref>Illustration by [[:Category:John Tenniel|John Tenniel]] of the [[RedQueen|Red Queen]] lecturing [[Alice]] for [[:Category:Lewis Carroll|Lewis Carroll's]] "[https://en.wikipedia.org/wiki/Through_the_Looking-Glass Through The Looking Glass]", 1871, [https://en.wikipedia.org/wiki/Red_Queen_%28Through_the_Looking-Glass%29 Red Queen (Through the Looking-Glass) - Wikipedia]</ref> ]]

'''RedQueen''',<br/>
an [[UCI]] compliant [[:Category:Open Source|open source chess engine]] under the [[Free Software Foundation#GPL|GNU General Public License]], written in [[Cpp|C++]] by [[Ben-Hur Carlos Vieira Langoni Junior]]. Using minimal library dependencies as possible, it could easily ported to various [[Software|operating systems]] such as [[Windows]], [[Linux]], [[Mac OS]], and [[Android]]. The name RedQueen was inspired by the [https://en.wikipedia.org/wiki/Red_Queen_%28Through_the_Looking-Glass%29 Red Queen character] in [[:Category:Lewis Carroll|Lewis Carroll's]] [https://en.wikipedia.org/wiki/Through_the_Looking-Glass Through the Looking-Glass] novel <ref>[http://redqueenchess.sourceforge.net/ RedQueen | Chess Engine]</ref> .

=Description=
==Bitboards==
RedQueen is a [[Bitboards|bitboard]] engine and uses [[Pradu Kannan|Pradu Kannan's]] [[Magic Bitboards|magic bitboards]] <ref>[http://sourceforge.net/projects/redqueenchess/ redqueen-1.1.2-windows.zip download], magicmoves.h, magicmoves.cpp</ref> to determine [[Sliding Piece Attacks|sliding piece attacks]]. [[BitScan|BitScans]] are either implemented in [[Assembly#InlineAssembly|inline assembly]] for [[x86-64]] [[BitScan#bsfbsr|processor instructions]], or with [[BitScan#DeBruijnMultiplation|De Bruijn multiplication]] and [[BitScan#DoubleConversionBSR|double conversion]] for forward and reverse scans respectively <span id="BitScan"></span> <ref>[http://sourceforge.net/projects/redqueenchess/ redqueen-1.1.2-windows.zip download], bitboard.h</ref>:
<pre>
const uint64_t debruijn64 = 0x07EDD5E59A4E28C2ULL;
const uint32_t index64[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5
};

inline int bitScanForward(int* const index, const uint64_t mask) {
#if defined(__LP64__)
uint64_t ret;
asm ("bsfq %[mask], %[ret]" : [ret] "=r" (ret) :[mask] "mr" (mask));
*index = int(ret);
#else
*index = int(index64[((mask & -mask) * debruijn64) >> 58]);
#endif
return mask?1:0;
}
inline int bitScanReverse(int* const index, const uint64_t mask) {
#if defined(__LP64__)
uint64_t ret;
asm ("bsrq %[mask], %[ret]" :[ret] "=r" (ret) :[mask] "mr" (mask));
*index = (unsigned int)ret;
#else
union {
double d;
struct {
unsigned int mantissal : 32;
unsigned int mantissah : 20;
unsigned int exponent : 11;
unsigned int sign : 1;
};
} ud;
ud.d = (double)(mask & ~(mask >> 32));
*index = ud.exponent - 1023;
#endif
return mask?1:0;
}
</pre>

Similar holds for [[Population Count|population count]] with [[SSE4]] instruction if available versus [[Population Count#SWARPopcount|SWAR-popcount]], also using an optimized version for populations below 16, borrowed from [[Stockfish]].

==Search==
RedQueen applies a [[Parallel Search|parallel search]] considering the [[Young Brothers Wait Concept]] using a pool of [[Thread|threads]] where a master spawns idle threads. The [[Search|search]] is [[Principal Variation Search|PVS]] [[Alpha-Beta|alpha-beta]] with the [[Shared Hash Table|shared]] [[Transposition Table|transposition table]] inside an [[Iterative Deepening|iterative deepening]] framework with [[Aspiration Windows|aspiration windows]]. [[Selectivity]] is applied by [[Check Extensions|check]] and [[PV Extensions|PV extensions]], [[Null Move Pruning#AdaptiveNullMovePruning|adaptive nullmove pruning]], [[Razoring|razoring]], [[Futility Pruning|futility pruning]], [[Reductions|reductions]] at [[Node Types#PV|PV-]] and more aggressively at none PV-nodes. The [[SEE - The Swap Algorithm|SEE swap algorithm]] is used to prune bad [[Captures|captures]] in [[Quiescence Search|quiescence search]], as well in [[Move Ordering|move ordering]], which is further improved by the obligatory [[Killer Heuristic|killer-]] and [[History Heuristic|history heuristics]].

==Evaluation==
The [[Evaluation|evaluation]] might be [[Lazy Evaluation|lazy]] and otherwise considers [[Tactics|tactical]] and positional features as well as [[Material|material imbalances]] along with a [[Pawn Hash Table|pawn structure cache]] and a [[Tapered Eval|tapered eval]] interpolating [[Middlegame|middlegame]] and [[Endgame|endgame]] [[Score|scores]] with [[Passed Pawn|passed pawn]] and [[King Safety|king safety]] and most dominant terms beside material.

=Tournament Play=
Over the board, RedQueen played the [[ICT 2010]], [[DOCCC 2010]], [[ICT 2011]], [[ICT 2012]], [[PT 52]], [[PT 53]] and [[PT 54]] [[CSVN]] tournaments in [https://en.wikipedia.org/wiki/Leiden Leiden], online the [[ACCA 2010]], [[ACCA 2011]], [[CCT13]], [[CCT14]], and the [[WCRCC 2011]].

=Selected Games=
[[ACCA 2011]], round 2, [[RedQueen]] - [[Crafty]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41067 2011 6ht annual ACCA games (RedQueen's games)] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], November 13, 2011</ref>
<pre>
[Event "ACCA 2011"]
[Site "HGM's server"]
[Date "2011.11.12"]
[Round "2"]
[White "RedQueen"]
[Black "Crafty"]
[Result "1/2-1/2"]

1.c4 e6 2.Nf3 d5 3.d4 Nf6 4.Nc3 Be7 5.Bf4 O-O 6.e3 Nbd7 7.c5 Nh5 8.Bd3 Nxf4
9.exf4 c6 10.Qc2 g6 11.h4 Nf6 12.a3 b6 13.b4 Qc7 14.g3 a5 15.Na4 b5 16.Nb6
Ra7 17.O-O axb4 18.axb4 Rxa1 19.Rxa1 Bb7 20.Qe2 Nd7 21.Nxd7 Qxd7 22.Ne5 Qc7
23.h5 Bf6 24.Qg4 Re8 25.Ra7 Kf8 26.hxg6 hxg6 27.Nxf7 Qxf7 28.Bxg6 Qg7 29.Rxb7
Qxb7 30.Bxe8 Kxe8 31.Qxe6+ Be7 32.f5 Qd7 33.Qg8+ Bf8 34.Qg6+ Kd8 35.Qf6+ Be7
36.Qh8+ Qe8 37.Qe5 Kd7 38.Qe6+ Kd8 39.Qe5 Kd7 40.Qe6+ Kd8 41.Qe5 1/2-1/2
</pre>

=See also=
* [[Alice]]
* [[Queen (engine)]]

=Forum Posts=
==2010==
* [http://www.talkchess.com/forum/viewtopic.php?t=35846 RedQueen 0.6] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], August 21, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=36417 Redqueen v0.7] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], October 18, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=36630 Redqueen v0.7.5 (ACCA 2010)] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], November 08, 2010 » [[ACCA 2010]]
* [http://www.talkchess.com/forum/viewtopic.php?t=36891 Redqueen v0.8] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], December 01, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=36967 Test position for average engines] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], December 06, 2010 » [[DOCCC 2010]], [[Fridolin]]
==2011==
* [http://www.talkchess.com/forum/viewtopic.php?t=37884 Redqueen v0.9 release] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], January 31, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38015 Redqueen v0.9.1 release] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], February 10, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38149 Redqueen v0.9.5 release] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], February 21, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38638 RedQueen for Android] by [[Aart Bik]], [[CCC]], April 03, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=38888 RedQueen v0.9.8 release] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], April 27, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39819 2011 Fifth Annual ACCA WCRCC: RedQueen games] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], July 23, 2011 » [[WCRCC 2011]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40265 RedQueen 1.0 beta release] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], September 04, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41067 2011 6ht annual ACCA games (RedQueen's games)] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], November 13, 2011 » [[ACCA 2011]]
==2012 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=42884 RedQueen 1.1 released] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], March 15, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=42892 RedQueen 1.1.1 (bugfix release)] by [[Ben-Hur Carlos Vieira Langoni Junior|Ben-Hur Carlos Langoni]], [[CCC]], March 15, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=42896 RedQueen 1.1.1 on Mac OS X] by [[Robert Purves]], [[CCC]], March 16, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43021 Redqueen 1.1.1 64-bit - Is this a bug?] by [[Gabor Szots]], [[CCC]], March 26, 2012
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=60130 Redqueen v1.1.98 Linux/Windows 64 bit edition] by [[Norbert Raimund Leisner]], {{CCC]], May 11, 2016
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=60325 RedQueen for the Mac] by [[Michael Byrne|MikeB]], [[CCC]], May 31, 2016

=External Links=
==Chess Engine==
* [https://sourceforge.net/projects/redqueenchess/ RedQueen Chess Engine website]
* [http://redqueenchess.sourceforge.net/ RedQueen | Chess Engine]
* [http://www.computerchess.org.uk/ccrl/4040/cgi/compare_engines.cgi?family=RedQueen&print=Rating+list&print=Results+table&print=LOS+table&print=Ponder+hit+table&print=Eval+difference+table&print=Comopp+gamenum+table&print=Overlap+table&print=Score+with+common+opponents RedQueen] in [[CCRL|CCRL 40/4]]
==Misc==
* [https://en.wikipedia.org/wiki/Red_Queen Red Queen (disambiguation) from Wikipedia]
* [https://en.wikipedia.org/wiki/Red_Queen_%28Through_the_Looking-Glass%29 Red Queen (Through the Looking-Glass) - Wikipedia]
: [https://en.wikipedia.org/wiki/Red_Queen%27s_race Red Queen's race from Wikipedia]
* [https://en.wikipedia.org/wiki/The_Red_Queen%27s_Race The Red Queen's Race from Wikipedia] ([[:Category:Isaac Asimov|Isaac Asimov]])
* [https://en.wikipedia.org/wiki/Red_Queen_hypothesis Red Queen hypothesis from Wikipedia]
* [https://en.wikipedia.org/wiki/Red_Queen_%28comics%29 Red Queen (comics) from Wikipedia]
* [https://en.wikipedia.org/wiki/The_Red_Queen:_Sex_and_the_Evolution_of_Human_Nature The Red Queen: Sex and the Evolution of Human Nature - Wikipedia]
* [[:Category:Gryphon|Gryphon]] - Checkmate, [https://en.wikipedia.org/wiki/Red_Queen_to_Gryphon_Three Red Queen to Gryphon Three] (1974), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=LXvLm_p1JII|alignment=left|valignment=top}}

=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Open Source]]
[[Category:GPL]]
[[Category:UCI]]
[[Category:Chess Pieces]]
[[Category:Comics]]
[[Category:Fiction]]
[[Category:Isaac Asimov]]
[[Category:John Tenniel]]
[[Category:Lewis Carroll]]
[[Category:Gryphon]]

Navigation menu