25,161
edits
Changes
Created page with "'''Home * Engines * EXchess''' '''EXchess''', (Experimental Chess Program)<br/> a Chess Engine Communication Protocol compatible experimental :Categor..."
'''[[Main Page|Home]] * [[Engines]] * EXchess'''
'''EXchess''', (Experimental Chess Program)<br/>
a [[Chess Engine Communication Protocol]] compatible experimental [[:Category:Open Source|open source chess engine]] by [[Dan Homan|Daniel Homan]],
written in [[Cpp|C++]], released under the [[Free Software Foundation#GPL|GNU Public License]].
EXchess may optionally use an own [[GUI]] based on the [https://en.wikipedia.org/wiki/FLTK Fast Light Tool Kit (FLTK)].
=Board Representation=
EXchess utilizes an [[8x8 Board]] and [[Piece-Lists|piece lists]] as demonstrated in its [[Move Generation|move generation routine]] <ref>[http://personal.denison.edu/%7Ehomand/EXchess_files/EXchess_v5.01beta_source.tar.gz EXchess v5.01 beta source code], chess.h, moves.cpp</ref> :
<pre>
struct square {
char type; // type of piece (0 - 6)
char side; // side which owns square (1 = white)
};
struct position {
square sq[64];
...
char plist[2][7][10];
...
};
void position::allmoves(move_list *list, tree_search *ts) {
...
for(i=1;i<=plist[wtm][PAWN][0];i++)
pawn_moves(list, plist[wtm][PAWN][i], ts);
for(i=1;i<=plist[wtm][KNIGHT][0];i++)
knight_moves(list, plist[wtm][KNIGHT][i], ts);
...
}
</pre>
=Search=
The ches engine performs advanced [[Search|search]] algorithms including [[Principal Variation Search|principle variation search]],
[[Null Move Pruning|null move]], [[Null Move Pruning#ZugzwangVerification|null move verification]], [[Extensions|dynamic search extensions]], [[Futility Pruning|futility pruning]], [[Hash Table|hash tables]], [[History Heuristic|history tables]], [[Quiescence Search|quiescence search]], and a [[Static Exchange Evaluation|material swap function]] <ref>[https://www.stmintz.com/ccc/index.php?id=161209 SEE and possible EXChess bug] by [[Gian-Carlo Pascutto]], [[CCC]], April 01, 2001</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=162704 EXchess v4.02 released] by [[Dan Homan]], [[CCC]], April 10, 2001</ref>.
<span id="LazySMP"></span>
=Lazy SMP=
[[Dan Homan|Daniel Homan]] in July 2013 on his [[Lazy SMP]] implementation and work sharing <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan|Daniel Homan]], [[CCC]], July 03, 2013 </ref>:
I changed the work-sharing approach to Lazy SMP in EXchess to be closer to the [[ABDADA]] model after [[Daniel Shawul|Daniel Shawul's]] posts about his tests on the subject <ref> [http://www.talkchess.com/forum/viewtopic.php?t=47887 ABDADA speedup results] by [[Daniel Shawul]], [[CCC]], May 01, 2013</ref>. However, I didn't want to use a [[Transposition Table|hash table]] to keep a counter for the [[Thread|threads]] working on a given position. My hash table already had a 16 byte long entry, so I didn't want to expand it, and I also didn't like the idea of having to make each move before seeing whether another thread was searching it.
So as an alternative to the hash table, I made a simple work sharing data structure. In the end, it was just a single hash key for a position which is OR'd with the move being searched and the depth of the search. I use this to keep track of the move being searched at each ply of the tree for a given thread. Then, before I search a move at a given ply, I can just check the same ply in the other threads to see that the move is not already being worked on at that depth. If it is, then the move get placed at the end of the move list to be searched last. This doesn't allow for [[Transposition|transpositions]] , but I expected the most likely work collisions to be as the threads are walking the [[Principal Variation|PV]] where they will initially all be the same. Indeed, this scheme only helps in the PV, and if I check for work sharing in [[Node Types|non-PV nodes]], it only slows things down a bit.
My previous Lazy SMP work sharing was just to alternate moves (odd-even) in the root node for the odd-even threads. The above approach is about 10% faster than my previous scheme, and I get a time-to-depth improvement of roughly 1.65 for 2 threads compared to 1 thread and roughly 2.5 for 4 threads compared to 1 thread. Maybe not quite as good as ABDADA with a hash table counter, but not too bad for the simplicity.
=TD-leaf=
EXchess applies [[Evaluation|evaluation]] [[Learning|learning]] using the [[Temporal Difference Learning]] (TD-leaf) <ref>[https://www.stmintz.com/ccc/index.php?id=139716 New version of EXchess] by [[Dan Homan]], [[CCC]], November 18, 2000</ref>.
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=16657 New version of EXchess released] by [[Dan Homan]], [[CCC]], April 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=20450 EXchess 2.37] by [[Dan Homan]], [[CCC]], June 13, 1998
* [https://www.stmintz.com/ccc/index.php?id=31385 New EXchess Version] by [[Dan Homan]], [[CCC]], November 02, 1998
* [https://www.stmintz.com/ccc/index.php?id=82280 EXchess pre-release testers sought] by [[Dan Homan]], [[CCC]], December 13, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=108784 version 3.14 of EXchess released] by [[Dan Homan]], [[CCC]], May 02, 2000
* [https://www.stmintz.com/ccc/index.php?id=139716 New version of EXchess] by [[Dan Homan]], [[CCC]], November 18, 2000
* [https://www.stmintz.com/ccc/index.php?id=162704 EXchess v4.02 released] by [[Dan Homan]], [[CCC]], April 10, 2001
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43496 Wb2UCI and Problems with ExChess4.03a and GnuChess4.0.8] by [[Arturo Ochoa]], [[Computer Chess Forums|Winboard Forum]], July 24, 2003 » [[Wb2UCI]], [[InBetween]]
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=483082 New Version of EXchess] by [[Dan Homan]], [[CCC]], Januaray 29, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=27266 Insanity... or Tal style?] by [[Miguel A. Ballicora]], [[CCC]], April 01, 2009 (refers EXchess) » [[Automated Tuning]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=41666 EXchess v6.01] by [[Dan Homan|Daniel Homan]], [[CCC]], December 29, 2011
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=42202 EXchess v6.10 released] by [[Dan Homan|Daniel Homan]], [[CCC]], January 29, 2012 » [[CLOP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44842 EXchess v6.50 released] by [[Dan Homan|Daniel Homan]], [[CCC]], August 19, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46513 EXchess v6.70 released] by [[Dan Homan|Daniel Homan]], [[CCC]], December 20, 2012
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47473 EXchess v7.01 Released] by [[Dan Homan|Daniel Homan]], [[CCC]], March 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47528 EXchess v7.02 released] by [[Dan Homan|Daniel Homan]], [[CCC]], March 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47643 EXchess v7.03 released (bugfix + speed improved version] by [[Dan Homan|Daniel Homan]], [[CCC]], March 29, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48448 EXchess v7.11 released] by [[Dan Homan|Daniel Homan]], [[CCC]], June 27, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan|Daniel Homan]], [[CCC]], July 03, 2013 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49356 EXchess v7.17 released] by [[Dan Homan|Daniel Homan]], [[CCC]], September 14, 2013
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=52241 EXchess v7.26 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 07, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53319 EXchess v7.31 released] by [[Dan Homan|Daniel Homan]], [[CCC]], August 17, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54756 EXchess v7.51 released] by [[Dan Homan|Daniel Homan]], [[CCC]], December 26, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56519 EXchess v7.71 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 29, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58737 EXchess v7.88 Released] by [[Dan Homan|Daniel Homan]], [[CCC]], December 30, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=60121 EXchess v7.91 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 10, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60121&start=2 EXchess v7.92 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 11, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61650 EXchess v7.92 and AMD Processors] by [[Dan Homan|Daniel Homan]], [[CCC]], October 08, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62995 EXchess v7.96] by [[Dan Homan|Daniel Homan]], [[CCC]], January 31, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63044 EXchess v7.97] by [[Dan Homan|Daniel Homan]], [[CCC]], February 04, 2017
=External Links=
* [https://sites.google.com/site/experimentalchessprogram/ Experimental Chess Program]
* [http://computerchess.org.uk/ccrl/4040/cgi/compare_engines.cgi?family=EXchess&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 EXchess] in [[CCRL|CCRL 40/40]]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Open Source]]
[[Category:GPL]]
[[Category:WinBoard]]
[[Category:XBoard]]
'''EXchess''', (Experimental Chess Program)<br/>
a [[Chess Engine Communication Protocol]] compatible experimental [[:Category:Open Source|open source chess engine]] by [[Dan Homan|Daniel Homan]],
written in [[Cpp|C++]], released under the [[Free Software Foundation#GPL|GNU Public License]].
EXchess may optionally use an own [[GUI]] based on the [https://en.wikipedia.org/wiki/FLTK Fast Light Tool Kit (FLTK)].
=Board Representation=
EXchess utilizes an [[8x8 Board]] and [[Piece-Lists|piece lists]] as demonstrated in its [[Move Generation|move generation routine]] <ref>[http://personal.denison.edu/%7Ehomand/EXchess_files/EXchess_v5.01beta_source.tar.gz EXchess v5.01 beta source code], chess.h, moves.cpp</ref> :
<pre>
struct square {
char type; // type of piece (0 - 6)
char side; // side which owns square (1 = white)
};
struct position {
square sq[64];
...
char plist[2][7][10];
...
};
void position::allmoves(move_list *list, tree_search *ts) {
...
for(i=1;i<=plist[wtm][PAWN][0];i++)
pawn_moves(list, plist[wtm][PAWN][i], ts);
for(i=1;i<=plist[wtm][KNIGHT][0];i++)
knight_moves(list, plist[wtm][KNIGHT][i], ts);
...
}
</pre>
=Search=
The ches engine performs advanced [[Search|search]] algorithms including [[Principal Variation Search|principle variation search]],
[[Null Move Pruning|null move]], [[Null Move Pruning#ZugzwangVerification|null move verification]], [[Extensions|dynamic search extensions]], [[Futility Pruning|futility pruning]], [[Hash Table|hash tables]], [[History Heuristic|history tables]], [[Quiescence Search|quiescence search]], and a [[Static Exchange Evaluation|material swap function]] <ref>[https://www.stmintz.com/ccc/index.php?id=161209 SEE and possible EXChess bug] by [[Gian-Carlo Pascutto]], [[CCC]], April 01, 2001</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=162704 EXchess v4.02 released] by [[Dan Homan]], [[CCC]], April 10, 2001</ref>.
<span id="LazySMP"></span>
=Lazy SMP=
[[Dan Homan|Daniel Homan]] in July 2013 on his [[Lazy SMP]] implementation and work sharing <ref>[http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan|Daniel Homan]], [[CCC]], July 03, 2013 </ref>:
I changed the work-sharing approach to Lazy SMP in EXchess to be closer to the [[ABDADA]] model after [[Daniel Shawul|Daniel Shawul's]] posts about his tests on the subject <ref> [http://www.talkchess.com/forum/viewtopic.php?t=47887 ABDADA speedup results] by [[Daniel Shawul]], [[CCC]], May 01, 2013</ref>. However, I didn't want to use a [[Transposition Table|hash table]] to keep a counter for the [[Thread|threads]] working on a given position. My hash table already had a 16 byte long entry, so I didn't want to expand it, and I also didn't like the idea of having to make each move before seeing whether another thread was searching it.
So as an alternative to the hash table, I made a simple work sharing data structure. In the end, it was just a single hash key for a position which is OR'd with the move being searched and the depth of the search. I use this to keep track of the move being searched at each ply of the tree for a given thread. Then, before I search a move at a given ply, I can just check the same ply in the other threads to see that the move is not already being worked on at that depth. If it is, then the move get placed at the end of the move list to be searched last. This doesn't allow for [[Transposition|transpositions]] , but I expected the most likely work collisions to be as the threads are walking the [[Principal Variation|PV]] where they will initially all be the same. Indeed, this scheme only helps in the PV, and if I check for work sharing in [[Node Types|non-PV nodes]], it only slows things down a bit.
My previous Lazy SMP work sharing was just to alternate moves (odd-even) in the root node for the odd-even threads. The above approach is about 10% faster than my previous scheme, and I get a time-to-depth improvement of roughly 1.65 for 2 threads compared to 1 thread and roughly 2.5 for 4 threads compared to 1 thread. Maybe not quite as good as ABDADA with a hash table counter, but not too bad for the simplicity.
=TD-leaf=
EXchess applies [[Evaluation|evaluation]] [[Learning|learning]] using the [[Temporal Difference Learning]] (TD-leaf) <ref>[https://www.stmintz.com/ccc/index.php?id=139716 New version of EXchess] by [[Dan Homan]], [[CCC]], November 18, 2000</ref>.
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=16657 New version of EXchess released] by [[Dan Homan]], [[CCC]], April 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=20450 EXchess 2.37] by [[Dan Homan]], [[CCC]], June 13, 1998
* [https://www.stmintz.com/ccc/index.php?id=31385 New EXchess Version] by [[Dan Homan]], [[CCC]], November 02, 1998
* [https://www.stmintz.com/ccc/index.php?id=82280 EXchess pre-release testers sought] by [[Dan Homan]], [[CCC]], December 13, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=108784 version 3.14 of EXchess released] by [[Dan Homan]], [[CCC]], May 02, 2000
* [https://www.stmintz.com/ccc/index.php?id=139716 New version of EXchess] by [[Dan Homan]], [[CCC]], November 18, 2000
* [https://www.stmintz.com/ccc/index.php?id=162704 EXchess v4.02 released] by [[Dan Homan]], [[CCC]], April 10, 2001
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=43496 Wb2UCI and Problems with ExChess4.03a and GnuChess4.0.8] by [[Arturo Ochoa]], [[Computer Chess Forums|Winboard Forum]], July 24, 2003 » [[Wb2UCI]], [[InBetween]]
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=483082 New Version of EXchess] by [[Dan Homan]], [[CCC]], Januaray 29, 2006
* [http://www.talkchess.com/forum/viewtopic.php?t=27266 Insanity... or Tal style?] by [[Miguel A. Ballicora]], [[CCC]], April 01, 2009 (refers EXchess) » [[Automated Tuning]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=41666 EXchess v6.01] by [[Dan Homan|Daniel Homan]], [[CCC]], December 29, 2011
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=42202 EXchess v6.10 released] by [[Dan Homan|Daniel Homan]], [[CCC]], January 29, 2012 » [[CLOP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44842 EXchess v6.50 released] by [[Dan Homan|Daniel Homan]], [[CCC]], August 19, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46513 EXchess v6.70 released] by [[Dan Homan|Daniel Homan]], [[CCC]], December 20, 2012
'''2013'''
* [http://www.talkchess.com/forum/viewtopic.php?t=46858 Lazy SMP, part 2] by [[Dan Homan|Daniel Homan]], [[CCC]], January 12, 2013 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=47473 EXchess v7.01 Released] by [[Dan Homan|Daniel Homan]], [[CCC]], March 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47528 EXchess v7.02 released] by [[Dan Homan|Daniel Homan]], [[CCC]], March 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47643 EXchess v7.03 released (bugfix + speed improved version] by [[Dan Homan|Daniel Homan]], [[CCC]], March 29, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48448 EXchess v7.11 released] by [[Dan Homan|Daniel Homan]], [[CCC]], June 27, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48536 Lazy SMP and Work Sharing] by [[Dan Homan|Daniel Homan]], [[CCC]], July 03, 2013 » [[Lazy SMP]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49356 EXchess v7.17 released] by [[Dan Homan|Daniel Homan]], [[CCC]], September 14, 2013
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=52241 EXchess v7.26 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 07, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=53319 EXchess v7.31 released] by [[Dan Homan|Daniel Homan]], [[CCC]], August 17, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54756 EXchess v7.51 released] by [[Dan Homan|Daniel Homan]], [[CCC]], December 26, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56519 EXchess v7.71 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 29, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58737 EXchess v7.88 Released] by [[Dan Homan|Daniel Homan]], [[CCC]], December 30, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=60121 EXchess v7.91 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 10, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=60121&start=2 EXchess v7.92 released] by [[Dan Homan|Daniel Homan]], [[CCC]], May 11, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61650 EXchess v7.92 and AMD Processors] by [[Dan Homan|Daniel Homan]], [[CCC]], October 08, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62995 EXchess v7.96] by [[Dan Homan|Daniel Homan]], [[CCC]], January 31, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63044 EXchess v7.97] by [[Dan Homan|Daniel Homan]], [[CCC]], February 04, 2017
=External Links=
* [https://sites.google.com/site/experimentalchessprogram/ Experimental Chess Program]
* [http://computerchess.org.uk/ccrl/4040/cgi/compare_engines.cgi?family=EXchess&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 EXchess] in [[CCRL|CCRL 40/40]]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[Category:Open Source]]
[[Category:GPL]]
[[Category:WinBoard]]
[[Category:XBoard]]
