Algoritmo Minimax com podas Alfa-beta

desde o advento da Inteligência Artificial (AI), de jogo tem sido uma das mais interessantes aplicações da IA.

os primeiros programas de xadrez foram escritos por Claude Shannon e por Alan Turing em 1950, quase assim que os computadores se tornaram programáveis.Jogos como xadrez, tic-tac-toe e Go são interessantes porque oferecem uma abstração pura da competição entre os dois exércitos.

é esta abstração que faz do jogo uma área atraente para a pesquisa de IA.

neste artigo, vamos passar pelos conceitos básicos do algoritmo Minimax, juntamente com o funcionamento do algoritmo.

nós também vamos dar uma olhada na otimização do algoritmo de minimax, poda alfa-beta.

Qual é o algoritmo Minimax?

Minimax é um algoritmo recursivo que é usado para escolher um movimento ideal para um jogador assumindo que o outro jogador também está jogando de forma otimizada.

é usado em jogos como tic-tac-toe, go, chess, Isola, checkers e muitos outros jogos de dois jogadores.Esses jogos são chamados de jogos de informação perfeita porque é possível ver todos os movimentos possíveis de um jogo em particular.

pode haver jogos de dois jogadores que não são de informação perfeita, como o Scrabble porque a jogada do adversário não pode ser prevista.

é semelhante a como pensamos quando jogamos um jogo:” se eu fizer este movimento, então o meu adversário só pode fazer estes movimentos”, e assim por diante.

Minimax é chamado assim porque ajuda a minimizar a perda quando o outro jogador escolhe a estratégia tendo a perda máxima.

terminologia

• Árvore de jogos: é uma estrutura na forma de uma árvore que consiste em todos os movimentos possíveis que lhe permitem passar de um estado do jogo para o próximo estado.

Um jogo pode ser definido como um problema de pesquisa com os seguintes componentes:

• estado Inicial: compreende a posição do conselho de administração e mostrando cuja movimentação é.
• função sucessora: Define quais são os movimentos legais que um jogador pode fazer.
• estado Terminal: é a posição do tabuleiro quando o jogo acaba.
• função de utilidade: é uma função que atribui um valor numérico para o resultado de um jogo. Por exemplo, no xadrez ou tic-tac-toe, o resultado é uma vitória, uma perda ou um empate, e estes podem ser representados pelos valores +1, -1, ou 0, respectivamente. Há jogos que têm uma gama muito maior de resultados possíveis; por exemplo, os utilitários em gamão varia de +192 a -192. Uma função de utilidade pública também pode ser chamada de função de pagamento.

como funciona o algoritmo?

há dois jogadores envolvidos em um jogo, chamado MIN e MAX. O jogador MAX tenta obter a maior pontuação possível e MIN tenta obter a menor pontuação possível, ou seja, MIN e MAX tentam agir em oposição um ao outro.

o processo geral do algoritmo Minimax é o seguinte:

Passo 1: Primeiro, gerar toda a árvore de jogos começando com a posição atual do jogo até os estados terminais. É assim que a árvore de jogo se parece para o jogo tic-tac-toe.

vamos entender a terminologia definida em termos do diagrama acima.

1. o estado inicial é a primeira camada que define que o tabuleiro está em branco é a vez de MAX jogar.
2. a função sucessora lista todos os possíveis movimentos sucessores. É definido para todas as camadas da árvore.
3. o estado Terminal é a última camada da árvore que mostra o estado final, ou seja, se o jogador MAX ganha, perde ou empata com o adversário.
4. Utilities in this case for the terminal states are 1, 0, and -1 as discussed earlier, and they can be used to determine the utilities of the other nodes as well.

Passo 2: Aplicar a função de utilidade para obter os valores de utilidade para todos os estados terminais.
Passo 3: Determinar os utilitários dos nós superiores com a ajuda dos utilitários dos nós terminais. Por exemplo, no diagrama abaixo, temos os utilitários para os estados terminais escritos nos quadrados.

vamos calcular o utilitário para o nó esquerdo(vermelho) da camada acima do terminal. Uma vez que é o movimento do jogador MIN, vamos escolher o mínimo de todos os utilitários. Para este caso, temos que avaliar MIN{3, 5, 10}, que sabemos ser certamente 3. Então o utilitário para o nó vermelho é 3.

similarmente, para o nó verde na mesma camada, teremos que avaliar MIN{2,2} que é 2.

Passo 4: Calcular os valores de utilidade com a ajuda de folhas considerando uma camada de cada vez até a raiz da árvore.
Passo 5: eventualmente, todos os valores de backup chegam à raiz da árvore, ou seja, o ponto mais alto. Nesse momento, MAX tem que escolher o valor mais alto.

