Algoritmos para um jogador inteligente de Poker



Baixar 1,37 Mb.
Página6/6
Encontro12.07.2018
Tamanho1,37 Mb.
1   2   3   4   5   6

1. Introdução


Ninguém sabe ao certo a origem do Poker (WIKIPEDIA POKER, 2008). O jogo mais antigo conhecido que tenha as características de blefe, “vence quem tem a melhor mão” e aposta é do século XV e de origem alemã, chamado Pochspiel. Há registros de pessoas jogando um jogo chamado As Nas no século XIX, que é muito parecido com poker e usa vinte cartas. Alguns historiadores descordam da origem do poker como uma variação do As Nas e acreditam vir de um jogo francês chamado Poque. O ator inglês Joseph Crowell relatou que o jogo era jogado em New Orleans em 1829, com um baralho de vinte cartas e quatro jogadores apostando qual “mão” era a mais valiosa. Logo após isso, o baralho inglês de 52 cartas foi utilizado e durante a Guerra Civil Americana as regras ficaram mais parecidas com as que são utilizadas hoje. Em torno de 1925 começou-se a jogar o poker com cartas comunitárias, que é a modalidade usada neste trabalho. O poker e seus jargões fazem parte da cultura americana. Em 1970 começaram os campeonatos mundiais de poker nos Estados Unidos. Em 1987, o poker com cartas comunitárias foram introduzidos em cassinos da Califórnia e se tornaram a modalidade de poker mais popular até hoje. Em 1998, um filme com o tema de poker chamado “Cartas na Mesa”, em inglês “Rounders”, foi lançado nos Estados Unidos.
Poker é um jogo de risco ou blefe. O espírito do jogo é conseguir convencer o adversário que o seu jogo é mais forte que o dele e tentar adivinhar se o jogo dele é mais forte que o seu. O convencimento é através de apostas. Se você não apostar que seu jogo é melhor que o do seu adversário, o seu adversário vence sem precisar mostrar o jogo. Também é conhecido como jogo de mentiroso, assim como o “truco” no Brasil.

As regras do jogo são bem simples e isso foi um dos motivos de ter se tornado tão popular (POKERLOCO, 2008). O jogador não possui informações suficientes para tomar a decisão ótima. Ou seja, é um jogo de informação incompleta e essa é uma característica de muitos problemas relacionados a área de Inteligência Artificial.

Um jogador com muita sorte consegue ganhar todos os jogos sem precisar tomar decisões inteligentes, mas esses casos são raros. Para a maioria das jogadores, Poker envolve alguma decisão inteligente. Isso explica porque bons jogadores de poker ganham mais que jogadores medianos e porque existem jogadores de Poker profissionais. Algumas pessoas afirmam que Poker é um jogo puramente de sorte mas para outras, que escreveram muitos livros a respeito, como David Sklansky, não. Existem muitos livros e artigos publicados a respeito, dezenas de softwares sendo comercializados em que o único propósito é tomar decisões inteligentes em Poker e muitos sites de Poker Online proíbem o uso destes softwares por dar muita vantagem aos jogadores que os utilizam.

Muitos jogadores artificiais de poker, também conhecidos como pokerbots, já foram desenvolvidos. Existem até torneios (JOHANSON, 2007) de pokerbots, como o 2007 AAAI Computer Poker Competition No-Limit event ocorrido no ano de 2007.

Para cumprir o objetivo de formular algoritmos que tomem decisões inteligentes em poker foi implementado cinco algoritmos de diferentes jogadores. O primeiro foi o jogador aleatório, que toma decisão aleatória, sem levar em conta o estado do jogo. O segundo foi o jogador constante, que toma uma decisão constante, também sem se importar com o estado do jogo. O terceiro, nomeado MFS, foi utilizar uma fórmula que faz uma relação linear com algumas informações do jogo, que são: com a quantidade de dinheiro apostado, a quantidade de dinheiro que possa vir a receber caso vença, a probabilidade de vencer e a probabilidade de perder. O quarto, nomeado RH, foi também utilizar outra fórmula que é uma relação linear de outras informações do jogo, que são: quantidade de dinheiro que receberá caso vença, a quantidade de jogadores que ainda vão tomar alguma decisão, a quantidade de jogadores não fugiram, a quantidade de dinheiro que precisa pagar para continuar no jogo e a quantidade de vezes que alguém aumentou a aposta. O quinto, nomeado jogador de aprendizado por reforço, foi armazenar milhões de decisões e consequências em diferentes estados do jogo através de simulações e, quando for tomar uma decisão, consultar essa base de dados por todas as decisões feitas em um estado semelhante e tomar a decisão que obteve o melhor resultado, na média. Este último jogador precisava de muitas constantes para ajustar a “semelhança do estado do jogo” e para encontrar estas constantes foi utilizado Algoritmo Genético.

