Othelo
Alunos:
Sávio Mendes de Figueiredo ([email protected])
Sômulo Nogueira Mafra ([email protected])
Prof.: Inês dutra
Inteligência artificial
Coppe sistemas - UFRJ
Índice
1.
2.
3.
4.
5.
6.
7.
8.
Origem do Jogo
Introdução
Regras
Como jogar
Heurística Posicional
Heurística Mobilidade
Conclusões
Bibliografia
Origem do Jogo
Este jogo foi inventado na Inglaterra, no final do século passado.
Também é conhecido como Reversi.
Introdução
O objetivo deste trabalho consiste na implementação de um
programa jogador de Othelo baseado no algoritmo Minimax com cortes
alfa-beta.
Em média, cada jogador no meio de uma partida possui 10 opções
de movimento. Sendo assim para realizar uma busca de profundidade 9
seria necessário investigar 9^10 posições. Por isso foi necessário utilizar
o corte alpha beta.
O trabalho foi implementado em C++ utilizando o ambiente Visual
C++ 6.0.
Regras
Othelo é um jogo de dois jogadores (azul e vermelho) e é normalmente
jogado num tabuleiro 8x8. O objetivo do jogo é preencher o tabuleiro com peças
de sua própria cor.
Você vence se ao final do jogo existirem mais peças da sua cor no
tabuleiro do que peças da cor do seu oponente. No ínicio do jogo, o tabuleiro
possui duas peças de cada jogador, colocadas diagonalmente em relação umas às
outras no centro do tabuleiro.
Cada jogador (na sua vez) coloca uma peça da sua cor no tabuleiro. Essa
jogada será válida se ela mudar a cor de pelo menos uma das peças do seu
oponente para a sua cor. Você pode fazer isto se quando vc colocar a peça no
tabuleiro, ela for colocada no fim de uma linha contínua de peças do seu
oponente, tendo no ínicio desta linha uma peça sua. Todas as peças desta linha
são então convertidas para sua cor. As linhas podem estar na vertical, diagonal
ou horizontal.
Regras (cont.)
Caso exista mais de uma linha de peças deste tipo, então todas as
peças dessas linhas serão convertidas para peças da sua cor.
Caso não exista nenhuma jogada possível, o jogador passa a vez
para o adversário.
O jogo termina quando o tabuleiro está totalmente preenchido ou
quando nenhum dos dois jogadores possuir uma jogada.
Como Jogar (Iniciando o Jogo)
Para iniciar uma partida na qual a primeira jogada será do usuário, basta
clicar na opção “Iniciar” do menu e depois na opção “Jogador”. Caso se queira
que a primeira jogada seja do computador, basta clicar na opção “Computador”.
Como Jogar (Movendo as peças)
O jogador humano joga sempre com as peças vermelhas. Para se
fazer uma jogada basta clicar com o botão esquerdo do mouse sobre a
posição do tabuleiro onde se deseja colocar a nova peça.
Esta posição que foi selecionada pelo mouse deve ser uma posição
válida como visto nas instruções.
Como Jogar (Selecionando nível)
Através da opção “Nível” do menu (“Fácil”, “Médio” ou
“Difícil”) é possível aumentar ou diminuir a dificuldade do jogo.
Na opção “Fácil”, é utilizada a profundidade 2 no algoritmo minmax, 4 na opção “Médio” e 6 na opção “Difícil”
Como Jogar (Selecionando heurística)
Através da opção “Estratégia” é selecionada a heurística que o
algoritmo irá utilizar na função de avaliação do tabuleiro. Existem duas
heurísticas disponíveis para escolha: “Posicional” e “Mobilidade”.
Heurística Posicional
Nesta heurística, para que eu possa calcular a força do tabuleiro
em um dado instante, eu vou atribuir os seguintes pesos às casas do
tabuleiro:
Logo, nesta heurística eu levo em consideração o número de peças de
cada jogador e o peso da peça devido à sua posição no tabuleiro.
Heurística Mobilidade
Nesta heurística, quantos mais movimentos eu puder fazer num
determinado tabuleiro, melhor será este tabuleiro.
Em outras palavras, para determinar a força do tabuleiro para um
determinado jogador (A por exemplo) eu faço a segunda conta:
numJogA – numJogB;
Onde numJogA é o número de possíveis jogadas do jogador A e
numJogB é o número de possíveis jogadas do jogador B.
Conclusões
Embora este jogo pareça ser bem mais simples que o jogo de
damas, até pelo fato de que nele não existem jogadas múltiplas, as
dificuldades encontradas foram bem parecidas.
Como exemplos de dificuldades podemos citar:
- encontrar funções heurísticas
- implementação do jogo própriamente dita (interface
gráfica, interação com o usuário, etc...)
- foi mais difícil encontrar informações relevantes
referentes a este jogo do que referentes ao jogo de damas.
Bibliografia
 Stuart Russel, Peter Norvig – Artificial Intelligence a Modern Approach
 http://www.geocities.com/jnkjavaconnection/othelo.html
 http://www.angelfire.com/tn/tanjeem/report.html