Melhores técnicas para uma IA de um jogo de cartas

Estou tentando desenvolver uma IA para um jogo de cartas e estou um pouco empolgado com a técnica / algoritmo que devo usar. Aqui estão algumas suposições sobre o jogo:

• Depois que as cartas são distribuídas aos jogadores, não há aleatoriedade. Quero dizer aqui que todo jogador pode escolher quais cartas ele joga, mas nenhum processo aleatório ocorre como na distribuição das cartas no início do jogo.
• Há restrições sobre as cartas que podem ser jogadas quando uma carta já foi jogada.
• O jogador que vencer o truque joga primeiro. Por exemplo, o jogador 1 joga uma carta, o jogador 2 joga uma carta e vence. Em seguida, o jogador 2 joga uma carta e depois o jogador 1.

Conheço muitas dicas / regras (por exemplo, se eu sei que o jogador tem as cartas A, B, C, então devo jogar D), o que me ajuda a vencer o jogo. Assim, eu primeiro queria usar uma rede bayesiana para descrever essas regras. O problema é que não conheço nenhuma probabilidade de atribuir, mas poderia calcular uma heurística usando o histórico dos jogos jogados (contra um humano). Segundo problemas, é muito provável que eu não conheça todas as regras e que exista algumas regras implícitas que a AI precisa para encontrar a jogada ideal.

Não tenho certeza se essa seria uma boa maneira de desenvolver uma IA para esse jogo de cartas?

Também estou me perguntando se existem outras técnicas que melhor se ajustariam ao problema. Por exemplo, dei uma olhada no minimax (talvez com um algoritmo de poda), mas seria uma boa opção para esse problema? Estou bastante inseguro, já que as jogadas mais importantes são no início do jogo, quando há os parâmetros desconhecidos mais altos (a maioria das cartas ainda não foi jogada).

Seu exemplo parece semelhante ao Bridge . Os sistemas Top Bridge-playing usam métodos de Monte Carlo para selecionar movimentos. Em alto nível:

• Determine as probabilidades de cada carta estar em uma determinada mão. Você sabe com certeza quais cartas estão na sua mão e quais cartas foram jogadas. Determine a probabilidade de todas as outras cartas com base nas cartas que foram jogadas e possivelmente no lance de um jogador, se houver lances envolvidos. Para começar, você pode usar uma probabilidade ingênua e igual de que uma carta esteja na mão de algum jogador.
• Agora, execute o máximo de jogos "virtuais" que puder. Simule jogar uma carta da sua mão e determine as respostas dos seus oponentes usando as regras do jogo e suas probabilidades. Para cada jogo virtual, use suas probabilidades para atribuir cartas a um jogador e simule rapidamente o jogo. Suponha que cada jogador jogue da melhor maneira possível. Você conhece todas as cartas do seu jogo virtual para poder fazer com que cada jogador jogue perfeitamente.
• Quando você tiver uma amostra sólida (ou o tempo esgotar), escolha a ação legal que lhe deu o melhor resultado com mais frequência.

Depois de conseguir algo funcionando, você pode adicionar todo tipo de estratégias enriquecidas. Por exemplo, varie suas probabilidades com base nas jogadas históricas de um jogador, varie probabilidades com base no estilo de um jogador (passivo, cauteloso, agressivo) ou até considere os efeitos de jogadores específicos jogando juntos.

Editar por comentário de LaurentG:

Por fim, convém descartar a idéia de jogo perfeito para todos os jogadores e substituir algo mais realista. Conceitualmente, separe as probabilidades de uma carta estar na mão de alguém (distribuição de cartas) da probabilidade de um jogador jogar uma determinada carta legal durante uma mão (seleção de cartas).

A seleção de cartões está pronta para o aprendizado. Se você acompanhar as jogadas entre os jogos, poderá aprender como um determinado jogador, ou jogadores em geral, tendem a jogar com base nas cartas da mão e nas cartas que foram jogadas. Você pode até gostar e modelar suas suposições sobre cartões ocultos deles.

Há também oportunidades de aprendizado para distribuição de cartões. Os lances anteriores de um jogador e a seleção de cartas durante uma mão podem revelar um "aviso" sobre o que está oculto em sua mão. Você pode usar dados históricos para ajustar as probabilidades ao criar cada jogo virtual.

Um caso de experiência pessoal recente:

Eu mesmo trabalhei em um jogo de cartas (Bisca, um jogo de português para dois jogadores) e obtive bons resultados usando os métodos de Monte Carlo, especialmente usando o recente algoritmo de pesquisa em árvore do Monte Carlo de conjunto de informações (ISMCTS, descrito com exemplo de código fonte no Python em http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Joga razoavelmente bem, com movimentos ocasionais incorretos, apenas com o conhecimento das regras do jogo. Atualmente, estou tentando grok, para poder aprimorá-lo, pois de acordo com as informações que li sobre ele (e seu MCTS "pai"), é possível aprimorar seu jogo com heurísticas ( http: // www .orangehelicopter.com / ed / papers / aiide13.pdf ) e inferência da carta do oponente.

Eu acho que depende das regras do jogo.

Aqui está o que eu entendo da sua pergunta:

• O jogo é jogado em rodadas, com cada jogador jogando uma carta por rodada
• O jogador que jogar primeiro pode jogar qualquer carta que quiser
• O jogador que fica em segundo lugar só pode jogar certas cartas, dependendo do que foi jogado primeiro
• O jogador que vence a rodada vai primeiro na próxima rodada
• Todos os cartões são distribuídos antes da primeira rodada

Suposições :

• Com pleno conhecimento das cartas do outro jogador, o jogador que decide primeiro, para cada uma delas, se uma carta vencerá a rodada ou não (o primeiro jogador pode jogar uma carta certa)
• Se as cartas A e B vencerem quando jogadas primeiro nesta rodada, jogar A nesta rodada (e vencer) e jogar B na rodada seguinte significa que B também vencerá (as cartas não perdem valor)
• Com o conhecimento completo das cartas do outro jogador, o jogador que fica em segundo lugar pode decidir se uma carta pode ganhar nesta rodada, mas perderia se jogada primeiro na rodada seguinte (escolha a pior carta vencedora)

Exemplo de jogo que segue estas regras:

O primeiro jogador joga uma carta. O segundo jogador tem que jogar uma carta da mesma suíte ou perder. Se as suítes combinarem, a carta mais alta vence.

Agora, este jogo é decidido pela sorte do empate e pela capacidade de memorizar quais cartas foram jogadas para conhecer a mão do seu oponente.
Nessa situação, eu faria com que a IA se lembrasse apenas parcialmente de quais cartas foram jogadas, ou seja, remova aleatoriamente da lista lembrada uma porcentagem das cartas jogadas (número menor = maior dificuldade da IA), mas não as importantes como Ases ou Reis. Dessa forma, por exemplo, a IA saberá que é seguro jogar uma dama de copas, porque ele lembrará que o oponente não tem o ás ou o rei, mas terá que calcular uma probabilidade se quiser jogar o 10, porque ele pode não se lembrar se o Jack ainda está em jogo.
Isso imita a atenção humana.

TL; DR
Limite o quanto a IA sabe para que suas decisões não sejam perfeitas, apenas boas o suficiente.