Alpha Beta Poda em AI

Alpha Beta de Poda
Compartilhe

Facebook
Twitter
WhatsApp

Alpha beta a poda é uma técnica de otimização para o algoritmo minimax. Através do curso deste blog, vamos discutir o que significa poda alpha beta, vamos discutir algoritmo minimax, regras para encontrar uma boa encomenda, e muito mais.

  1. Introdução
  2. algoritmo Minimax
  3. pontos-Chave na Podas Alfa-beta
  4. Trabalho de Podas Alfa-beta
  5. Mover para Pedido de Poda
  6. Regras encontrar Bom ordenação
  7. Códigos em Python

Introdução

A palavra ‘poda’ significa corte de ramos e folhas. Em Ciência da informação poda é um termo muito usado que se refere ao pós e pré-poda em árvores de decisão e floresta aleatória. A poda alfa-beta não é mais do que a poda de ramos inúteis nas árvores decisivas. Este algoritmo de poda alfa-beta foi descoberto independentemente pelos pesquisadores em 1900.

poda alfa-beta é uma técnica de otimização para o algoritmo minimax que é discutido na próxima seção. A necessidade de podar veio do fato de que, em alguns casos, as árvores de decisão se tornam muito complexas. Nessa árvore, alguns ramos inúteis aumentam a complexidade do modelo. Então, para evitar isso, poda alfa-Beta vem para jogar de modo que o computador não tem que olhar para toda a árvore. Estes nós incomuns tornam o algoritmo lento. Assim, ao remover estes nós algoritmo torna-se rápido.

Learn about a * algorithm.

algoritmo Minimax

Minimax é uma técnica clássica de busca de profundidade para um jogo sequencial de dois jogadores. Os dois jogadores são chamados MAX E MIN. O algoritmo minimax é projetado para encontrar o movimento ideal para MAX, o jogador no nó raiz. A árvore de busca é criada pela expansão recursivamente de todos os nós da raiz de uma forma de profundidade-primeira até que seja atingido o fim do jogo ou a profundidade máxima de busca. Vamos explorar este algoritmo em detalhe.Como já mencionado, há dois jogadores no jogo, viz – Max e Min. O Max dá o primeiro passo. A tarefa de Max é maximizar a sua recompensa, enquanto a tarefa de Min é minimizar a recompensa de Max, aumentando a sua própria recompensa ao mesmo tempo. Digamos que o Max pode fazer as acções a, b ou C. qual delas dará à Max a melhor recompensa quando o jogo acabar? Para responder a esta pergunta, precisamos explorar a árvore de jogo a uma profundidade suficiente e assumir que Min joga de forma otimizada para minimizar a recompensa de Max.

aqui está um exemplo. Quatro moedas estão em linha e cada jogador pode pegar uma ou duas moedas na sua vez. O jogador que pegar a última moeda ganha. Assumindo que o Max joga primeiro, que jogada deve a Max fazer para ganhar?

Se Max escolher duas moedas, então apenas duas moedas permanecem e Min pode escolher duas moedas e ganhar. Assim, recolher 1 moeda maximizará a recompensa de Max.

como você pode ter notado, os nós da árvore na figura abaixo têm alguns valores inscritos neles, estes são chamados de valor minimax. O valor minimax de um nó é o Utilitário do nó se ele é um nó terminal.

Esta imagem tem um atributo alt vazio; o nome do arquivo é eZEpHI4GGSgWTP98X9P9RWZYc-VVYf3Tys0Ya8rnYhQHYPcIhU3HhrdPBHlvz8rzgemcsgy-r1CKYpUnUnp8h7l4CAnnweRhG9orqGkoyc2bxdbo9njpjxqzsfjyn6zy7tlp1b7lmw1wzjlycq

Se o nó não-terminal nó Máximo, o minimax valor do nó é o máximo de minimax valores de todos os sucessores do nó. Por outro lado, se o nó é um nó Min Não-terminal, o valor de minimax do nó é o mínimo dos valores de minimax de todos os sucessores do nó.Agora vamos discutir a ideia por trás da poda alfa beta. Se aplicarmos a poda alfa-beta ao algoritmo de minimax padrão, ele dá a mesma decisão que a do algoritmo padrão, mas ele diminui ou reduz os nós que são incomuns na árvore de decisão, ou seja, que não estão afetando a decisão final tomada pelo algoritmo. Isto ajudará a evitar a complexidade na interpretação de árvores complexas.

See how KNN algorithm works.Agora vamos discutir a intuição por trás desta técnica. Vamos tentar encontrar a decisão minimax na árvore abaixo :

neste caso,,

Minimax Decisão = MAX {MIN {3, 5, 10}, MIN {2, a, b}, MIN.{2, 7, 3}}

= MAX {3, c, 2} = 3

Aqui no resultado acima, você deve ter uma dúvida em sua mente de que como podemos encontrar o máximo de valor em falta. Então, aqui está a solução da sua dúvida também:

no segundo nó escolhemos o valor mínimo como c que é menor ou igual a 2 ou seja c <= 2. Agora se c < = 3 e temos que escolher o máximo de 3, c, 2 o valor máximo será 3.Chegámos a uma decisão sem olhar para esses nós. E é aqui que a poda alfa-beta entra na peça.

