Alfa-bèta-snoeiing

Alfa-bèta-snoeiing versnelt het zoekproces van een schaakengine, een programma dat zetten en antwoorden vergelijkt. Het zoekproces kan als een boom worden voorgesteld: elke knoop is een stelling en elke tak een legale zet. Zonder snoeiing zou het programma veel voortzettingen onderzoeken die uiteindelijk irrelevant blijken.

De methode houdt tijdens het zoeken twee grenzen bij. Alfa is het beste resultaat dat één partij langs het huidige pad al kan garanderen. Bèta is een grens die ontstaat door een alternatief dat de tegenstander al beschikbaar heeft. Zodra een voortzetting zo slecht is dat een rationele speler haar nooit zou kiezen, kan verder zoeken daarin de beslissing bij de hogere knoop niet veranderen.

De tak wordt gestopt vanwege een logische grens in de boom, niet alleen omdat een zet onaantrekkelijk lijkt. Bij dezelfde diepte en met dezelfde evaluaties aan de zoekgrens geeft alfa-bèta dezelfde keuze als een volledig zoekproces die veronderstelt dat beide partijen hun beste antwoorden spelen.

De besparing hangt sterk af van de zetvolgorde. Sterke zetten vroeg testen stelt eerder nuttige grenzen vast en laat meer takken stoppen zonder diepgaander onderzoek. Een evaluatiefunctie, die een numerieke schatting aan een stelling toekent, levert waarden waar het eindige zoekproces stopt.