Tietokoneshakki / Siirtojärjestyksen parantaminen

Hyödyt alfa-beta-karsinnan kanssa

Jotta alfa-beta-karsinnasta olisi todellista hyötyä, täytyy siirtojen tutkimisjärjestys olla sopiva. Jos tutkittasiin siirrto heikoimmasta vahvimpaan, ei karsimista tapahtuisi, koska ei olisi rajaa, jota vasten karsia. Toisaalta päinvastainen järjestys olisi optimaalinen, koska ensimmäisesstä haarasta saatu tulos aiheuttaisi karsintaa kaikissa muissa. Tällöin haku olisi moninkertaisesti nopeampi. Käytännössä tällöin eksponentiaalisesta kasvusta johtuen käytetty aikaa putoaa neliöjuureensa ja täten haku voidaan suorittaa kaksi kertaa syvemmälle.

Mahdollisesti siirtojen järjestämiseen kuluva aika kasvattaa hakuaikaa lineaarisesti, mutta jos vastaavasti saatu hyöty takaa eksponentiaalisen pienentymisen, on kokonaisuutena saatu hyöty riittävän suuri, jotta tämä kannattaisi. Lisäksi jos alfa-beta-hakua kehitetään esimerkiksi päämuunnelman hauksi, saatu hyöty on vielä suurempi.

Arvokkain lyöty - arvottomin lyöjä

Lyöntien järjestäminen on hiukan helpompaa kuin muiden siirtojen. Ne voidaan järjestää sen mukaan kuinka arvokkaita löydyt nappulat ja lyöjät ovat. Tämä perustuu siihen, että on todennäköisempää, että siirto, joka lyö arvokkaamman nappulan on parempi kuin siirto, joka lyö vähemmän arvokkaan nappulan, koska sillä saadaan enemmän materiaalia. Toisaalta lyövän nappulan arvokin vaikuttaa asiaan, sillä jos vastustaja pystyy heti lyömään takaisin, niin materiaalieroksi jää lyödyn nappulan ja lyövän nappulan erotus. Siirrot voidaan siis järjestää tuon erotuksen mukaan.

Historiaheuristiikka

Historiaheuristiikka käyttää hyväkseen sitä tietoa, että jos siirto on aiemmin ollut hyvä, on se sitä jatkossakin. Ja vaikkei olisikaan, niin on se ainakin tutkimisen arvoinen. Niinpä siirrosta voidaan pitää yllä taulukkoa, joka on indeksoitu lähtö- ja kohderuutujen mukaan. Tämän taulukon arvoja kasvatetaan aina, kun jokin siirto aiheuttaa beta-karsinnan. Tällöin siirto aiheuttanee beta-karsinnan muissakin tapauksissa. Siirtojen järjestämisessä käytetään sitten tuon taulukon arvoja siirtojen järjestämiseen. Historiaheuristiikan taulukko on nollattava riittävän usein, jotta sen sisälty pysyisi koherenttina. Sopiva tilanne on esimerkiksi sen jälkeen, kun varsinainen siirto on tehty.

Tappajasiirtoheuristiikka

Tappajasiirtoheuristiikka muistuttaa historiaheuristiikkaa siinä, että senkin tarkoitus on hyödyntää aiemmin hyviä siirtoja. Tappajasiirtoheurisitiikassa on kuitenkin jokaista etsintäsyvyyden askelta kohti omat taulukkonsa. Lisäksi tappajasiirtoja voidaan pitää muistissa useita. Tämä heuristiikka sopii erityisesti päämuunnelman tutkimiseen, koska siinä paras siirtovaihtoehto löydetään nopeasti.


Pääsivulle