| dbpprop:abstract
|
- Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games. It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes.
- Die Alpha-Beta-Suche, auch Alpha-Beta-Cut oder Alpha-Beta-Pruning genannt, ist eine optimierte Variante des Minimax-Suchverfahrens, also eines Algorithmus zur Bestimmung eines optimalen Zuges bei Spielen mit zwei gegnerischen Parteien. Während der Suche werden zwei Werte Alpha und Beta aktualisiert, die angeben, welches Ergebnis die Spieler bei optimaler Spielweise erzielen können. Mit Hilfe dieser Werte kann entschieden werden, welche Teile des Suchbaumes nicht untersucht werden müssen, weil sie das Ergebnis der Problemlösung nicht beeinflussen können. Die einfache (nicht optimierte) Alpha-Beta-Suche liefert exakt dasselbe Ergebnis wie die Minimax-Suche.
- Alfa-beta ořezávání (angl. alpha-beta pruning) je vylepšení algoritmu minimax, které v průměrném případě zrychluje jeho běh. Je založeno na pozorování, že pokud právě zpracovávaný půltah už nemůže obstát v konkurenci s jiným, nemusíme dál prohledávat jeho důsledky. Metoda byla pojmenována alfa-beta, protože v ní rozšiřujeme původní minimaxový algoritmus o dvě další hodnoty alfa a beta, které nám určují potřebné meze. Účinnost ořezání nepotřebných větví lze zvýšit vhodnou volbou pořadí, v němž jsou procházeny. Nejvýhodnější je projít nejprve ty větve, které by měly dát podle nějakého rychlého (ve srovnání s procházení kompletním minimaxem) odhadu nejlepší výsledky. Další možností, jak odlišit lepší tahy od horších je tzv. kaskádová metoda (anglicky iterative deepening depth-first search), která spočívá v tom, že pokud bychom chtěli prohládavat do hloubky n půltahů, budeme algoritmus postupně pouštět na hloubku 1, 2, ... , n půltahů a v každé další iteraci budeme na tahy pouštět vylepšený minimax v tom pořadí, v jakém nám předchozí iterace ohodnotila tahy. Pokud budeme mít při volbě pořadí procházení tahů smůlu, alfa-beta ořezávání běh nezrychlí vůbec.
- La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go. Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D. J Edwards y T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth y Ronald W. Moore El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.
- L'élagage alpha-beta est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme MinMax. L'algorithme MinMax effectue en effet une exploration complète de l'arbre de recherche jusqu'à un niveau donné, alors qu'une exploration partielle de l'arbre est généralement suffisante : lors de l'exploration, il n'est pas nécessaire d'examiner les sous-arbres qui conduisent à des configurations dont la valeur ne contribuera sûrement pas au calcul du gain à la racine de l'arbre. L’élagage αβ nous permet de réaliser ceci. Plus simplement, l'élagage αβ évite d'évaluer des nœuds de l'arbre de recherche dont on est sûr que leur qualité sera inférieure à un nœud déjà évalué. L'élagage αβ permet d'optimiser grandement l'algorithme MinMax sans en modifier le résultat. Il est très utilisé dans le cas des jeux à 2 joueurs, comme par exemple les échecs ou le go.
- Az alfa-béta vágás egy játékelméleti keresési algoritmus, amellyel csökkenthető a játékfában lévő kiértékelendő állások száma a minimax algoritmus által szükséges kiértékelésekhez képest. Az algoritmust az olyan kétszemélyes játékoknál mint például az amőba, sakk, go stb. lehet eredményesen használni gépi játékos készítésére. Az algoritmus alapötlete azon nyugszik, hogy ha a játékfában az éppen vizsgált lépésünkre az ellenfélnek van egy olyan erős lépése ami miatt ezt a lépést úgyse választanánk (mivel a vizsgálat korábbi részéből már van jobb választásunk), akkor az erre a lépésre az ellenfél által adható további lépéseket nem szükséges megvizsgálni. Az algoritmusban ezen részjátékfák fölösleges vizsgálatának kihagyását hívjuk alfa illetve béta vágásnak. A minimax algoritmus ilyetén történő optimalizálása nem változtatja meg a kapott végeredményt.
- La potatura alfa-beta è un algoritmo di ricerca che riduce drasticamente il numero di nodi da valutare nell'albero di ricerca dell'algoritmo minimax. Viene comunemente usata nei programmi di gioco automatico per computer, per giochi a turni a due o più giocatori, e consiste nel terminare la valutazione di una possibile mossa non appena viene dimostrato che è comunque peggiore di una già valutata in precedenza: è una ottimizzazione sicura, che non modifica il risultato finale dell'algoritmo a cui viene applicata.
- アルファ・ベータ法（— ほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。ゲーム木において、枝刈りを行うことでミニマックス法よりも評価するノード数を抑えている。アルファ・ベータ法はミニマックス法とは別のアルゴリズムというより、それを改良したものと考えられる。
- Algorytm Alfa-Beta – algorytm przeszukujący, redukujący liczbę węzłów, które muszą być rozwiązywane w drzewach przeszukujących przez algorytm min-max. Jest to przeszukiwanie wykorzystywane w grach dwuosobowych, takich jak kółko i krzyżyk, szachy, go. Warunkiem stopu jest znalezienie przynajmniej jednego rozwiązania czyniącego obecnie badaną opcję ruchu gorszą od poprzednio zbadanych opcji. Wybranie takiej opcji ruchu nie przyniosłoby korzyści graczowi ruszającemu się, dlatego też nie ma potrzeby przeszukiwać dalej gałęzi drzewa tej opcji. Ta technika pozwala zaoszczędzić czas poszukiwania bez zmiany wyniku działania algorytmu.
- A poda α-β é uma variação do algoritmo minimax que visa reduzir o número de nós que são avaliados na árvore de busca. É uma busca adversarista comummente utilizada na implementação de jogadores automáticos em jogos de dois jogadores. Ele pára completamente de avaliar um movimento quando ele encontra, de maneira comprovada, um movimento cujo valor associado seja pior do que um movimento previamente examinado. Sendo assim, os movimentos posteriores não necessitam ser avaliados. A poda alfa beta não altera o resultado final da avaliação de uma sub-árvore e a sua vantagem está no fato de que, em árvores de busca com um fator de ramificação muito grande, a utilização de memória será significativamente reduzida.
- Альфа-бета відсічення — алгоритм пошуку, що зменшує кількість вузлів, які необхідно оцінити в дереві пошуку мінімаксного алгоритму і при цьому отримати дозволяє отримати ідентичний результат. Цей алгоритм використовується в програмуванні настільних ігор, де грають два гравці. Використовуючи цей алгоритм, програма повністю припиняє оцінювати хід, якщо знайшла доказ, що цей хід гірший, ніж оцінений раніше. Такі ходи не потребують подальшої оцінки.
|
| rdfs:comment
|
- Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games. It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further.
- Die Alpha-Beta-Suche, auch Alpha-Beta-Cut oder Alpha-Beta-Pruning genannt, ist eine optimierte Variante des Minimax-Suchverfahrens, also eines Algorithmus zur Bestimmung eines optimalen Zuges bei Spielen mit zwei gegnerischen Parteien. Während der Suche werden zwei Werte Alpha und Beta aktualisiert, die angeben, welches Ergebnis die Spieler bei optimaler Spielweise erzielen können.
- Alfa-beta ořezávání (angl. alpha-beta pruning) je vylepšení algoritmu minimax, které v průměrném případě zrychluje jeho běh. Je založeno na pozorování, že pokud právě zpracovávaný půltah už nemůže obstát v konkurenci s jiným, nemusíme dál prohledávat jeho důsledky. Metoda byla pojmenována alfa-beta, protože v ní rozšiřujeme původní minimaxový algoritmus o dvě další hodnoty alfa a beta, které nám určují potřebné meze.
- La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go. Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D. J Edwards y T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth y Ronald W.
- L'élagage alpha-beta est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme MinMax.
- Az alfa-béta vágás egy játékelméleti keresési algoritmus, amellyel csökkenthető a játékfában lévő kiértékelendő állások száma a minimax algoritmus által szükséges kiértékelésekhez képest. Az algoritmust az olyan kétszemélyes játékoknál mint például az amőba, sakk, go stb. lehet eredményesen használni gépi játékos készítésére.
- La potatura alfa-beta è un algoritmo di ricerca che riduce drasticamente il numero di nodi da valutare nell'albero di ricerca dell'algoritmo minimax.
- アルファ・ベータ法（— ほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。ゲーム木において、枝刈りを行うことでミニマックス法よりも評価するノード数を抑えている。アルファ・ベータ法はミニマックス法とは別のアルゴリズムというより、それを改良したものと考えられる。
- Algorytm Alfa-Beta – algorytm przeszukujący, redukujący liczbę węzłów, które muszą być rozwiązywane w drzewach przeszukujących przez algorytm min-max. Jest to przeszukiwanie wykorzystywane w grach dwuosobowych, takich jak kółko i krzyżyk, szachy, go. Warunkiem stopu jest znalezienie przynajmniej jednego rozwiązania czyniącego obecnie badaną opcję ruchu gorszą od poprzednio zbadanych opcji.
- A poda α-β é uma variação do algoritmo minimax que visa reduzir o número de nós que são avaliados na árvore de busca. É uma busca adversarista comummente utilizada na implementação de jogadores automáticos em jogos de dois jogadores. Ele pára completamente de avaliar um movimento quando ele encontra, de maneira comprovada, um movimento cujo valor associado seja pior do que um movimento previamente examinado. Sendo assim, os movimentos posteriores não necessitam ser avaliados.
- Альфа-бета відсічення — алгоритм пошуку, що зменшує кількість вузлів, які необхідно оцінити в дереві пошуку мінімаксного алгоритму і при цьому отримати дозволяє отримати ідентичний результат.
|
![[RDF Data]](/statics/sw-cube.png)
