Qual melhor estratégia no jogo de tirar 1,3 ou 4 bolinhas?

Question

Imagine um jogo com dois jogadores, Mary e John. Cada um pode retirar 1,3 ou 4 bolinhas por vez e caso existam apenas 1,3,4 bolinhas restantes, eles vao pegar esse número. Quem pega a última pedra ganha.

A estratégia de John é quando houver mais de 4 bolinhas, ele pega apenas 1 bolinha. Já a de Mary é quando houver mais de 4 bolinhas, ela pega 4 bolinhas.

Implemente um par de funções mutualmente recursivas que simule este jogo. Quando n está entre 1 e 100, quem tem a melhor estratégia?

Answer 1

def mary_joga(n, verbose):
    if n==1: 
        if verbose ==1:
            print ('bolinhas na mesa =', n)
            print ('Mary pegou a 1 bolinha e ganhou')
        return 0
    if n==2: 
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('Mary perdeu pois restaram 2 bolinhas')
        return 1
    if n==3:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('Mary pegou as 3 bolinhas e ganhou')
        return 0
    if n==4:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('Mary pegou as 4 bolinhas e ganhou')
        return 0
    if n>4:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('Mary pegou 4 bolinhas')
        n=n-4
        return john_joga(n,verbose)

def john_joga(n,verbose):
    if n==1: 
        if verbose ==1:
            print ('bolinhas na mesa =', n)
            print ('John pegou a 1 bolinha e ganhou')
        return 1
    if n==2:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('John perdeu pois restaram 2 bolinhas')
        return 0
    if n==3:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('John pegou as 3 bolinhas e ganhou')
        return 1
    if n==4:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('John pegou as 4 bolinhas e ganhou')
        return 1
    if n>4:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('John pegou 1 bolinhas')
        n=n-1
        return mary_joga(n,verbose)

def simular_jogo(n, nome):
    if  nome=='Mary':
        return mary_joga(n,1)
    if nome =='John':
        return john_joga(n,1)
    if nome != ('Mary' or 'John'):
        return print('esse jogador não existe!')

def avaliacao_estrategias():
     #para avaliar qual a melhor estratégia

    mary_wins = 0
    john_wins = 0
    for i in range(1,101):
        resultado1 = mary_joga(i,0)
        if resultado1==0: 
            mary_wins = mary_wins+1
        if resultado1==1:
            john_wins = john_wins +1
        resultado2 = john_joga(i,0)
        if resultado2==0: 
            mary_wins = mary_wins+1
        if resultado2==1:
            john_wins = john_wins +1
    if (mary_wins>john_wins): 
        print('Mary vence em ', mary_wins/2, '% das vezes', ',alternando quem começa')
        return
    else:
        print('John vence em ', john_wins/2, '% das vezes',  ',alternando quem começa')
        return

if __name__ == '__main__':

    #para simular o jogo

    resultado = simular_jogo(12, 'Mary')
    print ('SIMULAÇÃO DO JOGO')
    print('o retorno do jogo foi:',resultado )

    # para avaliar as estratégias

    avaliacao_estrategias() 

Cujo resultado é:

bolinhas na mesa = 12
Mary pegou 4 bolinhas
bolinhas na mesa = 8
John pegou 1 bolinhas
bolinhas na mesa = 7
Mary pegou 4 bolinhas
bolinhas na mesa = 3
John pegou as 3 bolinhas e ganhou
SIMULAÇÃO DO JOGO
o retorno do jogo foi: 1
John vence em 59.5 % das vezes ,alternando quem começa

Note que as estraégias de John e Maria são péssimas :-)

Comments

Julia, gostei da sua implementação. Só vou apontar para um pequeno detalhe para o código ficar menos repetitivo.

Você poderia ter juntado as condições n== 1,3,4 e usando a seguinte forma pra mostrar a mensagem.

 if n<= 4 and n !=2:
        if verbose ==1:
            print ('bolinhas na mesa =',n)
            print ('Mary pegou as %d bolinhas e ganhou' % n)

---

Ótima implementação!! Achei que ficou uma programação bem organizada e tranquila para ser lida por terceiros.

Essa ideia de utilizar funções mutuamente recursivas é bem legal e imagino que a mesma ideia possa ser utilizada em outros problemas.

Answer 2

