Jogo da velha
Foto por Teresa Stanton

O jogo da velha, conhecido também por Tic tac toe, é um jogo bem simples e muito utilizado para aplicar conhecimentos básicos da Inteligência Artificial (AI) e Teoria da decisão ou Minimax.

"Quanta coisa pode-se aprender com um simples jogo da velha."

Trata-se de um jogo composto por um tabuleiro de matriz três linhas por três colunas onde dois jogadores se enfrentam. Ganha o jogador que conseguir três círculos ou três xis em linha, seja vertical, horizontal ou diagonal.

O jogo foi desenvolvido na linguagem de programação PHP e pode ser executado por linha de comando ou no navegador. Recomendo executar o jogo na linha de comando para acompanhar cada jogada atentamente com o Delay de três segundos entre as jogadas. Se for executar no navegador, altere o intervalo para zero ou pode demorar até vinte e sete segundos para você visualizar algo.

Quem joga?

Diferente do que você está acustumado, a partida é disputada por códigos, programas ou agentes inteligentes. Cada um programa o seu jogador e depois os programas se enfrentam.

A Inteligência Artificial

O jogo da velha pode ser dividido e tratado em agente e ambiente. O agente é o jogador, percebe o seu ambiente por meio de sensores, que são os parâmetros, e age sobre o ambiente por intermédio de atuadores, o valor retornado com as coordenadas da jogada.

O ambiente é definido como:

Completamente observável

Os agentes tem acesso ao estado completo do ambiente. Os sensores detectam todos os aspectos que são relevantes para a escolha da ação. A cada jogada o jogador recebe a matriz do tabuleiro atualizada.

Estratégico

O próximo estado do ambiente é completamente determinado pelo estado atual e pela ação executada pelos agentes.

Seqüencial

A decisão afeta todas as ações futuras. Ações em curto prazo podem ter conseqüências a longo prazo. O jogador faz uma jogada, o próximo jogador pode dar continuidade a sua jogada anterior, como também se defender ou iniciar uma nova jogada.

Estático

O ambiente não se altera enquanto o agente está decidindo sobre a realização de uma ação, nem precisa se preocupar com a passagem do tempo.

Discreto

O ambiente tem um número finito de estados distintos, também tem um número discreto de percepções e ações.

Multiagente

O agente está em um ambiente de dois agentes, o jogo precisa de dois jogadores pra disputar a partida.

Eu diria que existe dois tipos de agentes inteligentes para o jogo da velha: o agente que faz a melhor jogada analisando a situação atual, não significa que para sua próxima jogada o seu movimento atual vai ser realmente útil; e o agente que planeja suas jogadas, o agente qua age com estratégia. O agente que faz a melhor jogada olha para o tabuleiro e se pergunta "O que pode me fazer ganhar ou perder?". Já o agente estratégico pode fazer jogadas que aparentemente não tem sentido, mas que futuramente vão decidir a partida.

Teoria da decisão, Minimax ou Minmax

Minimax lida com jogos como o jogo da velha, no qual cada jogador pode ganhar, perder ou empatar. Se o jogador A pode vencer com um movimento, seu melhor movimento é o movimento para a vitória. Se o jogador B identifica que um movimento levará a uma situação em que o adversário pode ganhar em um movimento, enquanto outro movimento levará a uma situação de empate, então a melhor jogada do jogador B é a que leva para o empate. Após algumas rodadas é fácil identificar qual é o melhor movimento. O algoritmo minimax ajuda a encontrar a melhor jogada ao caminhar pelas opções válidas a partir do fim do jogo. A cada passo assume-se que o jogador A está tentando maximizar as chances de A ganhar, enquanto na próxima rodada o jogador B está tentando minimizar as chances de isso acontecer (ao maximizar as chances de que ele próprio ganhe).

É a sua vez de jogar, o que você escolheria? Fazer um movimento de defesa impedindo que oponente vença na próxima jogada, iniciar um nova estratégia, continuar com a sua estratégia de jogadas anteriores ou fazer o movimento para a vitória? Separe os tipos de jogadas e estabeleça prioridades. É preferível vencer que impedir que o adversário vença na próxima jogada.

O Jogo

Tictactoe

Tictactoe é responsável pelas regras e execução do jogo. Os jogadores são inseridos no tabuleiro e o jogo é iniciado.

As regras do jogo são bem simples:

• O tabuleiro é uma matriz quadrada de três linhas por três colunas (3x3). O valor mínimo e máximo para a coordenada é respectivamente 0 e 2.
• Em cada jogada o jogador recebe por parâmetro a matriz atualizada do tabuleiro e a sua marcação, caractere "x" (xis) ou "o" (círculo).
• Se em sua jogada o jogador não retornar um coordenada válida ou a coordenada já tiver ocupada o openente vence.
• O jogador vence quando conseguir três "o" (círculos) ou três "x" (xis) em linha, seja vertical, horizontal ou diagonal.

É um pouco rígido dar a vitória ao oponente se o jogador cometer qualquer deslize, como fazer uma jogada onde já foi marcado. Em uma partida jogada por seres humanos a vez não passa até que o jogador marque corretamente no tabuleiro. Então, por que dar a vitória ao oponente quando um ser humano tem inúmeros tentativas? Porque são códigos que estão competindo, o objetivo não é ver quem responde em três ou mais tentativas e sim qual é o melhor algoritmo.