no nosso exemplo, temos apenas 3 camadas, então chegamos imediatamente à raiz, mas em jogos reais, haverá muitas mais camadas e nós. Temos de avaliar o máximo que é 3.

portanto, o melhor movimento de abertura para MAX é o nó esquerdo(ou o vermelho). Este movimento é chamado de decisão minimax como ele maximiza o utilitário seguindo a suposição de que o adversário também está jogando de forma otimizada para minimizá-lo.

Para resumir,

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

Psuedocode:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

Otimização

Jogo de árvores são, em geral, muito demorado para se construir, e é apenas para os jogos de simples que pode ser gerado em um curto período de tempo.

If there are \(b\) legal moves, i.e., \(b\) os nós em cada ponto e a profundidade máxima da árvore é \(m\), a complexidade de tempo do algoritmo minimax é da ordem \(b^m (S(b^m))\).

para conter esta situação, existem algumas otimizações que podem ser adicionadas ao algoritmo.

felizmente, é viável encontrar a decisão minimax real sem mesmo olhar para cada nó da árvore de jogo. Assim, eliminamos nós da árvore sem analisar, e este processo é chamado de Poda.

poda alfa-beta

o método que vamos procurar neste artigo é chamado de poda alfa-beta.

se aplicarmos a poda alfa-beta a um algoritmo de minimax padrão, ele retorna o mesmo movimento que o padrão, mas remove (ameixas) todos os nós que possivelmente não estão afetando a decisão final.Vamos compreender a intuição por trás disto primeiro e depois formalizaremos o algoritmo. Suponha que temos a seguinte árvore de jogo:

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

Você ficaria surpreso!Como podemos calcular o máximo com um valor em falta? Eis o truque. MIN{2,A,b} certamente seria menor ou igual a 2, ou seja, c<=2 e,portanto,MAX{3, c, 2} tem que ser 3.

a questão agora é se realmente precisamos calcular c? Claro que não.Podíamos ter chegado a uma conclusão sem olhar para esses nós. E é aqui que a poda alfa-beta entra em cena.

algumas definições:

Alpha: é a melhor escolha até agora para o jogador MAX. Queremos obter o maior valor possível aqui.
Beta: É a melhor escolha até agora para MIN, e tem que ser o menor valor possível.Nota: cada nó tem de acompanhar os 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.Como funciona a poda alfa-beta?

1. inicializar Alfa = – infinito e beta = infinito como os piores casos possíveis. A condição para podar um nó é quando Alfa se torna maior ou igual a beta.
2. comece por atribuir os valores iniciais de alfa e beta à raiz e como alfa é menor que beta não o podamos.
3. transportar estes valores de alfa e beta para o nó-criança à esquerda. E agora, a partir do valor de utilidade do estado terminal, vamos atualizar os valores de alpha e be, para que não tenhamos que atualizar o valor de beta. Mais uma vez, não podamos porque a condição permanece a mesma. Da mesma forma, o terceiro nó de criança também. E então voltando para a raiz, colocamos alfa = 3 porque esse é o valor mínimo que alfa pode ter.
   
4. agora, alfa = 3 e beta=infinito na raiz. Então, não podamos. Levando isto para o nó central, e calculando MIN{2, infinity}, temos alfa=3 e beta=2.
5. podar os nós do segundo e terceiro filhos porque alfa é agora maior que beta.
6. Alfa na raiz permanece 3 porque é maior que 2. Levando isto para o nó criança mais à direita, avalie MIN{infinity, 2} = 2. Actualizar beta para 2 e alfa permanece 3.
7. podar os nós do segundo e terceiro filhos porque alfa é agora maior que beta.
8. portanto, temos 3, 2, 2 No nós MIN esquerdo, centro, e direito, respectivamente. E calculando o máximo{3,2,2}, temos 3. Portanto, sem sequer olhar para quatro folhas poderíamos encontrar corretamente a decisão minimax.

Pseudocode (fonte: curso de NPTEL):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

conclusão: os jogos são muito atraentes e escrever programas de jogos é talvez ainda mais emocionante. O que a corrida de Grand Prix é para a indústria automóvel, o jogo é para AI.Assim como não esperaríamos que um carro de corrida funcionasse perfeitamente em uma estrada acidentada, não esperaríamos que os algoritmos de jogo fossem perfeitos para cada situação.

assim como o algoritmo minimax. Pode não ser a melhor solução para todos os tipos de jogos de computador que precisam ter AI.

mas dada uma boa implementação, ele pode criar um competidor duro.