Horisont effekt
Horisonteffekten , även känd som horisontproblemet , är ett problem inom artificiell intelligens där , i många spel, antalet möjliga tillstånd eller positioner är enormt och datorer bara kan söka efter en liten del av dem, vanligtvis ett fåtal lager nedåt. spelträd . Således, för en dator som bara söker efter fem lager, finns det en möjlighet att den kommer att göra ett skadligt drag, men effekten är inte synlig eftersom datorn inte söker till djupet av felet (dvs. bortom dess "horisont" ) .
När man utvärderar ett stort viltträd med tekniker som minimax med alfa-beta-beskärning är sökdjupet begränsat av genomförbarhetsskäl. Att utvärdera ett delträd kan dock ge ett missvisande resultat. När en betydande förändring finns strax över horisonten av sökdjupet, faller beräkningsenheten offer för horisonteffekten.
1973 kallade Hans Berliner detta fenomen, som han och andra forskare hade observerat, för "horisonteffekten". Han delade upp effekten i två: den negativa horisonteffekten "resulterar i att skapa avledningar som ineffektivt fördröjer en oundviklig konsekvens eller får en ouppnåelig att framstå som möjlig." För den "till stor del förbisedda" Positiva Horisonteffekten, "griper programmet alldeles för tidigt efter en konsekvens som kan påtvingas en motståndare på fritiden, ofta i en mer effektiv form."
Giriga algoritmer tenderar att drabbas av horisonteffekten.
Horisonteffekten kan mildras genom att utöka sökalgoritmen med en vilosökning . Detta ger sökalgoritmen möjlighet att se bortom sin horisont efter en viss klass av drag av stor betydelse för speltillståndet, såsom fångster i schack .
Att skriva om utvärderingsfunktionen för lövnoder och/eller analysera fler noder kommer att lösa många horisonteffektproblem.
Exempel
Till exempel, i schack , anta en situation där datorn bara söker igenom spelträdet till sex lag och från den aktuella positionen avgör att damen är förlorad i det sjätte lagret; och anta att det finns ett drag i sökdjupet där den kan offra ett torn, och förlusten av drottningen skjuts till det åttonde lagret. Detta är naturligtvis ett sämre drag än att offra drottningen eftersom det leder till att man förlorar både en dam och ett torn. Men eftersom förlusten av drottningen sköts över sökandets horisont, upptäcks och utvärderas den inte av sökningen. Att förlora tornet verkar vara bättre än att förlora drottningen, så offret returneras som det bästa alternativet, medan att försena drottningens offer faktiskt ytterligare har försvagat datorns position.
Se även
- Russell, Stuart J .; Norvig, Peter (2003), Artificiell intelligens: A Modern Approach (2:a upplagan), Upper Saddle River, New Jersey: Prentice Hall, sid. 174, ISBN 0-13-790395-2
externa länkar
- Horisonteffekt vid schackprogrammering WIKI (CPW)