Alfa beta leikkaus

Alphabeta karsiminen on hakualgoritmi, joka pyrkii vähentämään minimimax-algoritmin avulla arvioimien solmujen määrää  hakupuussa . Suunniteltu vastakkaisiin peleihin ja käytetty konepeleihin ( tietokoneshakissa , tietokonepelissä ja muissa). Algoritmi perustuu ajatukseen, että hakupuun haaran arviointi voidaan lopettaa ennenaikaisesti (laskematta kaikkia arviointifunktion arvoja), jos havaitaan, että tämän haaran arviointifunktion arvo on joka tapauksessa huonompi kuin edelliselle haaralle laskettu. Alfa-beta-leikkaus on optimointi , koska se ei vaikuta algoritmin oikeellisuuteen.

Historia

Allen Newell ja Herbert Simon käyttivät sitä, mitä John McCarthy kutsui "likiarvoksi" [1] vuonna 1958, ja kirjoittivat, että alfa-beta-leikkaus " näyttää olevan keksitty toistuvasti " [2] . Arthur Samuel , Richards, Hart, Levin, Edwards ehdottivat itsenäisesti tämän algoritmin varhaisia ​​versioita [3] . McCarthy esitti samanlaisia ​​ajatuksia myös Dartmouthin seminaarissa vuonna 1956, ja sitten vuonna 1961 ehdotti ryhmälle MIT :n opiskelijoita , mukaan lukien Alan Kotok [4] , tutkimusta varten . Alexander Brudno löysi algoritmin itsenäisesti ja julkaisi tulokset vuonna 1963 [5] . Vuonna 1975 Donald Knuth ja Ronald Moore paransivat algoritmia lisäämällä "beta"-leikkauksen [6] [7] .

Minimax optimointi

Alfa-beta-leikkauksen etuna on itse asiassa se, että osa hakupuun alitason haaroista voidaan sulkea pois sen jälkeen, kun ainakin yksi tasohaaroista on tarkasteltu kokonaisuudessaan. Koska leikkaaminen tapahtuu kaikilla sisäkkäisillä tasoilla (paitsi viimeisellä), vaikutus voi olla varsin merkittävä. Menetelmän tehokkuuteen vaikuttaa merkittävästi vaihtoehtojen alustava lajittelu (ilman luettelointia tai luetteloimalla pienempään syvyyteen) - lajittelussa huomioidaan alussa "hyviä" vaihtoehtoja, sitä enemmän "huonoja" oksia voidaan leikata. pois ilman kattavaa analyysiä.

Muistiinpanot

1. ↑ McCarthy J. Ihmisen tason tekoäly on vaikeampaa kuin se näytti vuonna 1955 (LaTeX2HTML 27. marraskuuta 2006). Käyttöpäivä: 20. joulukuuta 2006. Arkistoitu alkuperäisestä 8. huhtikuuta 2012. (määrätön)
2. ↑ Newell A. , Simon HA Tietojenkäsittelytiede empiirisenä tutkimuksena: Symbols and Search  //  Communications of the ACM, Vol. 19, ei. 3: päiväkirja. - 1976 - maaliskuu. Arkistoitu alkuperäisestä 28. kesäkuuta 2007.
3. ↑ Richards DJ, Hart TP The Alpha-Beta Heuristic (AIM-030) . Massachusetts Institute of Technology (4. joulukuuta 1961 - 28. lokakuuta 1963). Haettu 21. joulukuuta 2006. Arkistoitu alkuperäisestä 8. huhtikuuta 2012. (määrätön)
4. ↑ Kotok A. MIT Artificial Intelligence Memo 41 (XHTML, 3. joulukuuta 2004). Haettu 1. heinäkuuta 2006. Arkistoitu alkuperäisestä 8. huhtikuuta 2012. (määrätön)
5. ↑ Marsland TA Computer Chess Methods (PDF) Encyclopedia of Artificial Intelligencesta / S. Shapiro (toimittaja) (PDF) 159-171. J. Wiley & Sons (toukokuu 1987). Haettu 21. joulukuuta 2006. Arkistoitu alkuperäisestä 8. huhtikuuta 2012. (määrätön)
6. ↑ Knuth DE, Moore RW An Analysis of Alpha-Beta  Pruning (uuspr.)  // Artificial Intelligence Voi. 6, ei. 4. - 1975. - S. 293-326 . , uusintapainos kirjan "Osa 9": Knuth DE Selected Papers on Analysis of Algorithms  (englanniksi) . — Stanford, Kalifornia: Kielen ja tiedon tutkimuksen keskus - CSLI Lecture Notes, no. 102, 2000. ISBN 1-57586-212-3 .
7. ↑ Abramson B. Control Strategies for Two-Player Games  (määrittelemätön)  // ACM Computing Surveys, Voi. 21, ei. 2. - 1989. - Kesäkuu ( nide 21 ). - S. 137 . - doi : 10.1145/66443.66444 . Arkistoitu alkuperäisestä 20. elokuuta 2008. Arkistoitu kopio (linkki ei saatavilla) . Haettu 25. lokakuuta 2009. Arkistoitu alkuperäisestä 20. elokuuta 2008. (määrätön)