Jogo do Galo: um exercício em programação descendente

Todos conhecemos o Jogo do Galo (que os ingleses chamam de Tic-Tac-Toe). O objectivo deste post é mostrar como podemos desenvolver um programa simples para permitir um humano jogar contra o computador. Mas o nosso interesse não é tanto no jogo, mas mais em ilustrar como podemos chegar à versão final, funcional, do programa de forma segura, tomando a cada momento as decisões mínimas que nos ajudem na sua construção. Chama-se a isso Construção Descendente de Programas. Vamos a isso.

Existem muitos aspectos a considerar no problema, mas se esquecermos os detalhes podemos propor uma primeira versão do nosso programa:

def tic_tac_toe_0(n):
    # inicializa tabuleiro
    # mostra tabuleiro
    # define jogador
    while True : # não há vencedor ou empate
        if True: # humano
            # pede jogada
            # actualiza tabuleiro
            pass
        else:
            # define jogada
            # actualiza tabuleiro
            pass
        # mostra tabuleiro
        # Vencedor ou empate --> termina
        # comuta jogador
    # mensagem final

Como se pode ver o jogo começa essencialmente por construir um tabuleiro e definir quem é o jogador que começa. Depois entramos num ciclo em que os jogadores jogam alternadamente enquanto não houver vencedor ou o jogo estar empatado. Podemos avançar um pouco começando por definir as partes que envolvem criar um tabuleiro e mostrar o tabuleiro.

def tic_tac_toe_1(n):
    # inicializa tabuleiro
    tabuleiro = inicializa_tabuleiro(n)
    # mostra tabuleiro
    mostra_tabuleiro(tabuleiro)
    # define jogador
    while True : # não há vencedor ou empate
        if True: # humano
            # pede jogada
            # actualiza tabuleiro
            pass
        else:
            # define jogada
            # actualiza tabuleiro
            pass
        # mostra tabuleiro
        mostra_tabuleiro(tabuleiro)
        # Vencedor ou empate --> termina
        # comuta jogador
    # mensagem final

Agora precisamos definir as novas funções. Para isso, é necessário decidir a representação para o tabuleiro. Optamos por uma lista de listas. Assim podemos facilmente modificar o seu conteúdo. Cada célula do tabuleiro, um elemento da lista de listas, poderá ter um de três valores: 0, quando está vazia, ‘X’ ou ‘O’ para a marca de cada jogador.

Começando pela inicialização do tabuleiro, podemos optar pela solução trivial:

def inicializa_tabuleiro_0(n):
    tabuleiro = []
    for i in range(n):
        # linha i
        linha_i = []
        for j in range(n):
            linha_i += [0]
        tabuleiro += [linha_i]
    return tabuleiro

Dois ciclos. O externo trata das linhas, o interno das colunas para cada linha. Uma alternativa:

def inicializa_tabuleiro(n):
    tabuleiro = []
    for i in range(n):
        # linha i
        tabuleiro += [[0] * n]
    return tabuleiro

Quem já conhece as listas por compreensão poderia optar por:

def inicializa_tabuleiro(n):
    return [[0] * n for i in range(n)]

Agora mostrar o tabuleiro. A solução banal:

def mostra_tabuleiro(tabuleiro):
    print(tabuleiro)

Esta solução esquece a natureza bi-dimensional do tabuleiro. Mas isso pode-se resolver, ainda de modo simples:

def mostra_tabuleiro(tabuleiro):
    for linha in tabuleiro:
        for valor in linha:
            print(valor,'  ',end='')
        print()

E agora? Que fazer? Vamos definir o jogador:

