La NP-complétude du problème d'emballage des tables de hachage pour les Magic Bitboards aux échecs

Cet article prouve la forte NP-complétude du problème d'emballage des tables de hachage rencontré lors de l'optimisation des Magic Bitboards aux échecs. L'auteur réduit le problème de la 3-partition au problème d'emballage des tables de hachage, démontrant qu'il est computaitonnellement intraitable de trouver un emballage de taille minimale. Cela implique que des heuristiques doivent être utilisées en pratique au lieu de chercher des solutions optimales. Ceci a des implications significatives pour l'optimisation des performances des moteurs d'échecs, car les Magic Bitboards sont cruciales pour une génération efficace des coups.