| dbo:abstract
|
- تقييم ألفا - بيتا هي خوارزمية بحث تسعى إلى تقليل عدد الأحتمالات التي تقييمها بواسطة خوارزمية مينيكس في شجرة البحث الخاصة بها. وتستخدم بشكل شائع للعب الالعاب الذهنية (مثل الشطرنج، الداما، اكس او إلخ). وتتوقف عن البحث في الأحتمال إذا عُثِرَ على احتمال واحد على الأقل يثبت أن الحركة أسوأ من أحتمال وجد مسبقًا. مثل هذه التحركات لا تحتاج إلى مزيد من التقييم. تفحص الاحتمالات مثل شجرة المينيكس القياسية، ولكنها تقطع الأحتمالات التي تبدو سيئة بشكل واضح. (ar)
- 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. Z tohoto pohledu jde o algoritmus používající metodu větví a mezí, kde meze jsou dvě, každá pro jednoho hráče. Úč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 prohledávat 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. V průběhu algoritmu (mezi iteracemi i v rámci iterace) se takové informace o tazích ukládají do . 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. Naopak, při výběru optimálního tahu na začátku se dosažená hloubka prohledávání (při stejném čase) zdvojnásobí. (cs)
- 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. (de)
- Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Connect 4, etc.). It stops 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. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision. (en)
- 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, , , 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. (es)
- En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax. Il est utilisé dans des programmes informatiques qui jouent à des jeux à 2 joueurs, comme les échecs ou les dames[réf. souhaitée]. (fr)
- 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 (Tris, Go, Scacchi ecc.), 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. (it)
- 알파-베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화(미니맥스) 알고리즘을 적용할 때 평가(evaluate)하는 노드의 수를 줄이기 위한 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘이라고도 하며, 기계가 플레이하는 2인용 게임(틱택토, 체스, 바둑)에 주로 사용된다. 이 알고리즘은 이전에 평가한 노드보다 현재 평가하는 노드가 더 좋지 않을 가능성이 있으면 평가를 중단한다. 이 노드의 남은 형제(sibling) 노드와 모든 후손 노드는 가지치기되어 평가하지 않는다. 이 알고리즘을 일반적인 미니맥스에 적용하면 동일한 결과를 얻게 된다. 최종 결정에 영향을 미치지 않는 가지들을 쳐낼 뿐이다. (ko)
- アルファ・ベータ法（アルファ・ベータほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。 (ja)
- 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. (pl)
- Альфа-бета-отсечение (англ. alpha-beta pruning) — алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакса. Предназначен для антагонистических игр и используется для машинной игры (в компьютерных шахматах, компьютерном го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета-отсечение является оптимизацией, так как не влияет на корректность работы алгоритма. (ru)
- Альфа-бета відсічення — алгоритм пошуку, що зменшує кількість вузлів, які необхідно оцінити в дереві пошуку мінімаксного алгоритму і при цьому дозволяє отримати ідентичний результат. Цей алгоритм використовується в програмуванні настільних ігор, де грають два гравці (хрестики-нулики, шахи, ґо). Використовуючи цей алгоритм, програма повністю припиняє оцінювати хід, якщо знайшла доказ, що цей хід гірший, ніж оцінений раніше. Такі ходи не потребують подальшої оцінки. (uk)
- Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。 (zh)
|
| rdfs:comment
|
- تقييم ألفا - بيتا هي خوارزمية بحث تسعى إلى تقليل عدد الأحتمالات التي تقييمها بواسطة خوارزمية مينيكس في شجرة البحث الخاصة بها. وتستخدم بشكل شائع للعب الالعاب الذهنية (مثل الشطرنج، الداما، اكس او إلخ). وتتوقف عن البحث في الأحتمال إذا عُثِرَ على احتمال واحد على الأقل يثبت أن الحركة أسوأ من أحتمال وجد مسبقًا. مثل هذه التحركات لا تحتاج إلى مزيد من التقييم. تفحص الاحتمالات مثل شجرة المينيكس القياسية، ولكنها تقطع الأحتمالات التي تبدو سيئة بشكل واضح. (ar)
- Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Connect 4, etc.). It stops 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. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision. (en)
- En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax. Il est utilisé dans des programmes informatiques qui jouent à des jeux à 2 joueurs, comme les échecs ou les dames[réf. souhaitée]. (fr)
- 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 (Tris, Go, Scacchi ecc.), 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. (it)
- 알파-베타 가지치기(Alpha–beta pruning)는 탐색 트리에서 최소극대화(미니맥스) 알고리즘을 적용할 때 평가(evaluate)하는 노드의 수를 줄이기 위한 알고리즘이다. 이 알고리즘은 적대탐색 알고리즘이라고도 하며, 기계가 플레이하는 2인용 게임(틱택토, 체스, 바둑)에 주로 사용된다. 이 알고리즘은 이전에 평가한 노드보다 현재 평가하는 노드가 더 좋지 않을 가능성이 있으면 평가를 중단한다. 이 노드의 남은 형제(sibling) 노드와 모든 후손 노드는 가지치기되어 평가하지 않는다. 이 알고리즘을 일반적인 미니맥스에 적용하면 동일한 결과를 얻게 된다. 최종 결정에 영향을 미치지 않는 가지들을 쳐낼 뿐이다. (ko)
- アルファ・ベータ法（アルファ・ベータほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。 (ja)
- 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. (pl)
- Альфа-бета-отсечение (англ. alpha-beta pruning) — алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакса. Предназначен для антагонистических игр и используется для машинной игры (в компьютерных шахматах, компьютерном го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета-отсечение является оптимизацией, так как не влияет на корректность работы алгоритма. (ru)
- Альфа-бета відсічення — алгоритм пошуку, що зменшує кількість вузлів, які необхідно оцінити в дереві пошуку мінімаксного алгоритму і при цьому дозволяє отримати ідентичний результат. Цей алгоритм використовується в програмуванні настільних ігор, де грають два гравці (хрестики-нулики, шахи, ґо). Використовуючи цей алгоритм, програма повністю припиняє оцінювати хід, якщо знайшла доказ, що цей хід гірший, ніж оцінений раніше. Такі ходи не потребують подальшої оцінки. (uk)
- Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。 (zh)
- 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. Z tohoto pohledu jde o algoritmus používající metodu větví a mezí, kde meze jsou dvě, každá pro jednoho hráče. (cs)
- 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. (de)
- 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, , , Donald Knuth y Ronald W. Moore (es)
|
