IA para o jogo Três! por Sirvo LLC. Você pode obter o jogo aqui: http://asherv.com/threes/
Construir esta IA foi a inspiração para minha IA posterior de 2048, e algumas das ideias da IA de 2048 também foram transferidas para esta IA.
Embora eu não tenha avaliado formalmente o desempenho desta IA (ainda), sei que ela atingiu com sucesso o bloco 6144 várias vezes, que é o bloco mais alto disponível no jogo. (Telhas mais altas são possíveis, mas improváveis, devido aos fortes efeitos aleatórios). A pontuação máxima (no momento da redação) é de 775.524 pontos:
Esta IA é muito mais experimental do que seu irmão mais novo, 2048 AI, devido à maior complexidade do Três! e porque não recebeu tanto tempo de desenvolvimento. Além disso, Três! em geral, é um alvo móvel, já que os algoritmos de geração de blocos aleatórios são ocasionalmente ajustados, necessitando de mudanças na IA.
O algoritmo para esta IA já está essencialmente detalhado nesta resposta do StackOverflow que descreve minha IA 2048. Em essência, ele implementa uma pesquisa de força bruta altamente otimizada na árvore do jogo (todos os movimentos possíveis, valores de geração de blocos e valores de blocos), usando a otimização expectimax para combinar os resultados e encontrar o "melhor" movimento possível.
Esta IA Threes é na verdade mais sofisticada do que a IA 2048 de várias maneiras: mais notavelmente, ela leva em conta o "baralho" das próximas peças (o processo bem documentado pelo qual as peças aleatórias recebidas são selecionadas) e lida adequadamente com todos os locais possíveis de geração de peças com base nos movimentos feitos. Resumindo: esta IA do Threes emula corretamente (até onde sei) todos os detalhes do jogo Threes como parte do processo de otimização expectimax.
A maneira mais fácil de colocar a IA em execução é clonar uma das ramificações prebuilt/ correspondentes ao seu sistema operacional e processador. Essas ramificações possuem binários pré-construídos no diretório bin/ .
Observe que o Python "padrão" no Windows é de 32 bits, enquanto o Python "padrão" no OS X e Linux é de 64 bits. As compilações de 32 bits são marcadas como i386 enquanto as compilações de 64 bits são marcadas como x86_64 .
Se você quiser construí-lo a partir do código-fonte (por exemplo, se estiver fazendo alterações), siga as instruções abaixo.
Executar
./configure
make
em um terminal. Qualquer compilador C++ relativamente recente deve ser capaz de construir a saída.
Observe que você não faz make install ; este programa deve ser executado a partir deste diretório.
Você tem algumas opções, dependendo do que instalou.
Pure Cygwin: siga as instruções Unix/Linux/OS X acima. A DLL resultante só pode ser usada com programas Cygwin, portanto, para executar a versão de controle do navegador, você deve usar o Python Cygwin (não o Python python.org). Para obter instruções passo a passo, cortesia de Tamas Szell (@matukaa), consulte este documento.
Cygwin com MinGW: execute
CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make
em um shell MinGW ou Cygwin para construir. A DLL resultante pode ser usada com programas não Cygwin.
Visual Studio: abra um prompt de comando do Visual Studio, cd no diretório threes-ai e execute make-msvc.bat .
Você precisará do Python 2.7, NumPy e PIL para executar os programas Python.
Execute bin/threes se quiser ver a IA sozinha em ação.
Existem algumas versões do Threes baseadas na web, mas eu queria fazer a IA jogar contra o aplicativo real. Então, construí um programa "assistente" para dispositivos Android, chamado android_assistant.py , que se comunica com o telefone via ADB e faz movimentos de forma totalmente automática. Requer apenas permissões USB ADB (acesso padrão do desenvolvedor) e não requer root ou qualquer outra modificação do dispositivo ou aplicativo. Ele usa o utilitário screencap padrão do Android para obter o estado (visível) do jogo, calcula o movimento ideal e, em seguida, usa o subsistema de eventos de entrada do Linux para gerar eventos de furto.
Para usar android_assistant.py , você precisará configurar o subsistema OCR para o seu dispositivo. Você também terá que registrar eventos de furto para reprodução. Atualmente, dois dispositivos estão configurados: o LG Nexus 5 e o OnePlus One (correspondente aos telefones em que testei). Patches são bem-vindos para adicionar mais telefones.
Para configurar o sistema OCR, você deve adicionar uma entrada em ocr/devices.py correspondente ao seu dispositivo. O nome do modelo pode ser obtido simplesmente executando android_assistant.py enquanto estiver conectado ao dispositivo (deve haver erro com o nome do modelo esperado). Essencialmente, você precisará fazer uma captura de tela do jogo e derivar a posição do painel "próximo bloco", bem como a posição e o espaçamento da grade de blocos. (Esta parte provavelmente poderia usar mais automação e/ou simplificação!)
Para registrar eventos, basta executar python -m android.inputemu --record up down left right e executar o gesto apropriado em seu telefone quando solicitado.
O assistente manual é um Três de uso geral! assistente que funciona com qualquer implementação do Threes!. Você informa o tabuleiro e o próximo conjunto de peças, e o assistente calcula a melhor jogada.
Execute manual_assistant.py para iniciar o assistente manual.
Observe que o assistente manual espera ver movimentos sequenciais. Se você avançar (fazer movimentos sem o assistente), saia do assistente pressionando Ctrl+C e reinicie-o. Caso contrário, você poderá receber uma mensagem de erro como "situação impossível" se entrar em um quadro que não seja sequencial ao quadro anterior.
Ao entrar no próximo tabuleiro, você pode usar espaços, novas linhas e/ou vírgulas para separar as peças. Leia da esquerda para a direita e depois de cima para baixo. Insira um zero para espaços vazios. Entrada de exemplo:
Usando vírgulas e novas linhas:
96,2,3,0
2,1,1,0
2,1,0,0
0,0,2,0
Usando apenas vírgulas:
96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
Usando espaços:
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
Você também pode inserir um "delta" do quadro anterior. Especifique a linha ou coluna na qual a nova peça foi gerada e o valor da peça que foi gerada (você pode omitir isso se houver apenas uma possível nova peça no último movimento, por exemplo, se for vermelha ou azul). Especifique também o movimento que você fez, caso não tenha sido o movimento sugerido pela IA.
As colunas e linhas são numeradas da esquerda para a direita e de cima para baixo: a coluna 1 é a coluna da esquerda e a linha 1 é a linha superior.
Por exemplo, se o quadro for deslizado para cima e passar de
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
para
96 3 3 0
2 1 1 0
2 0 2 0
0 3 0 0
então você enviaria 2,3,up como tabuleiro (na 2ª coluna, um 3 apareceu). Se a IA tivesse recomendado o movimento up , você poderia simplesmente omitir isso e enviar 2,3 . Se o próximo bloco tivesse sido previsto como 3, você poderia omitir o 3 e enviar apenas 2 .
Ao inserir deltas, você economizará muito tempo. Na maioria dos casos, você só precisa inserir um número (a coluna/linha que foi alterada).
Ao inserir o próximo bloco, use um dos seguintes formatos:
blue (1), red (2) ou white (3+)1 , 2 , 3 , 3+ , 6+ ou, por exemplo, 24,48,96 , 24 48 963+ significa que pode ser 3 ou superior; use isso com Três mais velhos! que não mostram um sinal de "mais" nas peças de bônus6+ significa que é qualquer peça de bônus; use isto se o próximo bloco for "+"24,48,96 significa que é um desses três; use isso com Threes mais recentes! que mostram opções explícitas para o valor da peça de bônus.