Apesar de não ser pedido no enunciado, resolvi implementar a estratégio de um equilibrio de Nash (a partir de agora chamado "jogador Nash") e para ficar completo a de uma jogadora chamada Trinity, que dá preferência pelo 3 (como o John tem pelo 1 e a Mary pela 4)

Dessa maneira, se estiver correto, o grande vencedor é o Nash, conforme tabela abaixo:

1o jogador/2o jogador Nash John Mary Trinity
Nash 71/28 98/1 97/2 98/2
John 3/96 50/49 60/39 50/49
Mary 5/94 41/58 50/49 43/56
Trinity 4/95 50/49 57/42 50/49

def Mary(n, verbose=1):
    if n==1:
        if verbose:
            print ('Mary pega 1')
        return 1
    elif n==2:
        if verbose:
            print ('Mary pega 1')
        return 1    
    elif n==3:
        if verbose:
            print ('Mary pega 3')
        return 3
    if verbose:
        print ('Mary pega 4')
    return 4

def John(n, verbose=1):
    if n==3:
        if verbose:
            print ('John pega 3')
        return 3
    elif n==2:
        if verbose:
            print ('John pega 1')
        return 1
    elif n==4:
        if verbose:
            print ('John pega 4')
        return 4
    if verbose:
        print ('John pega 4')
    return 1

def Trinity(n, verbose=1):
    if n==1:
        if verbose:
            print ('Trinity pega 1')
        return 1
    elif n==2:
        if verbose:
            print ('Trinity pega 1')
        return 1
    elif n==4:
        if verbose:
            print ('Trinity pega 4')
        return 4
    if verbose:
        print ('Trinity pega 3')
    return 3


def Nash(n, verbose=1):
    if (n<6):
        if n==1:
            if verbose:
                print('Nash pega 1')
            return 1
        elif n==2:
            if verbose:
                print('Nash (perde) e pega 1')
            return 1
        elif n==3:
            if verbose:
                print ('Nash pega 3')
            return 3
        elif n==4:
            if verbose:
                print ('Nash pega 4')
            return 4
        elif n==5:
            if verbose:
                print ('Nash pega 3')
            return 3
    k=(n+1)%7
    if k==0:
        if verbose:
            print('Nash pega 4')
        return 4
    elif k==1:
        if verbose:
            print('Nash (perde) e pega 1')
        return 1
    elif k==2:
        if verbose:
            print('Nash pega 1')
        return 1
    elif k==3:
        if verbose:
            print('Nash (perde) pega 1')
        return 1
    elif k==4:
        if verbose:
            print('Nash pega 1')
        return 1
    elif k==5:
        if verbose:
            print ('Nash pega 4')
        return 4
    elif k==6:
        if verbose:
            print ('Nash pega 3')
        return 3

def Simular_jogo(n,jogador1, jogador2, verbose=1):
    quem = 0
    while n>0:
        quem = 1 - quem
        if quem:
            pegou = jogador1(n, verbose)
        else:
            pegou = jogador2(n, verbose)
        n = n-pegou
        if verbose:
            print (n)
    if quem:
        if verbose:
            print (jogador1.__name__, 'venceu!')
        return jogador1.__name__ , 1
    else:
        if verbose:
            print (jogador2.__name__, 'venceu')
        return jogador2.__name__ , 2


if __name__ == '__main__':

    #para simular um jogo entre dois jogadores, por exemplo Mary e Nash (e Nash começando) com n=15:

    Simular_jogo(15, Mary,Nash, 1)

    #para simular um jogo entre dois jogadores do mesmo tipo, usar o segundo retorno da função

    a,b = Simular_jogo(15, Nash, Nash, 1)

    if b==1:
        print('O primeiro jogador venceu')
    elif b==2:
        print ('O segundo jogador venceu')

    #Calcular qual a melhor estratégia

    jogador1_wins =0
    jogador2_wins = 0

    for i in range(1,100):
        a, b = Simular_jogo(i, Nash, Nash, 0)
        if b==1:
            jogador1_wins = jogador1_wins + 1
        elif b==2:
            jogador2_wins = jogador2_wins + 1
    print ('Jogador 1 ganhou', jogador1_wins, 'vezes, enquanto jogador 2 ganhou', jogador2_wins, 'vezes')

Comments

O comentário que fiz acima também se aplica aqui nas funções John(.) e Mary(.).