Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game. This algorithm relies on the fact that to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single procedure can be used to value both positions. This is a coding simplification over minimax, which requires that A selects the move with the maximum-valued successor while B selects the mo
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Negamax (es)
- Negamax (it)
- Negamax (en)
- Negamax (pt)
|
| rdfs:comment
| - Negamax es una variante del algoritmo minimax donde cada nodo independientemente si fuese MIN o MAX toma el valor máximo de sus hijos (como si todos los nodo fueran MAX), solo que los valores de los nodos MAX se cambian de signo (de ahí su nombre, en vez de tomar máximos y mínimos toma siempre máximos pero con valores cambiados). De esta forma se logra el mismo efecto ya que tomar el mayor valor pero cambiado de signo es en realidad tomar el menor así cuando el algoritmo está en un nivel MIN cuando toma el mayor de sus hijos en realidad está tomando al menor.
* max(x, y)=-min(-x,-y) (es)
- Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game. This algorithm relies on the fact that to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single procedure can be used to value both positions. This is a coding simplification over minimax, which requires that A selects the move with the maximum-valued successor while B selects the mo (en)
- Il negamax è una piccola variante dell'algoritmo minimax che si basa sulle proprietà dei giochi a somma zero con due giocatori. Per definizione, il valore della posizione del giocatore A in un certo gioco è la negazione del valore della posizione del giocatore B. Così, il giocatore che deve muovere cercherà una mossa che massimizzi la negazione del valore della posizione risultante dalla mossa: per definizione, questa posizione del successore deve essere stata valutata dall'avversario. La veridicità di questa affermazione si mantiene indipendentemente dal fatto che sia A o B a dover muovere. Ciò significa che un singolo calcolo può essere usato per dare valore a tutte le posizioni. Questa è una semplificazione rispetto al minimax, che richiede che A scelga la mossa con il massimo valore di (it)
- Na programação de jogos de xadrez, o algoritmo de busca negamax é uma variante na implementação do algoritmo de busca minimax e seus derivados. Ambos os algoritmos baseiam-se na propriedade de soma zero de um jogo entre dois jogadores. O algoritmo negamax baseia-se na equação para simplificar a implementação da lógica do algoritmo minimax, que por sua vez leva em consideração a avaliação das posições dos jogadores separadamente. (pt)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Negamax es una variante del algoritmo minimax donde cada nodo independientemente si fuese MIN o MAX toma el valor máximo de sus hijos (como si todos los nodo fueran MAX), solo que los valores de los nodos MAX se cambian de signo (de ahí su nombre, en vez de tomar máximos y mínimos toma siempre máximos pero con valores cambiados). De esta forma se logra el mismo efecto ya que tomar el mayor valor pero cambiado de signo es en realidad tomar el menor así cuando el algoritmo está en un nivel MIN cuando toma el mayor de sus hijos en realidad está tomando al menor. La función Negamax podría recibir como parámetro un signo, de esta manera se podría comenzar por niveles MIN o niveles MAX, pero no necesariamente ya se puede establecer niveles estáticos, donde cada nivel está definido por un signo distinto. Hablando del Minimax: Suponiendo que existe min que devuelve el menor y max que devuelve el mayor, Negamax se basa en la siguiente igualdad matemática:
* max(x, y)=-min(-x,-y) A este algoritmo también se le pueden aplicar podas y heurísticas para acortar su tiempo de ejecución, además existe una mejora de este algoritmo llamado negascout. (es)
- Negamax search is a variant form of minimax search that relies on the zero-sum property of a two-player game. This algorithm relies on the fact that to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single procedure can be used to value both positions. This is a coding simplification over minimax, which requires that A selects the move with the maximum-valued successor while B selects the move with the minimum-valued successor. It should not be confused with negascout, an algorithm to compute the minimax or negamax value quickly by clever use of alpha-beta pruning discovered in the 1980s. Note that alpha-beta pruning is itself a way to compute the minimax or negamax value of a position quickly by avoiding the search of certain uninteresting positions. Most adversarial search engines are coded using some form of negamax search. (en)
- Il negamax è una piccola variante dell'algoritmo minimax che si basa sulle proprietà dei giochi a somma zero con due giocatori. Per definizione, il valore della posizione del giocatore A in un certo gioco è la negazione del valore della posizione del giocatore B. Così, il giocatore che deve muovere cercherà una mossa che massimizzi la negazione del valore della posizione risultante dalla mossa: per definizione, questa posizione del successore deve essere stata valutata dall'avversario. La veridicità di questa affermazione si mantiene indipendentemente dal fatto che sia A o B a dover muovere. Ciò significa che un singolo calcolo può essere usato per dare valore a tutte le posizioni. Questa è una semplificazione rispetto al minimax, che richiede che A scelga la mossa con il massimo valore di successione mentre B con il minimo. Il negamax non va confuso con il negascout, una moderna variante dell'agoritmo potatura alfa-beta scoperto negli anni '80, divenendo esso stesso una versione più avanzata del minimax o del negamax. Molti motori per la ricerca di soluzioni con avversari sono programmati utilizzando alcune forme dell'algoritmo negamax. (it)
- Na programação de jogos de xadrez, o algoritmo de busca negamax é uma variante na implementação do algoritmo de busca minimax e seus derivados. Ambos os algoritmos baseiam-se na propriedade de soma zero de um jogo entre dois jogadores. O algoritmo negamax baseia-se na equação para simplificar a implementação da lógica do algoritmo minimax, que por sua vez leva em consideração a avaliação das posições dos jogadores separadamente. Mais precisamente, o valor de uma posição para o jogador A é a negação do valor para o jogador B soma zero. Dessa forma, o jogador em movimento procura uma jogada que maximize a negação do valor resultante da jogada: esta posição sucessora deve, por definição, ter sido avaliada pelo oponente. Funcionando independentemente de A ou B estarem a jogar. Isso significa que um único procedimento pode ser usado para avaliar ambas as posições, seja a vez dos jogadores A ou B. Esta é uma simplificação de codificação sobre minimax, que requer que A selecione o movimento com o sucessor de valor máximo enquanto B seleciona o movimento com o sucessor de valor mínimo. O objetivo do algoritmo de pesquisa negamax é encontrar o valor da pontuação do nó para o jogador que está jogando no nó raiz (geralmente atribuímos +1 para as peças brancas e -1 para as peças negras). O pseudocódigo abaixo mostra o algoritmo base negamax, com um limite de profundidade de busca máxima configurável: função negamax(nó, profundidade, cor) se profundidade = 0 ou nó é um nó terminal então retorna valor heurístico do nó × cor valor = −∞ para cada filho do nó faça valor = máximo(valor, −negamax(filho, profundidade − 1, −cor)) retorna valor(* Chamada inicial da função negamax para o nó raiz do Jogador A *)negamax(nó raíz, profundidade, 1)(* Chamada inicial da função negamax para o nó raiz do Jogador B *)negamax(nó raíz, profundidade, −1) (pt)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[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)