Para medir o desempenho dos jogadores foi feito uma comparação de quantidade de vitórias disputando as diferentes estratégias uma com a outra, além de jogadores humanos testarem os jogadores artificiais. As disputas foram feitas utilizando diferentes configurações dos jogadores artificiais.

A justificativa para esse trabalho não é apenas criar um bom jogador de poker. A motivação é testar e comparar diferentes algoritmos de para jogar poker e testar um novo algoritmo de aprendizado para solucinar um problema com informação incompleta em um domínio relativamente simples que é o poker. Uma boa solução pode servir de inspiração para resolver problemas mais genéricos relacionados a barganha, que é o espírito do poker, como a bolsa de valores.

  1. 2. Metodologia


Foi desenvolvido um programa de jogo de poker na modalidade no-limit que aceita jogadores genéricos, que pode ser um jogador humano, que pega as entradas do teclado, quatro jogadores estáticos – constante, aleatório, MFS e RH, e um jogador evolutivo – aprendizado por reforço. Todos esses jogadores jogam entre si milhares de vezes e de diversas formas possíveis: mesas entre 2 a 10 jogadores e com jogadores aleatoriamente escolhidos tanto no treinamento como na verificação de desempenho dos jogadores. Em todos os jogos, o valor de dinheiro inicial foi 1000 e o valor do small blind foi 10.
    1. 2.1. Treinamento


O treinamento dos jogadores deveria ser rápido para se tornar viável a tentativa de diversas formas de treinamento. A estratégia utilizada para o treinamento com este objetivo foi dividir em duas etapas onde a primeira etapa é feita apenas uma vez e a segunda etapa, que necessita de muitos ajustes, é feita muitas vezes.

A primeira etapa foi registrar um histórico de jogos, decisões e recompensas. Nessa base foi registrado todos as decisões de jogadores com diferentes métodos em vários jogos e a recompensa daquela decisão, que só é preenchida no final do jogo e é replicada para todas as ações que levaram àquele recompensa. A informação contida nessa base é a seguinte:



Tabela 1. dimensões do estado do jogo


Nome

Descrição

POT

Soma da quantidade de dinheiro apostado por todos

ODDS

Relação do POT com o dinheiro apostado

RAISE

Quantidade de dinheiro que precisa usar para continuar no jogo

CHANCE

Probabilidade de vencer o jogo quando todos mostram as cartas

ROUND

Em que rodada - pre-flop, flop, turn ou river - o jogo se encontra

FOLLOWERS

Número de jogadores que ainda vão decidir na rodada atual

INGAME

Número de jogadores que não fugiram nem saíram

NPLAYERS

Número de jogadores

QTYPLAYERS

Quantidade de BET / RAISE feito por todos

As informações contidas no estado do jogo ainda não comentadas são o ODDS, o FOLLOWERS, o INGAME, o NPLAYERS e o QTYRAISE. ODDS é apenas a relação do dinheiro do POT em relação ao dinheiro apostado, por exemplo, um ODDS igual a 5 significa que tem no POT 5 vezes o valor apostado pelo jogador. O FOLLOWERS indica quantos jogadores ainda vão decidir algo. Isso porque o último a decidir tem vantagem em relação ao primeiro a decidir porque o último já sabe quem aumentou e quem não. INGAME indica quantos jogadores ainda não fugiram. NPLAYERS indica quantos jogadores estão jogando, independente de ter fugido, falido ou ainda estar em jogo. O QTYRAISE indica a quantidade de vezes que algum jogador aumentou a aposta e é importante porque jogos que houveram muito aumento de aposta pode indicar que muitos jogadores estão com boas chances de vencer.

Depois de preenchida essa base de dados com milhares de decisões, foi iniciado a segunda etapa, que consiste em passar para todos os jogadores informações de treinamento que são essas informações do histórico de jogos. Os jogadores estáticos ignoram essa informação assim como os humanos. Um exemplo de uma linha de informação dessa base de dados: primeira rodada, chance de vencer de 30%, POT de 50, ODDS de 3, é necessário pagar 20 para continuar no jogo, foi tomada a decisão de RAISE 40, recompensa de 50.

    1. 2.2. Implementação dos Jogadores Artificiais


Para tomar uma decisão, cada jogador tem como entrada o estado do jogo, que é multidimensional e suas dimensões são as mesmas informações guardadas na base de dados, que são: POT, ODDS, RAISE, CHANCE, ROUND, FOLLOWERS, INGAME, NPLAYERS, QTYRAISE.

Para simplificar a implementação e o treinamento dos jogadores, foi estabelecido que cada jogador tem como saída da ação 'tomar uma decisão' um valor discreto entre 1 e 6, que é a decisão discretizada:



Tabela 2. decisão discretizada


Código

Descrição

1

Fugir

2

