Difference between revisions of "OliThink"

From Chessprogramming wiki
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 11: Line 11:
 
<span id="SlidingPieceAttacks"></span>
 
<span id="SlidingPieceAttacks"></span>
 
==Sliding Piece Attacks==
 
==Sliding Piece Attacks==
−
OliThink pre 5 versions used [[Rotated Bitboards|rotated bitboards]] to determine [[Sliding Piece Attacks|sliding piece attacks]]. Since version 5, only the usual [[Occupancy|occupancy]] is used to [[Occupancy of any Line|map the masked line to an index]], for [[Files|files]] and [[Diagonals|diagonals]] by a [[General Setwise Operations#Multiplication|north-fill multiplication]] and right shift as also applied in [[Kindergarten Bitboards|kindergarten bitboards]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=24724 Kindergarten Bitboard Approach by Gerd Isenberg] by [[Edsel Apostol]], [[CCC]], November 05, 2008</ref>, with the addition not only to lookup attack bitboards, but also [[X-ray Attacks (Bitboards)#Xray1|X-ray attacks]] through the first blocking pieces (if any) of both [[Direction|ray-directions]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=166649&t=18750 Re: Question about SEE (Static exchange evaluation)] by [[Oliver Brausch]], [[CCC]], December 18, 2007</ref> . A pre-initialized [[Array|array]] of 8 times 8K bitboards (512 Kbyte in total) is used for attacks on [[Ranks|ranks]], files, diagonals and [[Anti-Diagonals|anti-diagonals]] in its lower half, while the upper half holds appropriate x-ray attacks. Per line, a 13-bit index is composed of the 6-bit square index and a 7-bit occupancy key.  
+
OliThink pre 5 versions used [[Rotated Bitboards|rotated bitboards]] to determine [[Sliding Piece Attacks|sliding piece attacks]]. Since version 5, only the usual [[Occupancy|occupancy]] is used to [[Occupancy of any Line|map the masked line to an index]], for [[Files|files]] and [[Diagonals|diagonals]] by a [[General Setwise Operations#Multiplication|north-fill multiplication]] and right shift as also applied in [[Kindergarten Bitboards|kindergarten bitboards]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=24724 Kindergarten Bitboard Approach by Gerd Isenberg] by [[Edsel Apostol]], [[CCC]], November 05, 2008</ref>, with the addition not only to lookup attack bitboards, but also [[X-ray Attacks (Bitboards)#Xray1|X-ray attacks]] through the first blocking pieces (if any) of both [[Direction|ray-directions]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=166649&t=18750 Re: Question about SEE (Static exchange evaluation)] by [[Oliver Brausch]], [[CCC]], December 18, 2007</ref> . A pre-initialized [[Array|array]] of 8 times 4K bitboards (256 Kbyte in total) is used for attacks on [[Ranks|ranks]], files, diagonals and [[Anti-Diagonals|anti-diagonals]] in its lower half, while the upper half holds appropriate x-ray attacks. Per line, a 12-bit index is composed of the 6-bit square index and a 6-bit occupancy key <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77339&start=44 Re: OliThink 5.9.5 is very small] by [[Oliver Brausch]], [[CCC]], June 06, 2021</ref>.  
  
 
===C Source===
 
===C Source===
−
These are the relevant code snippets and data declarations of the attack and x-ray attack getter in the [[C]] source, initialization omitted <ref>[http://brausch.org/home/chess/index.html Chess Engine OliThink - OliThink Source Code Vers. 5.3.2 Native - olithink.c (slightly edited)]</ref>. Using addition instead of bitwise-or might take advantage of the [[x86]] lea instruction, specially for the line-offsets:  
+
These are the relevant code snippets and data declarations of the attack and x-ray attack getter in the [[C]] source, initialization omitted <ref>[https://github.com/olithink/OliThink/commit/78fa794f777bd5e851fc0abbcfc1bca22e6c0dcf 5.9.8a Half sized bitboards  (slightly edited)]</ref> :  
 
<pre>
 
<pre>
−
static u64 rays[0x10000]; /* 8*64 = 512 KByte */
+
static u64 rays[0x8000]; /* 256 KByte */
 
u64 bmask45[64];
 
u64 bmask45[64];
 
u64 bmask135[64];
 
u64 bmask135[64];
Line 22: Line 22:
 
#define BOARD (colorb[0] | colorb[1])
 
#define BOARD (colorb[0] | colorb[1])
  
−
#define RATT1(f)  rays[((f) << 7) | key000(BOARD, f)        ]
+
#define RATT1(f)  rays[((f) << 6) | key000(BOARD, f)        ]
−
#define RATT2(f)  rays[((f) << 7) | key090(BOARD, f) | 0x2000]
+
#define RATT2(f)  rays[((f) << 6) | key090(BOARD, f) | 0x1000]
−
#define BATT3(f)  rays[((f) << 7) | key045(BOARD, f) | 0x4000]
+
#define BATT3(f)  rays[((f) << 6) | key045(BOARD, f) | 0x2000]
−
#define BATT4(f)  rays[((f) << 7) | key135(BOARD, f) | 0x6000]
+
#define BATT4(f)  rays[((f) << 6) | key135(BOARD, f) | 0x3000]
−
#define RXRAY1(f) rays[((f) << 7) | key000(BOARD, f) | 0x8000]
+
#define RXRAY1(f) rays[((f) << 6) | key000(BOARD, f) | 0x4000]
−
#define RXRAY2(f) rays[((f) << 7) | key090(BOARD, f) | 0xA000]
+
#define RXRAY2(f) rays[((f) << 6) | key090(BOARD, f) | 0x5000]
−
#define BXRAY3(f) rays[((f) << 7) | key045(BOARD, f) | 0xC000]
+
#define BXRAY3(f) rays[((f) << 6) | key045(BOARD, f) | 0x6000]
−
#define BXRAY4(f) rays[((f) << 7) | key135(BOARD, f) | 0xE000]
+
#define BXRAY4(f) rays[((f) << 6) | key135(BOARD, f) | 0x7000]
  
−
int key000(u64 b, int f) {return (int) ((b >> (f & 56)) & 0x7E);}
+
int key000(u64 b, int f) {return (int) ((b >> ((f & 56) + 1)) & 0x3F);}
 
int key090(u64 b, int f) {
 
int key090(u64 b, int f) {
 
   u64 _b = (b >> (f&7)) & 0x0101010101010101LL;
 
   u64 _b = (b >> (f&7)) & 0x0101010101010101LL;
 
   _b = _b * 0x0080402010080400LL;
 
   _b = _b * 0x0080402010080400LL;
−
   return (int)(_b >> 57);
+
   return (int)(_b >> 58);
 
}
 
}
 
int keyDiag(u64 _b) {
 
int keyDiag(u64 _b) {
 
   _b = _b * 0x0202020202020202LL;
 
   _b = _b * 0x0202020202020202LL;
−
   return (int)(_b >> 57);
+
   return (int)(_b >> 58);
 
}
 
}
 
int key045(u64 b, int f) {return keyDiag(b & bmask45[f]);}
 
int key045(u64 b, int f) {return keyDiag(b & bmask45[f]);}
Line 45: Line 45:
 
</pre>
 
</pre>
 
===Java Source===
 
===Java Source===
−
In [[Java]], the code looks quite similar, embedded inside the class OliThink <ref>[http://brausch.org/home/chess/index.html Chess Engine OliThink - OliThink Source Code Vers. 5.3.2 Java - olithink.java (slightly edited)]</ref>, using the [https://en.wikipedia.org/wiki/Bitwise_operation#Shifts_in_Java unsigned right shift operator] (>>>) instead the arithmetical one (>>) inside the keyxxx routines would safe the post-masking with 0x7f:
+
In [[Java]], the code looks quite similar, embedded inside the class OliThink <ref>[http://brausch.org/home/chess/index.html Chess Engine OliThink - OliThink Source Code Vers. 5.3.2 Java - olithink.java (slightly edited)]</ref>:
 
<pre>
 
<pre>
−
final static long[] rays = new long[0x10000];
+
final static long[] rays = new long[0x8000];
 
final static long[] bmask45 = new long[64];
 
final static long[] bmask45 = new long[64];
 
final static long[] bmask135 = new long[64];
 
final static long[] bmask135 = new long[64];
Line 53: Line 53:
 
static long BOARD() { return (colorb[0] | colorb[1]); }
 
static long BOARD() { return (colorb[0] | colorb[1]); }
  
−
static long RATT1(int f)  {return rays[((f) << 7) | key000(BOARD(), f)        ];}
+
static long RATT1(int f)  {return rays[((f) << 6) | key000(BOARD(), f)        ];}
−
static long RATT2(int f)  {return rays[((f) << 7) | key090(BOARD(), f) | 0x2000];}
+
static long RATT2(int f)  {return rays[((f) << 6) | key090(BOARD(), f) | 0x1000];}
−
static long BATT3(int f)  {return rays[((f) << 7) | key045(BOARD(), f) | 0x4000];}
+
static long BATT3(int f)  {return rays[((f) << 6) | key045(BOARD(), f) | 0x2000];}
−
static long BATT4(int f)  {return rays[((f) << 7) | key135(BOARD(), f) | 0x6000];}
+
static long BATT4(int f)  {return rays[((f) << 6) | key135(BOARD(), f) | 0x3000];}
−
static long RXRAY1(int f) {return rays[((f) << 7) | key000(BOARD(), f) | 0x8000];}
+
static long RXRAY1(int f) {return rays[((f) << 6) | key000(BOARD(), f) | 0x4000];}
−
static long RXRAY2(int f) {return rays[((f) << 7) | key090(BOARD(), f) | 0xA000];}
+
static long RXRAY2(int f) {return rays[((f) << 6) | key090(BOARD(), f) | 0x5000];}
−
static long BXRAY3(int f) {return rays[((f) << 7) | key045(BOARD(), f) | 0xC000];}
+
static long BXRAY3(int f) {return rays[((f) << 6) | key045(BOARD(), f) | 0x6000];}
−
static long BXRAY4(int f) {return rays[((f) << 7) | key135(BOARD(), f) | 0xE000];}
+
static long BXRAY4(int f) {return rays[((f) << 6) | key135(BOARD(), f) | 0x7000];}
  
−
static int key000(long b, int f) {return (int) ((b >> (f & 56)) & 0x7E);}
+
static int key000(long b, int f) {return (int) ((b >> ((f & 56) + 1)) & 0x3f);}
 
static int key090(long b, int f) {
 
static int key090(long b, int f) {
 
   long _b = (b >> (f&7)) & 0x0101010101010101L;
 
   long _b = (b >> (f&7)) & 0x0101010101010101L;
 
   _b = _b * 0x0080402010080400L;
 
   _b = _b * 0x0080402010080400L;
−
   return (int)((_b >> 57) & 0x7F);
+
   return (int)((_b >> 58) & 0x3F);
 
}
 
}
 
static int keyDiag(long _b) {
 
static int keyDiag(long _b) {
 
   _b = _b * 0x0202020202020202L;
 
   _b = _b * 0x0202020202020202L;
−
   return (int)((_b >> 57) & 0x7F);
+
   return (int)((_b >> 58) & 0x3F);
 
}
 
}
 
static int key045(long b, int f) {return keyDiag(b & bmask45[f]);}
 
static int key045(long b, int f) {return keyDiag(b & bmask45[f]);}
Line 182: Line 182:
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75670 Ancient olithink fossils] by [[Dann Corbit]], [[CCC]], November 03, 2020
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75670 Ancient olithink fossils] by [[Dann Corbit]], [[CCC]], November 03, 2020
 
: [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75670&start=1 Re: Ancient olithink fossils] by Ajedrecista, [[CCC]], November 03, 2020
 
: [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75670&start=1 Re: Ancient olithink fossils] by Ajedrecista, [[CCC]], November 03, 2020
 +
'''2021'''
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77339 OliThink 5.9.5 is very small] by [[Oliver Brausch]], [[CCC]], May 18, 2021
 +
: [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77339&start=44 Re: OliThink 5.9.5 is very small] by [[Oliver Brausch]], [[CCC]], June 06, 2021 » [[Kindergarten Bitboards]]
  
 
=External Links=  
 
=External Links=  
 +
* [https://github.com/olithink/OliThink GitHub - olithink/OliThink: OliThink 5]
 
* [http://brausch.org/home/chess/index.html Chess Engine OliThink] by [[Oliver Brausch]]
 
* [http://brausch.org/home/chess/index.html Chess Engine OliThink] by [[Oliver Brausch]]
 
* [http://computerchess.org.uk/ccrl/4040/cgi/engine_details.cgi?print=Details+%28text%29&eng=OliThink%205.3.0 OliThink 5.3.0] in [[CCRL|CCRL 40/40]]
 
* [http://computerchess.org.uk/ccrl/4040/cgi/engine_details.cgi?print=Details+%28text%29&eng=OliThink%205.3.0 OliThink 5.3.0] in [[CCRL|CCRL 40/40]]

Latest revision as of 12:46, 7 June 2021

Home * Engines * OliThink

OliThink5 Java online [1]

OliThink,
an open source chess engine supporting the Chess Engine Communication Protocol written by Oliver Brausch with C and Java versions available, and binaries running under Windows, Linux and Mac OS [2]. The completely rewritten OliThink 5.x has a very fast move generator based on the framework of the Perft program OliPerft with a plain bitboard board representation without any piece-lists or board arrays [3]. OliThink's evaluation consists almost of material balance and mobility, plus a very simple pawn structure evaluation, rewarding passed pawns. OliThink 4.13 played the CCT6 in 2004, with four points out of nine games [4]. In June 2020, after a long break, Oliver Brausch published OliThink 5.4.0 with a big leap in playing strength due to modifications in evaluation of likely drawn endgames [5].

Description

Search

OliThink's search relies on PVS without aspiration windows in its iterative deepening loop [6], along with a fixed sized transposition table. It further applies flexible null move pruning, late move reductions [7], IID, singular reply-, check- and passed pawn extensions [8]. Move ordering considers PV-moves stored in a triangular PV-Table, SEE, killer- and history heuristic.

Sliding Piece Attacks

OliThink pre 5 versions used rotated bitboards to determine sliding piece attacks. Since version 5, only the usual occupancy is used to map the masked line to an index, for files and diagonals by a north-fill multiplication and right shift as also applied in kindergarten bitboards [9], with the addition not only to lookup attack bitboards, but also X-ray attacks through the first blocking pieces (if any) of both ray-directions [10] . A pre-initialized array of 8 times 4K bitboards (256 Kbyte in total) is used for attacks on ranks, files, diagonals and anti-diagonals in its lower half, while the upper half holds appropriate x-ray attacks. Per line, a 12-bit index is composed of the 6-bit square index and a 6-bit occupancy key [11].

C Source

These are the relevant code snippets and data declarations of the attack and x-ray attack getter in the C source, initialization omitted [12] : 

static u64 rays[0x8000]; /* 256 KByte */
u64 bmask45[64];
u64 bmask135[64];

#define BOARD (colorb[0] | colorb[1])

#define RATT1(f)  rays[((f) << 6) | key000(BOARD, f)         ]
#define RATT2(f)  rays[((f) << 6) | key090(BOARD, f) | 0x1000]
#define BATT3(f)  rays[((f) << 6) | key045(BOARD, f) | 0x2000]
#define BATT4(f)  rays[((f) << 6) | key135(BOARD, f) | 0x3000]
#define RXRAY1(f) rays[((f) << 6) | key000(BOARD, f) | 0x4000]
#define RXRAY2(f) rays[((f) << 6) | key090(BOARD, f) | 0x5000]
#define BXRAY3(f) rays[((f) << 6) | key045(BOARD, f) | 0x6000]
#define BXRAY4(f) rays[((f) << 6) | key135(BOARD, f) | 0x7000]

int key000(u64 b, int f) {return (int) ((b >> ((f & 56) + 1)) & 0x3F);}
int key090(u64 b, int f) {
   u64 _b = (b >> (f&7)) & 0x0101010101010101LL;
  _b = _b * 0x0080402010080400LL;
   return (int)(_b >> 58);
}
int keyDiag(u64 _b) {
   _b = _b * 0x0202020202020202LL;
   return (int)(_b >> 58);
}
int key045(u64 b, int f) {return keyDiag(b & bmask45[f]);}
int key135(u64 b, int f) {return keyDiag(b & bmask135[f]);}

Java Source

In Java, the code looks quite similar, embedded inside the class OliThink [13]: 

final static long[] rays = new long[0x8000];
final static long[] bmask45 = new long[64];
final static long[] bmask135 = new long[64];

static long BOARD() { return (colorb[0] | colorb[1]); }

static long RATT1(int f)  {return rays[((f) << 6) | key000(BOARD(), f)         ];}
static long RATT2(int f)  {return rays[((f) << 6) | key090(BOARD(), f) | 0x1000];}
static long BATT3(int f)  {return rays[((f) << 6) | key045(BOARD(), f) | 0x2000];}
static long BATT4(int f)  {return rays[((f) << 6) | key135(BOARD(), f) | 0x3000];}
static long RXRAY1(int f) {return rays[((f) << 6) | key000(BOARD(), f) | 0x4000];}
static long RXRAY2(int f) {return rays[((f) << 6) | key090(BOARD(), f) | 0x5000];}
static long BXRAY3(int f) {return rays[((f) << 6) | key045(BOARD(), f) | 0x6000];}
static long BXRAY4(int f) {return rays[((f) << 6) | key135(BOARD(), f) | 0x7000];}

static int key000(long b, int f) {return (int) ((b >> ((f & 56) + 1)) & 0x3f);}
static int key090(long b, int f) {
   long _b = (b >> (f&7)) & 0x0101010101010101L;
   _b = _b * 0x0080402010080400L;
   return (int)((_b >> 58) & 0x3F);
}
static int keyDiag(long _b) {
   _b = _b * 0x0202020202020202L;
   return (int)((_b >> 58) & 0x3F);
}
static int key045(long b, int f) {return keyDiag(b & bmask45[f]);}
static int key135(long b, int f) {return keyDiag(b & bmask135[f]);}

Selected Games

SEE

CCT6, SEE - OliThink 4.13 [14] 

[Event "CCT6"]
[Site "Internet Chess Club"]
[Date "2004.01.31"]
[Round "3"]
[White "SEE"]
[Black "OliThink 4.13"]
[Result "0-1"]

1.Nf3 d5 2.d4 e6 3.Bd2 c5 4.e3 Nc6 5.Bb5 Bd7 6.O-O Qb6 7.Nc3 cxd4 8.Nxd4 Nxd4 9.Bxd7+ 
Kxd7 10.exd4 Qxd4 11.Qe2 Nf6 12.Be3 Qb4 13.a3 Qa5 14.b4 Qa6 15.Qxa6 bxa6 16.Bd4 Rc8 
17.Ra2 a5 18.b5 Bc5 19.Ne2 Bxd4 20.Nxd4 a4 21.Rb2 Rc3 22.Ra1 Rb8 23.Nc6 Rc8 24.Ne5+ 
Ke8 25.Raa2 Ne4 26.Nc6 a6 27.Na7 R8c7 28.b6 Rb7 29.Rb4 Nd6 30.g3 Nc4 31.Nc6 Kd7 32.Nd4 
Nxb6 33.Ne2 Rc5 34.Rab2 Kc6 35.Kg2 e5 36.c3 f6 37.Rb1 a5 38.R4b2 g5 39.f3 h5 40.g4 h4 
41.Kf2 Rb8 42.Ke1 Kc7 43.Kf2 Nd7 44.Rxb8 Nxb8 45.Ke3 Nd7 46.Kf2 Nb6 47.Ke3 Nc4+ 48.Kd3 
Nxa3 49.Ra1 Nc4 50.Rb1 a3 51.Nc1 Nb2+ 52.Kc2 d4 53.Na2 d3+ 54.Kd2 Rd5 55.c4 Nxc4+ 
56.Ke1 d2+ 57.Ke2 Nb2 58.Rd1 Nxd1 0-1

Bodo

CCT6, Bodo - OliThink 4.13 [15] 

[Event "CCT6"]
[Site "Internet Chess Club"]
[Date "2004.02.01"]
[Round "9"]
[White "Bodo"]
[Black "OliThink 4.13"]
[Result "1-0"]

1.Nf3 d5 2.g3 g6 3.Bg2 Bg7 4.d4 Nf6 5.Ne5 c6 6.O-O Nbd7 7.c4 Ne4 8.cxd5 Nxe5 9.dxe5 
cxd5 10.Qa4+ Bd7 11.Qb4 Bxe5 12.Qxb7 Nf6 13.Nc3 e6 14.e4 Bxc3 15.bxc3 Nxe4 16.Bxe4 dxe4 
17.Bh6 f5 18.Rfd1 Rc8 19.Qxa7 Rg8 20.Rab1 Rc7 21.Qd4 Qc8 22.Qf6 g5 23.Rb8 Qxb8 24.Bxg5 
Rxg5 25.Qh8+ Ke7 26.Qxb8 Rc8 27.Qd6+ Kf6  1-0

Forum Posts

1998 ...

2000 ...

2005 ...

2008

2009

2010 ...

2011

2012

2020 ...

Re: Ancient olithink fossils by Ajedrecista, CCC, November 03, 2020

2021

Re: OliThink 5.9.5 is very small by Oliver Brausch, CCC, June 06, 2021 » Kindergarten Bitboards

External Links

References

  1. ↑ Chess Engine OliThink by Oliver Brausch
  2. ↑ Chess Engine OliThink by Oliver Brausch
  3. ↑ OliPerft with divide Option as Pre Version for OliThink 5 by Oliver Brausch, CCC, December 27, 2007
  4. ↑ OliThink@CCT6 - Programmers View by Oliver Brausch, CCC, February 03, 2004
  5. ↑ OliThink 5.4.0 has been published with an big leap in strength for only 3 lines of code by Oliver Brausch, CCC, June 16, 2020
  6. ↑ OliThink 5.1.2 released by Oliver Brausch, CCC, April 03, 2008
  7. ↑ OliThink 5.2.6 released introducing LMR by Oliver Brausch, CCC, December 31, 2009
  8. ↑ OliThink 5.1.1 released by Oliver Brausch, CCC, March 21, 2008
  9. ↑ Kindergarten Bitboard Approach by Gerd Isenberg by Edsel Apostol, CCC, November 05, 2008
  10. ↑ Re: Question about SEE (Static exchange evaluation) by Oliver Brausch, CCC, December 18, 2007
  11. ↑ Re: OliThink 5.9.5 is very small by Oliver Brausch, CCC, June 06, 2021
  12. ↑ 5.9.8a Half sized bitboards (slightly edited)
  13. ↑ Chess Engine OliThink - OliThink Source Code Vers. 5.3.2 Java - olithink.java (slightly edited)
  14. ↑ CCT6 hosted by Volker Richey
  15. ↑ CCT6 hosted by Volker Richey

Up one level

Retrieved from "https://www.chessprogramming.org/index.php?title=OliThink&oldid=24939"