Função minimax C++

Question

Pesquisei essa pergunta no Google e no Stackoverflow, mas ainda não entendi como funciona uma função minimax.

Descobri que a entrada da Wikipedia tem uma versão em pseudocódigo da função:

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

Várias outras funções minimax que encontrei no Google são basicamente a mesma coisa;Estou tentando implementar isso em C++ e foi isso que descobri até agora:

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

Como você pode ver, estou bastante confuso sobre essa função minimax.Por favor, pelo menos me dê algumas dicas para me ajudar com isso.

Obrigado!:)

Answer 1

Essa amostra da Wikipedia está fazendo Negamax com poda alfa/beta.

Você pode ser ajudado a nomear a nomeação:

• A base é minimax, uma implementação literal envolveria 2 métodos que se revezam (mutuamente recursivo), 1 para cada lado.

• Programadores preguiçosos transformam isso em negamax, um método com um posicionado estrategicamente - operador.

• A poda alfa/beta está acompanhando uma janela de melhores movimentos (em várias profundidades) para detectar galhos mortos.

Sua playerTurn é usado para determinar de quem é a curva. No Negamax, você pode derivar isso da profundidade (iterações) sendo estranhos ou mesmo. Mas seria mais fácil usar 2 parâmetros (MyColor, OtherColor) e alterná -los em cada nível.

Answer 2

Sua função minimax () deve se lembrar do melhor movimento que encontrou até agora. Então, em vez deste código:

  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

Você deve fazer algo assim:

  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

Obviamente, você precisa de uma variável "BestMove" e uma maneira de devolver o melhor movimento encontrado ao chamador.

Answer 3

Adicione o playerTurn variável como argumento para miniMax, e ligue miniMax que o jogador atual é inicialmente e recursivamente.

Também, opponentSide precisa ser uma função de playerTurn.

Answer 4

Um bom lugar para começar a pesquisar na árvore do jogo é o wiki de programação de xadrez.Para sua pergunta sobre a mudança:Acho que é mais comum ter duas funções máximas.A diferença entre as duas funções max é que uma retorna apenas a pontuação e a outra retorna a pontuação e a melhor jogada.Uma ordem de chamada recursiva seria a seguinte:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

Existem alguns bons artigos com pseudocódigo para o algoritmo Alpha Beta:

• TA Marsland - Xadrez e Pesquisa de Computador
• J Schaeffer - Os jogos que os computadores (e as pessoas) jogam

Para sua pergunta no comentário: e math.max(alpha,score) ou math.min(alpha,score) Alpha é um booleano aí?!

Nenhum alfa é uma janela vinculada a um algoritmo alfa beta.O valor alfa é atualizado com um novo valor.Como alfa e beta são trocados com a chamada recursiva da função negamax, a variável alfa se refere à variável beta na próxima chamada recursiva.

Uma observação para a variável playerTurn:O algoritmo minimax ou alfa-beta não precisa dessas informações.Então eu daria a informação – quem é o próximo – na Estrutura do Conselho.As funções findPossibleMoves e boardEval obtêm todas as informações necessárias da estrutura do tabuleiro.

Uma observação sobre a condição de interrupção recursiva:Se eu entendi seu código corretamente, então você só tem aquele com iterations == o.Acho que isso significa que o algoritmo atingiu a profundidade desejada.Mas e se não houver mais movimentos possíveis antes que o algoritmo atinja essa profundidade?Talvez você devesse escrever o seguinte:

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);

Answer 5

No seu pseudocódigo, a variável do nó deve conter todas as informações sobre a posição atual da placa (ou qualquer outra coisa). Esta informação incluiria cuja vez ela é mover.