Ich würde das Veränderungspotential nicht verkleinern, sondern vielleicht mit einer gaus'schen Verteilung arbeiten, sodaß kleine Veränderungen wesentlich häufiger vorkommen, als große...
Dann wäre dein Problem der lokalen Maxima auch erledigt, denn irgendwann hüpft der Algorithmus aus einem lokalen Maximum wieder raus, nämlich genau dann, wenn zufällig eine ziemlich große Veränderung eintritt (und diese dann besser ist).
Eine weitere Vorgehensweise wäre noch, den Baum bis zu einer Tiefe X zu traversieren. Dabei sollten jedoch die einzelnen Stände gespeichert werden. Bevor nun eine Konstellation weiter untersucht wird, prüfst Du, ob diese Matrix, bzw. eine der Rotationen oder Spiegelungen nicht schon vorher analysiert wurde. Wenn ja, kannst Du dir weitere Arbeit schenken. Das dürfte den Aufwand schon mal drastisch senken, denn es gibt ja pro Matrix 4 Rotationen, 2 Spiegelungen und alle Kombinationen davon.
Vielleicht kannst Du mit dem Baumtraversieren zunächst die 'beste' Lösung (für max X Züge) finden und setzt die Baumtraversierung bei dem 'best of X' wieder an, wobei Du die bereits besuchten Stellungen natürlich nicht verwirfst, denn sonst würdest Du ja auch wieder rückwärts suchen, also in die Richtung, aus der Du gerade gekommen bist.
So könntest Du dich langsam zu einem brauchbaren Ergebnis hangeln.
Leider wird der Index recht groß, aber wozu hat man schließlich
RAM, Datenbanken und TByte-Platten.