def define_jogador():
    import random
    return random.choice(‘XO')

Notar onde é feita a importação do módulo. Isso tem consequências. Sabe quais são, certo? Com este modo de proceder, avançamos para uma versão mais detalhada:

def tic_tac_toe_2(n):
    # inicializa tabuleiro
    tabuleiro = inicializa_tabuleiro(n)
    # mostra tabuleiro
    mostra_tabuleiro(tabuleiro)
    # define jogador
    jogador = define_jogador()
    while True : # não há vencedor ou empate
        if jogador == 'X': # humano
            # pede jogada
            # actualiza tabuleiro
            pass
        else:
            # define jogada
            # actualiza tabuleiro
            pass
        # mostra tabuleiro
        mostra_tabuleiro(tabuleiro)
        # Vencedor ou empate --> termina
        # comuta jogador
        if jogador == 'X':
            return 'O'
        else:
            return 'X'        
    # mensagem final 

Está na hora de resolver o problema do conceito de jogada. Vamos admitir que jogar é simplesmente indicar as coordenadas da célula onde se pretende jogar. Existe uma diferença entre ser o humano ou ser o computador. No primeiro caso o programa dever pedir ao humano essas coordenadas:

def pede_jogada(tabuleiro):
    jogada = eval(input('A sua jogada (x,y)?: '))
    while not possivel(tabuleiro,jogada):
        print('Jogada ilegal...')
        jogada = eval(input('A sua jogada (x,y)?: '))
    return jogada


def possivel(tabuleiro,jogada):
    return tabuleiro[jogada[0]][jogada[1]] == 0

Só estamos a proteger o programa contra tentavas de jogar numa célula já ocupada…. No caso do computador a jogar podemos definir definir diferentes estratégias. apresentamos duas: numa, o computador procura por uma certa ordem a primeira posição disponível; na outra, o computador escolhe aleatoriamente uma de entre as disponíveis.

def joga_computador(tabuleiro):
    """Escolha por ordem"""
    for i in range(len(tabuleiro)):
        for j in range(len(tabuleiro[0])):
            if tabuleiro[i][j] == 0:
                return i,j
            
def joga_computador_b(tabuleiro):
    import random
    """Escolha aleatória"""
    livres = []
    for i in range(len(tabuleiro)):
        for j in range(len(tabuleiro[0])):
            if tabuleiro[i][j] == 0:
                livres += [(i,j)]
    return random.choice(livres)

Daqui resulta uma nova aproximação.

def tic_tac_toe_3(n):
    # inicializa tabuleiro
    tabuleiro = inicializa_tabuleiro(n)
    # mostra tabuleiro
    mostra_tabuleiro(tabuleiro)
    # define jogador X (humano)  ou O (computador)
    jogador = define_jogador()
    while True: # não há vencedor ou empate
        if jogador == 'X': # humano
            print('Joga Humano')
            # pede jogada
            jogada = pede_jogada(tabuleiro)
            # actualiza tabuleiro
        else:
            print('Joga computador')
            # define jogada
            jogada = joga_computador_b(tabuleiro)
            # actualiza tabuleiro
        # mostra tabuleiro
        mostra_tabuleiro(tabuleiro)
        # Vencedor ou empate --> termina
        # comuta jogador
        jogador = comuta_jogador(jogador)
    # mensagem final

Com o conceito de jogada definido podemos passar à actualização do tabuleiro. Como temos que colocar marcas diferentes, a função vai ter três parâmetros: o tabuleiro, a jogada (a posição) e a marca:

def actualiza_tabuleiro(tabuleiro, jogada, jogador):
    if jogador == 'X':
        tabuleiro[jogada[0]][jogada[1]] = 'X'
    else:
        tabuleiro[jogada[0]][jogada[1]] = 'O'
    return tabuleiro

E aproximamo-nos do final:

def tic_tac_toe_4(n):
    # inicializa tabuleiro
    tabuleiro = inicializa_tabuleiro(n)
    # mostra tabuleiro
    mostra_tabuleiro(tabuleiro)
    # define jogador X (humano)  ou O (computador)
    jogador = define_jogador()
    while True: # não há vencedor ou empate
        if jogador == 'X': # humano
            print('Joga Humano')
            # pede jogada
            jogada = pede_jogada(tabuleiro)
            # actualiza tabuleiro
            tabuleiro = actualiza_tabuleiro(tabuleiro,jogada,jogador)
        else:
            print('Joga computador')
            # define jogada
            jogada = joga_computador_b(tabuleiro)
            # actualiza tabuleiro
            tabuleiro = actualiza_tabuleiro(tabuleiro,jogada,jogador)
        # mostra tabuleiro
        mostra_tabuleiro(tabuleiro)
        # Vencedor ou empate --> termina
        # comuta jogador
        jogador = comuta_jogador(jogador)
    # mensagem final

Vamos tratar agora de uma parte mais difícil: Determinar se há vencedor ou se o jogo está empatado. Comecemos pela primeira questão. Haverá vencedor se um jogador tiver N marcas consecutivas, numa linha ou numa coluna ou numa diagonal. Vamos então separar estas três verificações, parando mal uma delas nos permita tirar conclusões. Então:

def vencedor(tabuleiro,jogador):
    return vence_linhas(tabuleiro,jogador) or vence_colunas(tabuleiro, jogador) or vence_diagonais(tabuleiro, jogador)

def vence_linhas(tabuleiro,jogador):
    for i in range(len(tabuleiro)):
        vence = True
        for j in range(len(tabuleiro[0])):
            vence = vence and (tabuleiro[i][j] == jogador)
        if vence:
            return True
    return False
        
def vence_colunas(tabuleiro,jogador):
    for i in range(len(tabuleiro[0])):
        vence = True
        for j in range(len(tabuleiro)):
            vence = vence and (tabuleiro[j][i] == jogador)
        if vence:
            return True
    return False

def vence_diagonais(tabuleiro,jogador):
    vence_1 = True
    vence_2 = True
    # diagonal principal
    for i in range(len(tabuleiro)):
        vence_1 = vence_1 and (tabuleiro[i][i] == jogador)
        vence_2 = vence_2 and (tabuleiro[i][len(tabuleiro)-1-i] == jogador)
    return vence_1 or vence_2

A verificaão de empate é mais simples:

def empate(tabuleiro):
    for i in range(len(tabuleiro)):
        for j in range(len(tabuleiro[0])):
            if tabuleiro[i][j] == 0:
                return False
    return True

Tome atenção sobretudo ao caso das diagonais e ao modo como calculamos as respectivas posições. Para concluir, só nos falta a mensagem final. Vamos colocá-la no programa e mostar a versão final.

def tic_tac_toe(n):
    # inicializa tabuleiro
    tabuleiro = inicializa_tabuleiro(n)
    # mostra tabuleiro
    mostra_tabuleiro(tabuleiro)
    # define jogador X (humano)  ou O (computador)
    jogador = define_jogador()
    while True: # não há vencedor ou empate
        if jogador == 'X': # humano
            print('Joga Humano')
            # pede jogada
            jogada = pede_jogada(tabuleiro)
            # actualiza tabuleiro
            tabuleiro = actualiza_tabuleiro(tabuleiro,jogada,jogador)
        else:
            print('Joga computador')
            # define jogada
            jogada = joga_computador_b(tabuleiro)
            # actualiza tabuleiro
            tabuleiro = actualiza_tabuleiro(tabuleiro,jogada,jogador)
        # mostra tabuleiro
        mostra_tabuleiro(tabuleiro)
        # Vencedor ou empate --> termina
        if vencedor(tabuleiro,jogador) or empate(tabuleiro):
            break
        # comuta jogador
        jogador = comuta_jogador(jogador)
    # mensagem final
    print('Finito...')
    if empate(tabuleiro):
        print('Fica para o próximo jogo!')
    elif jogador == 'X':
        print('Parabéns humanóide!')
    else:
        print('Parabéns Computador')

Agora já só falta … jogar. Ou quase. Se quiser melhorar o desempenho do computador, tem que pensar numa estratégia diferente O programa seguinte mostra uma hipótese. Não quer completar??

def joga_computador_c(tabuleiro):
    if pode_ganhar_computador(tabuleiro):
        # joga para aí
        pass
    elif pode_ganhar_humano(tabuleiro):
        # bloqueia
        pass
    elif livre_centro():
        # joga centro
        pass
    elif livre_canto():
        # joga_canto
        pass
    else:
        # joga
        pass

Moral da história: devagar se vai ao longe ou a complexidade domina-se dividindo um problema em sub-problemas mais simples.