Space-Time Tradeoff

Home * Programming * Space-Time Tradeoff

Space-time Vortex

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.

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
• 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
• 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

References

Up one Level