Жасанды интеллекттегі ойын әлсіздігі: "көлденең эффект". Теңіздің шегінен асып, қате бағалауға алып келетін шектеулі іздеу тереңдігі. Ойын стратегиясы, AI.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Ойын ойнаудағы жасанды интеллектінің әлсіздігі
Weakness of game playing artificial intelligence
Горизонт эффектісі, сондай-ақ горизонт проблемасы деп те аталады, – жасанды интеллектте кездесетін мәселе. Көптеген ойындарда мүмкін болатын күйлер немесе позициялардың саны тым көп болғандықтан, компьютерлер олардың шағын бөлігін ғана, әдетте ойын ағашының бірнеше қабатын ғана қарастыра алады. Осылайша, белгілі бір тереңдікте іздейтін компьютер зиянды қадам жасауы мүмкін, бірақ бұл әсер көрінбейді, себебі компьютер оның бағалау функциясы нақты бағаны көрсететін тереңдікке дейін іздемейді (яғни, оның «көгізігінен» тыс). Ірі ойын ағашын бағалау кезінде альфа-бета кесумен minimax сияқты техникаларды қолданғанда, есептеу мүмкіндігі үшін іздеу тереңдігі шектеледі. Дегенмен, жартылай ағашты бағалау қате нәтиже беруі мүмкін. Егер іздеу тереңдігінің «көкжиегінен» кейін маңызды өзгеріс орын алса, есептеу құрылғысы осы горизонт эффектісіне ұшырайды. 1973 жылы Ханс Берлинер өзі және басқа зерттеушілер байқаған осы құбылысты «Горизонт эффектісі» деп атады. Ол осы эффектіні екіге бөлді: Теріс горизонт эффектісі «тиімсіздікке алып келетін, қашуға болмайтын салдарды кешіктіруге немесе қол жеткізе алмайтын нәрсені қол жеткізілгендей көрсетуге» себеп болады. Ал «көпшілік назардан тыс қалған» Оң горизонт эффектісі үшін «бағдарлама қарсыласына ыңғайлы уақытта, көбінесе тиімдірек формада қолдануға болатын салдарды тым ерте ұстап алады». Ашкөз алгоритмдер көбінесе горизонт эффектісінен зардап шегеді. Горизонт эффектісін азайту үшін іздеу алгоритмін тыныштандыру іздеуімен кеңейтуге болады. Бұл іздеу алгоритміне ойын күйіне маңызды әсер ететін, мысалы, шахматтағы тұтқындау сияқты белгілі бір қимылдар класы үшін өзінің «көкжиегінен» тысқары қарауға мүмкіндік береді. Жапырақ түйіндері үшін бағалау функциясын қайта жазу және/немесе көбірек түйіндерді талдау көптеген горизонт эффектісі мәселелерін шешеді.
The horizon effect, also known as the horizon problem, is a problem in artificial intelligence whereby, in many games, the number of possible states or positions is immense and computers can only feasibly search a small portion of them, typically a few plies down the game tree. Thus, for a computer searching only a fixed number of plies, there is a possibility that it will make a detrimental move, but the effect is not visible because the computer does not search to the depth at which its evaluation function reveals the true evaluation of the line (i. e., beyond its "horizon"). When evaluating a large game tree using techniques such as minimax with alpha beta pruning, search depth is limited for feasibility reasons. However, evaluating a partial tree may give a misleading result. When a significant change exists just over the horizon of the search depth, the computational device falls victim to the horizon effect. In 1973 Hans Berliner named this phenomenon, which he and other researchers had observed, the "Horizon Effect." He split the effect into two: the Negative Horizon Effect "results in creating diversions which ineffectively delay an unavoidable consequence or make an unachievable one appear achievable." For the "largely overlooked" Positive Horizon Effect, "the program grabs much too soon at a consequence that can be imposed on an opponent at leisure, frequently in a more effective form." Greedy algorithms tend to suffer from the horizon effect. The horizon effect can be mitigated by extending the search algorithm with a quiescence search. This gives the search algorithm ability to look beyond its horizon for a certain class of moves of major importance to the game state, such as captures in chess. Rewriting the evaluation function for leaf nodes and/or analyzing more nodes will solve many horizon effect problems.
Мысал
Мысалы, шахматта, егер компьютер ойын ағашын тек алты қадамға дейін қарастырса және қазіргі позициядан патшайым алтыншы қадамда жоғалатынын анықтаса; сондай-ақ, іздеу тереңдігінде мұнараны құрбан ету мүмкіндігі бар бір қозғалыс болса, онда патшайымның жоғалуы сегізінші қадамға ығыстырылады. Бұл, әрине, патшайымды құрбан етуден де нашар қозғалыс, себебі ол патшайым мен мұнараның екеуін де жоғалтуға алып келеді. Дегенмен, патшайымның жоғалуы іздеу шегінен тысқары жылғатылғандықтан, ол іздеу барысында табылмайды және бағаланбайды. Мұнараны жоғалту патшайымды жоғалтудан жақсырақ көрінеді, сондықтан құрбандық ең жақсы нұсқа ретінде ұсынылады, ал патшайымды құрбан етуді кейінге қалдыру, шын мәнінде, компьютердің позициясын нашарлатады.
For example, in chess, assume a situation where the computer only searches the game tree to six plies and from the current position determines that the queen is lost in the sixth ply; and suppose there is a move in the search depth where it may sacrifice a rook, and the loss of the queen is pushed to the eighth ply. This is, of course, a worse move than sacrificing the queen because it leads to losing both a queen and a rook. However, because the loss of the queen was pushed over the horizon of search, it is not discovered and evaluated by the search. Losing the rook seems to be better than losing the queen, so the sacrifice is returned as the best option whereas delaying the sacrifice of the queen has in fact additionally weakened the computer's position.