| rdfs:comment
| - Negascout es una variante del algoritmo Minimax, es un algoritmo que combina la relación matemática del Negamax y el uso de . También llamado "búsqueda de la variante principal" este algoritmo puede ofrecer rendimientos incluso mayores a la poda alfa-beta si los nodos se encuentran correctamente ordenados. Al igual que alfa-beta, negascout es un algoritmo de búsqueda direccional para calcular el valor minimax de un nodo en un árbol. La mejora del algoritmo negascout sobre el algoritmo alfa-beta es que el primero no examinará un nodo que el segundo podaría. pseudocodigo: (es)
- Principal variation search (sometimes equated with the practically identical NegaScout) is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree. It dominates alpha-beta pruning in the sense that it will never examine a node that can be pruned by alpha-beta; however, it relies on accurate node ordering to capitalize on this advantage. (en)
- Il NegaScout o Ricerca a variazione principale è un algoritmo negamax che in alcuni casi può essere più veloce della potatura alfa-beta. Come quest'ultima, il Negascout è un algoritmo per la ricerca del nodo di valore minimo in un dato albero; è dominante sull'algoritmo alfa-beta, cioè non visiterà mai un nodo che l'alfa-beta avrebbe potato, però questa caratteristica esige un accurato ordinamento dell'albero da esaminare per essere vantaggiosa, per cui la sua adozione deve essere decisa valutando la struttura del programma e le caratteristiche del problema da affrontare. (it)
- NegaScout または PVS (Principal Variation Search) は Alexander Reinefeld によって考案された アルファ・ベータ法よりも効率の良いミニマックス法アルゴリズムの一種である。 NegaScout は手の選択肢を列挙し何らかの方法で並べ替えた上で、初めに最も良さそうな手を通常の探索窓で探索し評価値を得る。それ以降の手はまず Null Window Search を行いそれまでに見つかった最善手の評価値を超えるかどうかを調べ、超えた場合にのみあらためて通常の探索窓で再探索し評価値を得る。但し、得られた評価値がβ値以上でもあれば再探索を行わずその場でカットできる。Null Window Searchは探索窓が狭くカットが頻繁に起こるため通常の探索よりも短時間で終了するが、探索順序がランダムだと再探索が頻繁に起こり、結局はアルファ・ベータ法よりも時間が掛かってしまう。この様に NegaScout が効率よく機能するかどうかは手の並べ替えの精度に依存しており、初めに調べる手が最善手である場合に最も効率が良くなる。その際よく用いられる方法としては、浅い探索の結果による並べ替えがある。 (ja)
|
| has abstract
| - Negascout es una variante del algoritmo Minimax, es un algoritmo que combina la relación matemática del Negamax y el uso de . También llamado "búsqueda de la variante principal" este algoritmo puede ofrecer rendimientos incluso mayores a la poda alfa-beta si los nodos se encuentran correctamente ordenados. Al igual que alfa-beta, negascout es un algoritmo de búsqueda direccional para calcular el valor minimax de un nodo en un árbol. La mejora del algoritmo negascout sobre el algoritmo alfa-beta es que el primero no examinará un nodo que el segundo podaría. Este algoritmo es útil siempre y cuando los nodos estén bien ordenados ya que supone que el primer nodo explorado será el mejor, así podrá confirmarlo en otros nodos usando la ventana nula. En caso de fallo, como el primer nodo no era el de máximo nivel, se seguirá buscando el mejor nodo en el árbol del mismo modo que en el algoritmo alfa-beta. pseudocodigo: int negascout(nodo, profundidad, α, β) { if (esTerminal(nodo) || profundidad==0) return valorHeuristico(nodo); b = β; // la ventana inicial es (-β, -α) foreach nodoHijo a = -negascout (hijo, profundidad-1, -b, -α); if (a>α) α = a; if (α>=β) return α; //Corte Beta if (α>=b) //comprueba si fallo la ventana nula α = -negascout(hijo, profundidad-1, -β, -α); //Nueva búsqueda completa if (α>=β) return α; //Corte Beta b = α+1; //Crea nuava ventana nula return α;}
* Datos: Q2269304 (es)
- Principal variation search (sometimes equated with the practically identical NegaScout) is a negamax algorithm that can be faster than alpha-beta pruning. Like alpha-beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree. It dominates alpha-beta pruning in the sense that it will never examine a node that can be pruned by alpha-beta; however, it relies on accurate node ordering to capitalize on this advantage. NegaScout works best when there is a good move ordering. In practice, the move ordering is often determined by previous shallower searches. It produces more cutoffs than alpha-beta by assuming that the first explored node is the best. In other words, it supposes the first node is in the principal variation. Then, it can check whether that is true by searching the remaining nodes with a null window (also known as a scout window; when alpha and beta are equal), which is faster than searching with the regular alpha-beta window. If the proof fails, then the first node was not in the principal variation, and the search continues as normal alpha-beta. Hence, NegaScout works best when the move ordering is good. With a random move ordering, NegaScout will take more time than regular alpha-beta; although it will not explore any nodes alpha-beta did not, it will have to re-search many nodes. Alexander Reinefeld invented NegaScout several decades after the invention of alpha-beta pruning. He gives a proof of correctness of NegaScout in his book. Another search algorithm called SSS* can theoretically result in fewer nodes searched. However, its original formulation has practical issues (in particular, it relies heavily on an OPEN list for storage) and nowadays most chess engines still use a form of NegaScout in their search. Most chess engines use a transposition table in which the relevant part of the search tree is stored. This part of the tree has the same size as SSS*'s OPEN list would have. A reformulation called MT-SSS* allowed it to be implemented as a series of null window calls to Alpha-Beta (or NegaScout) that use a transposition table, and direct comparisons using game playing programs could be made. It did not outperform NegaScout in practice. Yet another search algorithm, which does tend to do better than NegaScout in practice, is the best-first algorithm called MTD(f), although neither algorithm dominates the other. There are trees in which NegaScout searches fewer nodes than SSS* or MTD(f) and vice versa. NegaScout takes after SCOUT, invented by Judea Pearl in 1980, which was the first algorithm to outperform alpha-beta and to be proven asymptotically optimal. Null windows, with β=α+1 in a negamax setting, were invented independently by J.P. Fishburn and used in an algorithm similar to SCOUT in an appendix to his Ph.D. thesis, in a parallel alpha-beta algorithm, and on the last subtree of a search tree root node. (en)
- NegaScout または PVS (Principal Variation Search) は Alexander Reinefeld によって考案された アルファ・ベータ法よりも効率の良いミニマックス法アルゴリズムの一種である。 NegaScout は手の選択肢を列挙し何らかの方法で並べ替えた上で、初めに最も良さそうな手を通常の探索窓で探索し評価値を得る。それ以降の手はまず Null Window Search を行いそれまでに見つかった最善手の評価値を超えるかどうかを調べ、超えた場合にのみあらためて通常の探索窓で再探索し評価値を得る。但し、得られた評価値がβ値以上でもあれば再探索を行わずその場でカットできる。Null Window Searchは探索窓が狭くカットが頻繁に起こるため通常の探索よりも短時間で終了するが、探索順序がランダムだと再探索が頻繁に起こり、結局はアルファ・ベータ法よりも時間が掛かってしまう。この様に NegaScout が効率よく機能するかどうかは手の並べ替えの精度に依存しており、初めに調べる手が最善手である場合に最も効率が良くなる。その際よく用いられる方法としては、浅い探索の結果による並べ替えがある。 チェスプログラムではアルファ・ベータ法に比べ、典型的には10％程度のパフォーマンス上昇が見込めると言われる。後にさらに少ない探索量が期待できるMTD(f)と呼ばれる探索法も考案されたが、置換表に強く依存するなどの性質を避けるために今日のチェスプログラムでも NegaScout は広く使われている。また、MTD(f)の基礎となったと呼ばれる最良優先探索アルゴリズムもあるが、探索するゲーム木によっては NegaScout と比べ探索量が増えたりもする事や、最良優先探索の性質である多くのメモリを必要とする事などの問題があるため普及していない。 (ja)
- Il NegaScout o Ricerca a variazione principale è un algoritmo negamax che in alcuni casi può essere più veloce della potatura alfa-beta. Come quest'ultima, il Negascout è un algoritmo per la ricerca del nodo di valore minimo in un dato albero; è dominante sull'algoritmo alfa-beta, cioè non visiterà mai un nodo che l'alfa-beta avrebbe potato, però questa caratteristica esige un accurato ordinamento dell'albero da esaminare per essere vantaggiosa, per cui la sua adozione deve essere decisa valutando la struttura del programma e le caratteristiche del problema da affrontare. Il NegaScout è stato inventato da alcuni decenni dopo l'invenzione della potatura alfa-beta; dimostrò la correttezza di questo algoritmo nel suo libro, citato sotto nei riferimenti. (it)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)