NP-Vollständigkeit des Hashtabellen-Packproblems für Magic Bitboards im Schach

Dieser Artikel beweist die starke NP-Vollständigkeit des Hashtabellen-Packproblems, das bei der Optimierung von Magic Bitboards im Schach auftritt. Der Autor reduziert das 3-Partitionierungsproblem auf das Hashtabellen-Packproblem und zeigt, dass das Finden einer minimalgroßen Packung rechnerisch unlösbar ist. Dies bedeutet, dass in der Praxis Heuristiken anstelle der Suche nach optimalen Lösungen verwendet werden müssen. Dies hat erhebliche Auswirkungen auf die Optimierung der Leistung von Schach-Engines, da Magic Bitboards für die effiziente Erzeugung von Zügen unerlässlich sind.