Difference between revisions of "Space-Time Tradeoff"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Programming * Space-Time Tradeoff''' FILE:vortex1_med.jpg|border|right|thumb|link=http://www.physorg.com/news8256.html|Space-time Vortex <ref>[h...") |
GerdIsenberg (talk | contribs) |
||
| (10 intermediate revisions by the same user not shown) | |||
| Line 10: | Line 10: | ||
* [[BitScan]] | * [[BitScan]] | ||
* [[Distance]] | * [[Distance]] | ||
| + | * [[Encoding Moves]] | ||
* [[Endgame Bitbases]] | * [[Endgame Bitbases]] | ||
* [[Endgame Tablebases]] | * [[Endgame Tablebases]] | ||
| Line 22: | Line 23: | ||
* [[Rotated Bitboards]] | * [[Rotated Bitboards]] | ||
* [[Table-driven Move Generation]] | * [[Table-driven Move Generation]] | ||
| − | * [[The | + | * [[The Switch Approach]] |
* [[Transposition Table]] | * [[Transposition Table]] | ||
| Line 37: | Line 38: | ||
=Publications= | =Publications= | ||
| − | * [https://en. | + | * [https://en.everybodywiki.com/Burton_Howard_Bloom Burton H. Bloom] ('''1970'''). ''[https://dl.acm.org/doi/10.1145/362686.362692 Space/time trade-offs in hash coding with allowable errors]''. [[ACM#Communications|Communications of the ACM]], Vol. 13, No. 7 <ref>[https://en.wikipedia.org/wiki/Bloom_filter Bloom filter from Wikipedia]</ref> |
| − | * [[Albert Zobrist]] | + | * [[Albert Zobrist]], [[Frederic Roy Carlson]] ('''1977'''). ''Detection of Combined Occurrences''. [[ACM#Communications|Communications of the ACM]], Vol. 20, No. 1 |
| + | |||
| + | =Forum Posts= | ||
| + | * [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=73273 Stockfish and latest +6 ELO patch!] by [[Jouni Uski]], [[CCC]], March 05, 2020 » [[Distance]], [[Stockfish]] <ref>[https://github.com/official-stockfish/Stockfish/commit/5a7b45eac9dedbf7ebc61d9deb4dd934058d1ca1#diff-4cd6bcdb505b124d7bdc612c4789dc26L57-R59 Use equations for PushAway and PushClose · official-stockfish/Stockfish@5a7b45e · GitHub]</ref> | ||
| + | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73319 Removing Large Arrays] by Deberger, [[CCC]], March 10, 2020 | ||
=External Links= | =External Links= | ||
| Line 62: | Line 67: | ||
* [https://en.wikipedia.org/wiki/Art_of_memory Art of memory from Wikipedia] | * [https://en.wikipedia.org/wiki/Art_of_memory Art of memory from Wikipedia] | ||
* [https://en.wikipedia.org/wiki/Eureka:_A_Prose_Poem Eureka: A Prose Poem from Wikipedia] | * [https://en.wikipedia.org/wiki/Eureka:_A_Prose_Poem Eureka: A Prose Poem from Wikipedia] | ||
| − | * [[ | + | * [[:Category:Time in Space|Time in Space]] - God Bless the Child, [https://de.wikipedia.org/wiki/Domicil Domicil], [https://en.wikipedia.org/wiki/Dortmund Dortmund], February 3, 2017, [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
| − | + | : In Memoriam [https://de.wikipedia.org/wiki/Wolf_Escher Wolf Escher] | |
| − | : {{#evu:https://www.youtube.com/watch?v= | + | : {{#evu:https://www.youtube.com/watch?v=XGcaF8JHHDk|alignment=left|valignment=top}} |
=References= | =References= | ||
<references /> | <references /> | ||
| − | |||
'''[[Programming|Up one Level]]''' | '''[[Programming|Up one Level]]''' | ||
| + | [[Category:Time in Space]] | ||
Latest revision as of 23:41, 21 March 2020
Home * Programming * Space-Time Tradeoff
Space-time Vortex [1]
Space-Time Tradeoff refers to providing knowledge, information or data, where memory size competes with computation time. This tradeoff is a frequent issue in computer chess programming, for instance low level stuff to calculate or lookup single populated bitboards by square index, or a distance between two squares. Lookup tables are non-volatile tables or initialized once at program startup, various hash tables and caches. Space-time tradeoff is also an issue in determining (almost) perfect knowledge from interior node recognizers by retrograde analysis, that is the application of endgame bit- or tablebases and various compression techniques.
Contents
Space-Time Tradeoffs
There are multiple CPW pages where memory competes with computation:
- Bit by Square
- BitScan
- Distance
- Encoding Moves
- Endgame Bitbases
- Endgame Tablebases
- Hash Table
- Kindergarten Bitboards
- KPK
- Legality Test
- Magic Bitboards
- Manhattan-Distance
- Material Tables
- Population Count
- Rotated Bitboards
- Table-driven Move Generation
- The Switch Approach
- Transposition Table
See also
- Algorithms
- Best-First
- Data
- Depth-First
- Dispersion and Distortion
- Knowledge
- Learning
- Memory
- Sequential Logic
Publications
- Burton H. Bloom (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, Vol. 13, No. 7 [2]
- Albert Zobrist, Frederic Roy Carlson (1977). Detection of Combined Occurrences. Communications of the ACM, Vol. 20, No. 1
Forum Posts
- Stockfish and latest +6 ELO patch! by Jouni Uski, CCC, March 05, 2020 » Distance, Stockfish [3]
- Removing Large Arrays by Deberger, CCC, March 10, 2020
External Links
- Space-time tradeoff from Wikipedia
- Blum's speedup theorem from Wikipedia
- Algorithmic efficiency from Wikipedia
- Shannon entropy from Wikipedia
- Computer memory from Wikipedia
- Cache from Wikipedia
- Lookup table from Wikipedia
- Database from Wikipedia
- Memory management unit from Wikipedia
- Volatile memory from Wikipedia
- Non-volatile memory from Wikipedia
- Random-access memory from Wikipedia
- Read-only memory from Wikipedia
- Memory footprint from Wikipedia
- Moore's law from Wikipedia
- Computation, Memory, Nature, and Life - Is digital storage the secret of life? by John Walker
- Spacetime from Wikipedia
- Philosophy of space and time from Wikipedia
- Einstein Minkowski Space-Time Diagram
- Art of memory from Wikipedia
- Eureka: A Prose Poem from Wikipedia
- Time in Space - God Bless the Child, Domicil, Dortmund, February 3, 2017, YouTube Video
- In Memoriam Wolf Escher