O Tabuleiro

/**
 * @author Alejandro Fernandez Moraga <moraga86@gmail.com>
 */

class Tictactoe {
	
	private $board = array(0 => array(null, null, null), 1 => array(null, null, null), 2 => array(null, null, null));
	private $players = array();
	
	public function setPlayers(Player $player1, Player $player2) {
		$this->players = array('x' => $player1, 'o' => $player2);
	}
	
	private function register($position, $cursor) {
		if (!is_array($position) || count($position) < 2)
			throw new Exception('invalid data');
			
		$row = array_shift($position);
		$col = array_shift($position);
		
		if (!is_numeric($row) || !is_numeric($col))
			throw new Exception('only numbers are accepted');

		if ($row > 2 || $col > 2)
			throw new Exception(sprintf('invalid coords (%d,%d)', $row, $col));
		
		if (!is_null($this->board[$row][$col]))
			throw new Exception(sprintf('invalid position (%d,%d)', $row, $col));
		$this->board[$row][$col] = $cursor;
		return true;
	}
	
	private function printBoard() {
		for ($i=0; $i < 3; $i++)
			echo implode(' | ', $this->board[$i])."\n";
		echo "\n";
	}
	
	private function has_winner() {
		$d1 = array();
		$d2 = array();
		for ($i=0; $i < 3; $i++) {
			$h = array();
			$v = array();
			for ($j=0; $j < 3; $j++) {
				# horizontal
				if ($h !== false && !is_null($this->board[$i][$j]) && (count($h) == 0 || in_array($this->board[$i][$j], $h)))
					$h[] = $this->board[$i][$j];
				else
					$h = false;
				# vertical	
				if ($v !== false && !is_null($this->board[$j][$i]) && (count($v) == 0 || in_array($this->board[$j][$i], $v)))
					$v[] = $this->board[$j][$i];
				else
					$v = false;
				# diagonal 1
				if ($i - $j == 0 && (count($d1) == 0 || in_array($this->board[$i][$j], $d1)))
					$d1[] = $this->board[$i][$j];
				# diagonal 2
				if ($i + $j == 2 && (count($d2) == 0 || in_array($this->board[$i][$j], $d2)))
					$d2[] = $this->board[$i][$j];
			}
			if ($h)
				return $this->players[$h[0]];
			if ($v)
				return $this->players[$v[0]];
		}

		if (count($d1) == 3)
			return $this->players[$d1[0]];

		if (count($d2) == 3)
			return $this->players[$d2[0]];

		return false;
	}
	
	public function run($sleep=3) {
		$playing = 'x';
		$moves = 0;
		while (true) {
			if ($moves == 9)
				break;
			try {
				$this->register($this->players[$playing]->move($this->board, $playing), $playing);
				$this->printBoard();
				$playing = ($playing == 'x' ? 'o' : 'x');
				$moves++;
				sleep($sleep);
				if ($moves >= 5)
					if ($winner = $this->has_winner())
						break;
			}
			catch (Exception $e) {
				exit(sprintf('Player %s lost: %s', get_class($this->players[$playing]), $e->getMessage()));
			}
		}
		exit(($winner ? 'Winner: '.get_class($winner) : 'draw')."\n");
	}
}

Interface Player - Interface do jogador

Os jogadores devem implementar a Interface Player. O método move é executado a cada jogada e deve retornar um Array com as coordenadas da jogada. O jogador recebe a matriz com a situação atual do tabuleiro ($board) e a sua marcação ($cursor) por parâmetros.

Implementar a interface não só é necessário para definir o método move, o tabuleiro só aceita jogadores do tipo Player.

A interface define um tipo em comum para os objetos jogadores e o método que devem implementar. Na programação, a interface não precisa necessariamente definir métodos, pode ter zero assim como inúmeros.

interface Player {
	public function move($board, $cursor);
}

Player Bootdon

Bootdon é um jogador randômico, aposta na sorte. Lê o tabuleiro, armazena todas as posições livres e depois sorteia uma jogada. A chance do Bootdon ganhar uma partida contra um jogador bem programado é muito baixa, ele foi construído para ser o seu adversário enquanto programa o seu jogador.

class Bootdon implements Player {
	public function move($board, $cursor) {
		$nulls = array();
		for ($i=0; $i < 3; $i++)
			for ($j=0; $j < 3; $j++)
				if (is_null($board[$i][$j]))
					$nulls[] = array($i, $j);
		return $nulls[rand(0, count($nulls) - 1)];
	}
}

Exemplos

Para linha de comando

$game = new Tictactoe();
$game->setPlayers(new Bootdon(), new Bootdon());
$game->run(); // intervalo de 3 segundos para cada jogada

Para navegador

$game = new Tictactoe();
$game->setPlayers(new Bootdon(), new Bootdon());

echo '<pre>';
$game->run(0); // sem intervalo
echo '</pre>';

Código fonte e Download

• Ver o Código fonte no formato .txt
• Baixar o Código fonte no formato .zip