Continuar no jogo

3

Aumentar pouco: equivalente a 2 a 4 small blind

4

Aumentar médio: equivalente a 6 a 18 small blind

5

Aumentar muito: equivalente a 20 a 40 small blind

6

Aumentar tudo: all-in



    1. 2.2.1. Jogadores Aleatórios


Esses jogadores tomam a decisão discretizada aleatória na seguinte proporção: 11% para cada decisão sendo que a decisão de continuar o jogo tem a proporção de 44%.
    1. 2.2.2. Jogadores Constantes


Esses jogadores tomam sempre a mesma decisão discretizada.
    1. 2.2.3. Jogadores MFS – Mathematically Fair Strategy


Esses jogadores (FINDLER, 1977) tomam a decisão discretizada definida por na fórmula:



Onde V é a relação MFS e T é uma constante. M é a quantidade de dinheiro do adversário, P é o POT, O é o ODDS, R é o RAISE, E é a quantidade de dinheiro apostado pelo jogador e C é a CHANCE em porcentagem e D é a decisão discretizada. Caso o O, que é o ODDS, seja igual a zero, significa começo de jogo onde o jogador não apostou nada ainda. Nesse caso, a decisão dele é sempre entrar no jogo.
    1. 2.2.4 Jogadores RH – Jean Rachlin e Gary Higgins


Esses jogadores (FINDLER, 1977) tomam a decisão discretizada definida por :



Onde V é a relação RH, P é o POT, R é o número de vezes que alguém decidiu RAISE / BET, F é o número de jogadores que ainda vão jogar nesta rodada, L é o número de jogadores que não fugiram, R é o RAISE, T é uma constante e D é a decisão discretizada.
    1. 2.2.5 Jogadores com Aprendizado por Reforço


Jogadores com aprendizado por reforço (SUTTON; BARTO, 2008, WIKIPEDIA REINFORCEMENT LEARNING, 2008) tem uma matriz com o número de dimensões iguais ao número de dimensões do estado do jogo. Cada dimensão tem uma quantidade de níveis e um intervalo correspondente a cada nível e o estado do jogo se enquadrará em um nível se o intervalo do estado corresponder àquele nível. Por exemplo, se a dimensão POT da matriz tem 7 níveis e cada nível tem o intervalo de 13,3, um estado do jogo em que o POT esteja em 29 se enquadrará no 3º nível desta dimensão da matriz porque o 1º nível vai de 0 a 13,3 e o 2º nível vai de 13,3 a 26,6. Caso o valor da dimensão do estado do jogo seja maior que o limite da matriz, esse valor é colocado no último nível. Além destas dimensões, a matriz tem mais duas dimensões, uma para indicar a decisão tomada e outra para indicar se o resultado foi prejuízo ou lucro. O conteúdo de cada célula da matriz é os resultados referentes àquele estado do jogo.

No treinamento, a decisão e a consequência, que é o dinheiro ganho ou perdido, é salvo na posição referente ao estado do jogo.



Na hora de tomar uma decisão, a matriz na posição referente ao estado do jogo é consultada e obtém uma lista de pares decisão discretizada e recompensa. Com essa lista, toma-se uma decisão que obtiver a maior média de recompensas por jogo.




Figura 1. Exemplo de uma situação de jogo que o jogador por reforço consulta sua base de conhecimento e decide 2, que significa “continuar no jogo”.
O jogador de aprendizado por reforço contem várias constantes que precisam de ajustes. Elas representam o intervalo que cada nível da matriz interna desse jogador que contem as nove dimensões - CHANCE, POT, RAISE, ODD, QTYRAISE, NPLAYERS, FOLLOWERS, ROUND e INGAME, com exceção da dimensão ROUND, que já foi pré-definida como tamanho 2, sendo o primeiro referente a primeira rodada e o segundo referente as demais rodadas. Cada dimensão deveria ter duas constantes: uma para o intervalo e outra para a quantidade de níveis mas, para simplificar, existe apenas duas constantes “quantidade de níveis”, uma para ODDS, POT, RAISE e CHANCE, chamado de “BIG QTY” e outra para QTYRAISE, NPLAYERS, FOLLOWERS e INGAME, chamada de “LITTLE QTY”, que totaliza dez constantes. Se cada variável fossem testados apenas 5 valores diferentes, a quantidade de testes seria , o que impossibilita testar todos os casos. Para encontrar uma boa configuração destas constantes foi utilizado Algoritmo Genético (HOLLAND, 1972, RUSSEL; NORVIG, 1995)..

