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.
- Introdução
- algoritmo Minimax
- pontos-Chave na Podas Alfa-beta
- Trabalho de Podas Alfa-beta
- Mover para Pedido de Poda
- Regras encontrar Bom ordenação
- 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.
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:
- 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.
- 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
- A* Algoritmo de Pesquisa em Inteligência Artificial (AI)
- Algoritmo de Árvore de Decisão Explicado com Exemplos
- o Melhor Algoritmo de Pesquisa em AI | Conceito, Aplicação, Vantagens, Desvantagens
- o Que é Inteligência Artificial? Como funciona a IA, tipos e futuro dela?