pontos-chave na poda alfa-beta

  • alfa: alfa é a melhor escolha ou o valor mais alto que encontramos em qualquer instância ao longo do Caminho do Maximizador. O valor inicial para alpha é -∞.
  • Beta: Beta é a melhor escolha ou o menor valor que encontramos em qualquer instância ao longo do Caminho do Minimizador. O valor inicial para alfa é+∞.
  • a condição para a poda alfa-beta é Que α > = β.
  • cada nó tem que manter o controle de seus valores alfa e beta. Alpha pode ser atualizado apenas quando é a vez de MAX e, da mesma forma, beta pode ser atualizado apenas quando é a chance de MIN.
  • MAX irá atualizar apenas os valores alfa e Min player irá atualizar apenas os valores beta.
  • os valores dos nós serão passados para nós superiores em vez de valores de alfa e beta durante ir para o reverso da árvore.
  • os valores alfa e Beta só podem ser passados para os nós-filhos.Vamos começar com o movimento inicial. Vamos inicialmente definir os valores alfa e beta como o pior caso, ou seja, α = -∞ e β= +∞. Só vamos podar o nó quando Alfa se tornar maior ou igual a beta.
  • 2. Como o valor inicial de alfa é inferior ao beta,não o podámos. Agora é a vez do MAX. Assim, no nó D, o valor de alfa será calculado. O valor de alfa no nó D será max (2, 3). Então, o valor de alfa no nó D Será 3.

    3. Agora a próxima jogada será no nó B e sua vez para MIN agora. Assim, no nó B, O valor de Alfa beta será min (3,∞). Então, no nó B os valores serão alfa= – ∞ e beta será 3.

    No próximo passo, algoritmos de atravessar o próximo sucessor do Nó B, que é o nó e, e os valores de α= – ∞ e β= 3 também será passado.

    4. Agora é a vez do MAX. Então, no nó E vamos procurar o MAX. O valor actual de alfa em e é ∞ e será comparado com 5. Então, MAX ( – ∞ , 5) será 5. Então, no nó E, Alfa = 5, Beta = 5. Agora como podemos ver que alfa é maior que beta, o que está satisfazendo a condição de poda para que possamos podar o sucessor certo do nó E E algoritmo não será atravessado e o valor no nó E será 5.

    6. No passo seguinte, o algoritmo novamente vem para o nó A do Nó B. No nó A Alfa será alterado para o valor máximo como MAX (- ∞, 3). Então agora o valor de alfa e beta no nó A será (3, + ∞) respectivamente e será transferido para o nó C. Estes mesmos valores serão transferidos para o nó F.

    7. No nó F, O valor de alfa será comparado com o ramo esquerdo que é 0. Assim, MAX (0, 3) será 3 e então comparado com a criança certa que é 1, e MAX (3,1) = 3 ainda α permanece 3, mas o valor do nó de F se tornará 1.

    8. Agora o nó F irá devolver o valor do nó 1 Para C e irá comparar com o valor beta em C. Agora a sua vez para MIN. Então, MIN ( + ∞ , 1) será 1. Agora no nó C, α= 3, e β= 1 e alfa é maior que beta, o que novamente satisfaz a condição de Poda. Assim, o próximo sucessor do nó C, i.e. G vai ser podadas e o algoritmo não computacional toda a subárvore G.

    Agora, C retornará o valor de nó para Um e o melhor valor de A será MAX (1, 3) será 3.

    a árvore representada acima é a árvore final que está mostrando os nós que são computados e os nós que não são computados. Então, para este exemplo, o valor ideal do maximizador será 3.

    veja as bibliotecas Python de código aberto.

    ordenar a poda

    a eficácia da poda alfa – beta baseia-se na ordem em que o nó é examinado. A ordenação de movimentos desempenha um papel importante na poda alfa beta.

    Existem dois tipos de movimento de ordenação em Alfa beta poda:

  1. Pior Ordenação: Em alguns casos de alpha beta poda nenhum nó podadas pelo algoritmo e funciona como padrão de algoritmo minimax. Isso consome muito tempo por causa de fatores alfa e beta e também não dá quaisquer resultados efetivos. Isto é chamado de pior encomenda em Poda. Neste caso, o melhor movimento ocorre no lado direito da árvore.
  2. ideal Ordering: In some cases of alpha beta pounding lot of the nods pounded by the algorithm. Isto é chamado de encomenda Ideal na poda. Neste caso, o melhor movimento ocorre no lado esquerdo da árvore. Aplicamos DFS, portanto, primeira busca à esquerda da árvore e ir mais fundo duas vezes como algoritmo minimax na mesma quantidade de tempo.

Regras encontrar Bom ordenação

  • A melhor jogada que acontece a partir do nó mais baixo
  • Utilização de domínio de conhecimento, ao encontrar os melhores mover
  • Ordem de nós deve ser de tal forma que o melhor de nós será calculado primeiro

confira este Python Tutorial para Iniciantes

Códigos em Python

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

neste documento, temos visto uma componente importante da teoria dos jogos. Embora o desempenho do algoritmo minimax seja bom, o algoritmo é lento. Então, para torná-lo rápido, usamos o algoritmo de poda alfa-beta que irá cortar os nós incomuns da árvore de decisão para melhorar o desempenho. Atualmente, algoritmo rápido e bem executado é amplamente utilizado.

confira estes cursos de Inteligência Artificial e aprendizagem de máquinas de grande aprendizagem para upskill no domínio e master Alpha Beta poda e outros algoritmos.

Ler Mais

  1. A* Algoritmo de Pesquisa em Inteligência Artificial (AI)
  2. Algoritmo de Árvore de Decisão Explicado com Exemplos
  3. o Melhor Algoritmo de Pesquisa em AI | Conceito, Aplicação, Vantagens, Desvantagens
  4. o Que é Inteligência Artificial? Como funciona a IA, tipos e futuro dela?

Deixe uma resposta

O seu endereço de email não será publicado.

Previous post Cumprir as Contas Wide Receivers
Next post Reddit Streaming Sites-Movies Subreddit & Entertainment List