Difference between revisions of "Titboards"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Titboards''' '''Titboards''' are a bitboard-based move generation technique inv...")
 
(Added a reference to new titboard engine (TDFA), as well as some new data on speed comparison between titboards and magic bitboards. Clarified the explanation for why titboards are not commonly used.)
 
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Titboards'''
 
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Titboards'''
  
−
'''Titboards''' are a bitboard-based move generation technique invented by [[Zach Wegner]] <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623&p=27838 Yet another new bitboard move generation method] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], September 22, 2006</ref>. Titboards are based on an extension of bitboards to ternary, hence the name ("bit" means binary digit, "tit" mean ternary digit). Titboards are only used for move generation, not for any other purposes that typical bitboard attack-getters will be used for.
+
'''Titboards''',<br/>
 +
a bitboard-based [[Move Generation|move generation]] technique invented by [[Zach Wegner]] <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623&p=27838 Yet another new bitboard move generation method] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], September 22, 2006</ref> and first implemented by Malik Tremain <ref name="TDFA">[https://github.com/TiltedDFA/TDFA TDFA - Titboard Engine] by Malik Tremain, January 22, 2024</ref>. Titboards are based on an extension of bitboards to ternary boards, hence the name ("bit" means binary digit, "tit" mean [https://en.wikipedia.org/wiki/Ternary_numeral_system  ternary digit]). Titboards are only used for move generation, not for any other purposes that typical bitboard attack-getters will be used for.
  
−
The idea of titboards is to eliminate bitscans. Typical bitboard move generation techniques generate a bitboard, intersect it with the set of allowable squares (empty or enemy-occupied), and then serialize that into a list of moves. Titboards take a bitboard occupancy for each side for just one rank, file, or diagonal, and convert them to ternary representations and add them together. This index can determine which squares can actually be moved to, instead of just attacked. It is used in a lookup table of 3^7=2187 entries per direction per square.
+
The idea of titboards is to eliminate [[BitScan|bitscans]]. Typical bitboard move generation techniques generate a bitboard, intersect it with the set of allowable [[Squares|squares]] (empty or enemy-occupied), and then [[Bitboard Serialization|serialize]] that into a list of moves. Titboards take a bitboard occupancy for each side for just one rank, file, or diagonal, and convert them to ternary representations and add them together. This index can determine which squares can actually be moved to, instead of just attacked. It is used in a lookup table of 3^7=2187 entries per [[Direction|direction]] per square.
  
−
Titboards are not typically used (there is no known engine that implements them). The reasons behind this are that they use a large amount of memory (more than [[Magic Bitboards]]), and they must keep another attack generation method beside them due to their inflexibility. However, they are very fast, possibly the fastest bitboard-based move generator.
+
Titboards are not typically used (there is one known engine that implements them <ref name="TDFA"/>). This is because they are currently slower than modern alternatives while being harder to implement. They require a large look-up table (~8.9 MB) and they work very differently from modern generation techniques likes [[Magic Bitboards]], where they require each direction to be calculated individually {File, Rank, Diagonal, Anti-Diagonal}. For each direction they require the input of (square, us, them), as a pose to (square, occupied) which is more commonly used.
 +
 
 +
=Speed=
 +
 
 +
Testing shows that titboards have no speed advantage over magic bitboards on modern hardware, however, the gap seemingly narrows on older CPUs that offer less efficient bitscan operations. A full array of results can be found here<ref>[https://github.com/TiltedDFA/TDFA/blob/3c4110f860f9c98b619a3f2565d139c92fe606c8/RunResults.txt TDFA - Perft result comparison]</ref>.
 +
 
 +
<pre>
 +
CPU: AMD Ryzen 9 5950X 16-Core Processor
 +
 
 +
Titboard perft group:
 +
All tests completed with mean nps: 22290500
 +
 
 +
Pext perft group:
 +
All tests completed with mean nps: 40633688
 +
 
 +
Magic Bitboard perft group:
 +
All tests completed with mean nps: 37989088
 +
</pre>
 +
 
 +
<pre>
 +
CPU: Ryzen 5 5600x
 +
Titboard perft group:
 +
All tests completed with mean nps: 21250050
 +
 
 +
Pext perft group:
 +
All tests completed with mean nps: 36773955
 +
 
 +
Magic Bitboard perft group:
 +
All tests completed with mean nps: 34421651
 +
</pre>
 +
 
 +
=Forum Posts=
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623 Yet another new bitboard move generation method] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], September 22, 2006 » [[Move Generation]]
 +
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623&start=6 Re: Yet another new bitboard move generation method] by [[Harm Geert Muller]], [[Computer Chess Forums|Winboard Forum]], October 01, 2006 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=52861&start=8 Re: multi-dimensional piece/square tables] by Tony P., [[CCC]], January 28, 2020 » [[Piece-Square Tables]]</ref>
  
 
=References=
 
=References=
 
<references />
 
<references />
−
 
 
'''[[Sliding Piece Attacks|Up one level]]'''
 
'''[[Sliding Piece Attacks|Up one level]]'''

Latest revision as of 13:35, 20 September 2024

Home * Board Representation * Bitboards * Sliding Piece Attacks * Titboards

Titboards,
a bitboard-based move generation technique invented by Zach Wegner [1] and first implemented by Malik Tremain [2]. Titboards are based on an extension of bitboards to ternary boards, hence the name ("bit" means binary digit, "tit" mean ternary digit). Titboards are only used for move generation, not for any other purposes that typical bitboard attack-getters will be used for.

The idea of titboards is to eliminate bitscans. Typical bitboard move generation techniques generate a bitboard, intersect it with the set of allowable squares (empty or enemy-occupied), and then serialize that into a list of moves. Titboards take a bitboard occupancy for each side for just one rank, file, or diagonal, and convert them to ternary representations and add them together. This index can determine which squares can actually be moved to, instead of just attacked. It is used in a lookup table of 3^7=2187 entries per direction per square.

Titboards are not typically used (there is one known engine that implements them [2]). This is because they are currently slower than modern alternatives while being harder to implement. They require a large look-up table (~8.9 MB) and they work very differently from modern generation techniques likes Magic Bitboards, where they require each direction to be calculated individually {File, Rank, Diagonal, Anti-Diagonal}. For each direction they require the input of (square, us, them), as a pose to (square, occupied) which is more commonly used.

Speed

Testing shows that titboards have no speed advantage over magic bitboards on modern hardware, however, the gap seemingly narrows on older CPUs that offer less efficient bitscan operations. A full array of results can be found here[3]. 

CPU: AMD Ryzen 9 5950X 16-Core Processor

Titboard perft group:
All tests completed with mean nps: 22290500

Pext perft group:
All tests completed with mean nps: 40633688

Magic Bitboard perft group:
All tests completed with mean nps: 37989088

CPU: Ryzen 5 5600x
Titboard perft group:
All tests completed with mean nps: 21250050

Pext perft group:
All tests completed with mean nps: 36773955

Magic Bitboard perft group:
All tests completed with mean nps: 34421651

Forum Posts

Re: Yet another new bitboard move generation method by Harm Geert Muller, Winboard Forum, October 01, 2006 [4]

References

  1. ↑ Yet another new bitboard move generation method by Zach Wegner, Winboard Forum, September 22, 2006
  2. ↑ 2.0 2.1 TDFA - Titboard Engine by Malik Tremain, January 22, 2024
  3. ↑ TDFA - Perft result comparison
  4. ↑ Re: multi-dimensional piece/square tables by Tony P., CCC, January 28, 2020 » Piece-Square Tables

Up one level

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