Shakkia pelaavat tietokoneohjelmat yleensä laskevat eteenpäin siirtoja niin, että vuorotellen etsitään kummallekin pelaajalle parhaat siirrot, kun vasta pelaaja on tehnyt siirtonsa. Jokaisella syvyydellä valitaan se siirto, jonka jälkeen saadaan paras arvo saavutettavalle asemalle. Jos tämä arvo valitaan siten, että negatiivinen ääretön on mustan voitto ja positiivinen ääretön on valkean voitto ja nolla on tasapeli, niin tuota arvoa siis vuorotellen minimoidaan ja maksimoidaan, koska oletetaan, että sekä musta että valkea pyrkivät tekemään parhaat siirrot kussakin asemassa. Tämä on kuitenkin äärimmäisen työlästä, koska mahdollisia siirtoja keskimäärin noin 35 ja tutkittavien asemien määrä kasvaa eksponentiaalisesti, koska jokaiselle noista 35:stä siirrosta etsitään 35 vastinetta ja niille edelleen vastineet, kunnes halutaan katkaista haku. Tällöin tutkittavien asemien määrä kasvaa nopeasti yli parhaankin supertietokoneen suorituskyvyn, jos tulos pitää saada parin minuutin sisään.
Alfa-beta-haussa ideana on, että jos vastustajalle löytyy siirto, jonka jälkeen asema on meille huonompi kuin tähän mennessä löydetty paras asema, niin muita vastustajan siirtoja tuossa asemassa ei tarvitse tutkia, koska emme kuitenkaan pelaa siirtoa, joka johtaa tuohon asemaan, koska meillä on parempikin vaihtoehto. Tämä karsii laskettavaa huomattavasti, koska jokaista vaihtoehtoa ei tutkita. Lisäksi tämä menetelmä on teoreettisesti korrekti, koska lopputulos on aivan sama kuin täydessä haussa.
Paras hyöty alfa-beta-hausta saadaan, jos tutkittavat siirrot on järjestetty parhaasta huonoimpaan, jolloin karsiminen tapahtuu nopeasti, ja hakupuu on minimaalinen. Käytännössä on kuitenkin mahdotonta etukäteen tietää, mikä on paras siirto kussakin asemassa ensin tutkimatta siirtoja. Tämän vuoksi on kehitetty erilaisia heuristiikkoja siirtojen järjestämiseen.
Pseudokoodina alfa-beta-haku on seuraavanlainen:
tutki(asema, syvyys, alfa, beta) if syvyys == 0 then return asema.staattinenArvio() parasTulos = - ääretön siirrot = asema.tuotaSiirrot() for i = 1 to siirrot.pituus() asema.tee( siirrot[i] ) tulos = - tutki(asema, syvyys - 1, - beta, - alfa) asema.peruuta( siirrot[i] ) if tulos > parasTulos then parasTulos = tulos if parasTulos > alfa then alfa = parasTulos if alfa >= beta return alfa return parasTulos
Tätä algoritmiä kutsuvassa ohjelmassa asetetaan alfa negatiiviseksi äärettömäksi ja beta positiiviseksi äärettömäksi. Nämä arvot edustavat rajoja, joiden välillä aseman arvo sijaitsee. Tämä väli eli ikkuna voidaan asettaa myös muulla tavoin, jos on olemassa riittävästi tietoa. Syvyys asetetaan halutuksi kiinteäksi arvoksi.
Päämuunnelman tutkimisessa otetaan lähtökohdaksi se, että paras siirto tutkitaan ensimmäisenä. Oletukseen perustuen muut siirrot tutkitaan minimaalisella alfa-beta-haun ikkunalla [-alfa-1, alfa] , jolloin päästään paljon nopeampaan hakuun, koska paljon hakupuun haaroja karsitaan pois pienestä ikkunasta johtuen. Kuitenkin, jos alkuperäinen oletuksemme osoittautui vääräksi, tapahtuu nopea karsiutuminen, ja siirto tutkitaan uudestaan normaalilla ikkunalla. Yleensä uudestaan tutkimiseen käytetty aika voitetaan moninkertaisesti takaisin pienemmällä ikkunalla suoritetuissa onnistuneissa hauissa. Tietysti siirtojen esijärjestäminen on tässä vielä tärkeämpää kuin pelkässä alfa-beta-haussa.
Tässä on päämuunnelman tutkimisen pseudokoodi:
tutki(asema, syvyys, alfa, beta) if syvyys == 0 then return asema.staattinenArvio() parasTulos = - ääretön siirrot = asema.tuotaSiirrot() asema.tee( siirrot[0] ) alfa = parasTulos = -tutki(asema, syvyys - 1, - beta, - alfa) asema.peruuta( siirrot[0] ) for i = 2 to siirrot.pituus() asema.tee( siirrot[i] ) tulos = - tutki(asema, syvyys - 1, - alfa - 1, - alfa) if tulos > parasTulos then if tulos > alfa ja tulos < beta then parasTulos = - tutki(asema, syvyys - 1, - beta, - tulos) else parasTulos = tulos asema.peruuta( siirrot[i] ) if parasTulos > alfa then alfa = parasTulos if alfa >= beta return alfa return parasTulos
Tietysti samaa idea voidaan vielä kehitellä, niin että jo hakupuun juuressa käytetään kapeaa ikkunaa ja tutkitaan uudestaan samoin kuin tässä, jos haku epäonnistuu.
Iteratiivisen syventämisen ideana on käyttää siirtoa varten varattu aika täysin hyväksi. Lisäksi sen avulla voidaan varmistaa, että haku saadaan valmiiksi ainakin jollekin syvyydelle asti. Iteratiivisessa syventämisessä aloitetaan haku hakemalla ensin esimerkiksi 3 puolisiirtoa syvälle ja kasvattamalla syvyyttä ja hakemalla uudestaan, kunnes aika on käytetty.
Se, että ensimmäiset haut ovat näennäisesti turhia, ei tuo paljonkaan lisäkuormaa laskentaa, koska hakuun käytetty aika kasvaa eksponentiaalisesti syvyyden mukana, joten matalammat haut kestävät vain murto-osan viimeisestä hausta. Hyvänä puolena on, että jos ei tiedetä etukäteen tietokoneen tehoja, niin haku suoritetaan optimaalisesti.
Hiukan kehittyneempi idea on tehdä haun sisäinen iteratiivinen syventäminen siirtojärjestyksen parantamiseksi. Tällöin haetaan hakualgoritmissa syvyydellä, joka on kaksi puolisiirtoa matalampi kuin hakusyvyys ja käytetään tulosta parhaan siirron löytämiseksi päämuunnelma hakua varten.
Nollasiirron käyttö on yksi viimeisimpiä kehityksiä shakkiohjelmien alalla. Ihmiset ovat käyttäneet nollasiirtoa niin kauan kuin shakkia on pelattu. Ihmiselle on normaalia ajatella, että jos en nyt siirtäisi, niin mitä vastustaja tekisi. Tällaisen ajatuksen hyödyntäminen tietokoneshakissa vaikuttaisi hiukan vaikealta, koska tietokoneohjelma ei voi suoraan hyödyntää vastustajan uhkien löytämistä.
Nollasiirtoa voidaan kuitenkin käyttää karsimaan pois hakupuun osia, jotka vaikuttavat huonoilta. Tämä tehdään niin, että annetaan pelaajan olla tekemättä siirtoa ja antaa vastustajan siirtää näin ollen kaksi kertaa. Jos tällöin saatu asema on edelleen hyvä meille, täytyy aseman olla todella hyvä. Näin ollen vastustaja tuskin olisi alunperin tehnyt siirtoa, joka johtaisi tällaiseen asemaan. Tätä voidaan käyttää hyväksi jättämällä tuo haara tutkimatta.
Nollasiirron käyttäminen suoraan hakualgoritmissa ei ole teoreettisesti oikein, joten se voi antaa vääriä tuloksia erityisesti siirtopakko tilanteissa, joissa siirtämättä jättäminen olisi paras vaihtoehto. Kuitenkaan se ei ole laillista, joten saatu tulos on väärä. Nollasiirtoa ei siis pitäisi käyttää ainakaan loppupeleissä eikä silloin, kun matti on lähellä. Toinen mahdollisuus on käyttää nollasiirtoa vain parhaan siirtokanditaatin löytämiseen, jolloin mitään ongelmia ei synny, koska varsinainen haku suoritetaan normaalisti.
Turhuuden karsinnassa ajatuksena on katkaista haku jo ennen laskentahorisonttia, jos näyttää siltä, että kyseisestä hakupuun haarasta ei löydy hyviä asemia. Tämä on teoreettisesti oikein vain, jos on määriteltävissä suurin mahdollinen asemallinen parannus, joka voidaan yhdellä siirrolla tehdä. Tällöin, jos tulos, johon on lisätty paras mahdollinen asemallinen parannus, on viimeistä edellisessä syvyydessä huonompi kuin haun antama alaraja, voidaan hakulopettaa siihen ja palauttaa staattinen arvio.
Tällainen karsiminen saattaa nopeuttaa hakua paljon, koska joka tapauksessa eniten aikaa menee hakupuun solmuissa, jotka ovat laskentahorisontissa. On myös mahdollista, että turhuuden karsinnassa käytetään pienempää väliä kuin parasta mahdolista asemallista parannusta, mutta tällöin saatetaan tehdä taktisesti virheellisiä siirtoja. Toisaalta, jos se, että viimeistä edellisessä syvyydessä on suoritettu karsintaa, antaakin aikaa suorittaa uusi haku myös seuraavassa syvyydessä, niin tulos itseasiassa paranee.