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.

Teste 2 - TP1

P1

Que variantes da instrução de atribuição usual ( = ) conhece? Resposta:

Existem três tipos de variantes para a forma explícita da instrução de atribuição: (a) aumentada: op= que equivale a = op por exemplo: x += 5

(b) em cadeia: x = y = … = que equivale a y = ; x = y para o caso de apenas dpis nomes. Exemplo: x = y = 7

(c) multipla: x, y = , , que equivale a x = ; y = , para o caso de apenas dois nomes. Exemplo: x,y = 4,7



P2

Calcular o valor do seno de um ângulo com uma dada precisão. Apresentar ainda o número de termos usados para obter a precisão pedida. O programa deve recorrer à definição de seno que usa a série infinita.

Este problema tem então dois dados de entrada (o ângulo e a precisão) e dois de saída (o seno e o número de termos). Como nos vamos basear na precisão temos que recorrer a um ciclo while. A garantia de cumprir a precisão desejada é controlada pela diferença do valor de duas somas parciais consecutivas.

import math

def seno(x,prec):
    """ Cálculo do seno com uma dada precisão."""
    res = 0
    dif = 1
    exp = 1
    while dif > prec:
        aux = res
        res += (-1)**(exp -1) * (x**(2*exp - 1) / math.factorial(2**exp - 1))
        dif = abs(res - aux)
        exp += 1
    return res, exp

P3

Dadas duas imagens a preto e branco, representadas por um tuplo de tuplos de uns e de zeros, verifique se são o negativo uma da outra. Assegure-se que as imagens têm o mesmo tamanho, caso contrário deve ser desencadeado um erro.

Para controlar o tamanho usamos a instrução assert, que analisa se têm o mesmo número de linhas e de colunas. Depois temos dois ciclos imbricados e mal se encontrem dois valores na mesma posição das duas imagens iguais podemos abandonar pois já sabemos que não podem ser o negativo uma da outra. Lembrar que apenas existem dois valores: 0 e 1.

def negativo(img_1, img_2):
    """ 
    Verifica se duas imagens são o negativo uma da outra.Verifica as dimensões.
    """ 
    assert (len(img_1) == len(img_2)) and (len(img_1[0]) == len(img_2[0])), “ Erro”
    linhas = len(img_1)
    colunas = len(img_1[0])
    for l in range(linhas):
        for c in range(colunas):
            if img_1[l][c] == img_2[l][c]):
                return False
    return True
   

O passeio da tartaruga

Na última aula vimos como se podia desenhar uma grelha usando turtle. Depois decidimos tornar o problema mais complexo colocando uma tartaruga a passear de modo aleatório nessa grelha. Partindo do centro da grelha a tartaruga a cada momento escolhe um de quatro movimentos (Norte, Sul, Este e Oeste). O mundo é finito pelo que a tartaruga não pode sair da grelha e isso tem que ser controlado pelo programa. Vamos ver uma solução possível.

Primeiro a grelha.

import turtle

def grelha(dim,lado):
    """Desenha uma grelha dim x dim em que cada célula tem de lado lado."""
    turtle.color("gray")
    tam = (dim*lado)
    x = -tam//2
    y = tam//2
    turtle.penup()
    turtle.goto(x,y)
    for lin in range(dim):  
        # Desenha linha de quadrados
        for col in range(dim):
            turtle.pendown()
            quadrado(lado)            
            turtle.penup()
            turtle.setx(turtle.xcor() + lado)
        # reposiciona
        turtle.penup()
        turtle.setposition(x, turtle.ycor()-lado)        
    turtle.hideturtle()

def quadrado(lado):
    for i in range(4):
        turtle.fd(lado)
        turtle.rt(90)

Notar que definimos uma função à parte para desenhar um quadrado, na posição em que a tartaruga se encontrar. Essencialmente, o programa é definido por dois ciclos. O mais exterior controla as linhas, o mais interior as colunas. Verifique também como se define a primeira posição da grela (canto superior esquerdo).

Feito isto, a parte fácil, vamos ao passeio.

def passeio(dim, lado, passos):    
    # Prepara grelha
    turtle.speed(0)
    grelha(dim,lado)
    turtle.color('red')
    turtle.home()
    turtle.pendown()
    # Passeio
    turtle.speed(6)
    turtle.dot()
    turtle.showturtle()
    lim_x = lim_y = (dim*lado)//2
    cor_x = 0
    cor_y = 0
    for i in range(passos):
        vai_para = random.choice(['N','E','S','W'])
        if (vai_para == 'N') and (cor_y < lim_y):
            cor_y += lado
            turtle.setheading(90)
            turtle.fd(lado)
        elif (vai_para == 'E') and (cor_x < lim_x):
            cor_x += lado
            turtle.setheading(0)
            turtle.fd(lado)
        elif (vai_para == 'S') and (cor_y > -lim_y):
            cor_y -= lado
            turtle.setheading(270)
            turtle.fd(lado)
        elif (vai_para == 'W') and (cor_x > -lim_x):
            cor_x -= lado
            turtle.setheading(180)
            turtle.fd(lado) 
        else:
            print((vai_para,turtle.xcor(),turtle.ycor()))
            continue

O programa começa por desenhar (a alta velocidade!!) a grelha e coloca a tartaruga no centro da grelha. De seguida temos um ciclo que executa um número de movimentos dado como parâmetro (passos). Usamos o módulo random para poder escolher de modo aleatório o movimento. Escolhido este, temos um longo if que faz uma análise por casos. Notar que no teste controlamos se a posição escolhida está ou não dentro da grelha. No caso de o movimento não ser possível imprime uma mensagem (ramo else final.). Agora é só experimentar!