A função fitness do algoritmo genético é a soma da quantidade vitórias diversas disputas, cada disputa com dez mesas, com o Jogador por Reforço usando 10 milhões de dados preenchidos na sua matriz interna. Foram usadas sete disputas, uma contra o jogador MFS com constante T = 1, uma contra o MFS com T=5, uma contra o Jogador Aleatório, uma contra o Jogador Constante que decide “continuar”, uma contra o Jogador Constante que decide “aumentar muito”, uma contra o Jogador RH com constante T=0,1 e uma contra o Jogador RH com T=0,001. O resultado da função fitness é a soma ponderada de vitórias das disputas com peso 2 contra o Jogador MFS, peso 1 contra o Jogador Constante, peso 1 contra o Jogador RH e peso 4 contra o Jogador Aleatório. A população tem tamanho 10 e a reprodução é feita na seguinte proporção: os 2 melhores sobrevivem para a próxima geração, 1 é mutação e 7 são produtos de crossover. Cada gene é uma constante e a população inicial é aleatória. A função de seleção escolhida foi a stochastic uniform (MATLAB, 2008). Essa função gera uma linha onde cada indivíduo tem um pedaço da linha proporcional ao fitness. Um ponto aleatório da linha é selecionado e o indivíduo que estiver naquela faixa da linha é o primeiro pai escolhido. Os outros pais são selecionados pela distribuição uniforme de pontos pela linha, igualmente espaçados.







Pot

Chance

Raise

Odds

QtyRaise

Followers

Ingame

Nplayers

LQ

BQ

Pai 1

14

5

7

9

1

4

3

8

3

7

Pai 2

27

20

3

2

4

1

2

3

5

10

Filho

27

20

7

9

1

1

3

3

3

7

Figura 2. Exemplo de uma situação de jogo que o jogador por reforço consulta sua base de conhecimento e decide 2, que significa “continuar no jogo”.
de jogadores que não fugiram, R é o RAISE, T é uma constante e D é a decisão discretizada.
    1. 3. Resultados


Não houve um algoritmo predominantemente vencedor. Houve apenas um que venceu, na média, mais que outro em uma disputa de todos contra todos. Mas em disputas individuais, que é um método contra outro, houve o caso do Reforço vencer o MFS que venceu o RH que venceu o Reforço, o que não deixou de continuar sendo o reforço o jogador favorito por ter vencido a maioria das disputas individuais. O jogador MFS obteve resultados muito bons em disputas individuais e os outros jogadores tiveram os piores resultados. Durante os experimentos o jogador MFS obteve resultados muito bons e demorou até que um jogador evolutivo conseguisse vencê-lo.

Figura 3. Resultado da disputa entre todos os jogadores

  1. 4. Conclusão


Os resultados foram abaixo da expectativa, que era do jogador por reforço ganhar muito mais que perder dos outros tipos de jogadores, que são decisões de fórmulas simples. Todos os resultados foram obtidos de simulações artificiais e uma base de dados com jogadas humanas pode aumentar a chance de vitória dos algoritmos evolutivos. Um problema em melhorar os algoritmos é o tempo de processamento necessário pois milhares de jogos precisam ser feitos para evoluir um jogador e pode demorar muito até verificar se um método é melhor que outro. Outro problema é que métodos artificiais que vencem métodos artificiais não necessariamente jogam bem contra jogadores humanos e uma bateria de teste com jogadores humanos é ainda mais demorado. Mesmo assim o resultado final foi um jogador que jogou razoavelmente bem.
  1. Referências


FINDLER, Nicholas V.. Studies in Machine Cognition Using the Game of Poker. State University Of New York At Buffalo: R. J. Hanson, 1977.

HOLLAND, John H.. Genetic Algorithms and the Optimal Allocation of Trials. Siam Journal On Computing, Philadelphia, n. 2 , p.88-105, 3 ago. 1972.

JOHANSON, Michael Bradley. Robust Strategies and Counter-Strategies: Building a Champion Level Computer Poker Player. 2007. 97 f. Tese (Mestrado) - University Of Alberta, Alberta, 2007.

MATLAB (Org.). The MathWorks: MATLAB and Simulink for Technical Computing. Disponível em: . Acesso em 1 out. 2008.

POKERLOCO (Org.). Como Jogar Poker: Resumo. Disponível em: . Acesso em: 1 out. 2008.

RUSSEL, Stuart J.; NORVIG, Peter. Artificial Intelligence: A Modern Approach. New Jersey: Prentice Hall, 1995.

SUTTON, Richard S.; BARTO, Andrew G.. Reinforcement Learning: An Introdution. E-Book. Disponível em: . Acesso em: 1 out. 2008.

WIKIPEDIA POKER (Org.). Poker. From Wikipedia, the free encyclopedia. Disponível em: . Acesso em: 1 out. 2008.

WIKIPEDIA REINFORCEMENT LEARNING (Org.). Reinforcement Learning. From Wikipedia, the free encyclopedia. Disponível em: . Acesso em: 1 out. 2008.

1   2   3   4   5   6


©livred.info 2017
enviar mensagem

    Página principal