Conexão Parcialmente Observável-4

8

O jogo

Você estará jogando um jogo (quase) padrão do Connect-4 . Infelizmente, é um jogo por correspondência e alguém colocou fita preta em cada segunda linha começando de baixo, para que você não possa ver nenhum dos movimentos de seu oponente nessas linhas.

Quaisquer movimentos dentro de colunas já cheias contarão como passando o seu turno, e se um jogo durar mais do que os 6 * 7turnos, será considerado um empate.

Especificação do desafio

Seu programa deve ser implementado como uma função Python 3. O primeiro argumento é uma "visão" do tabuleiro, representando o estado conhecido do tabuleiro como uma lista 2D de linhas de baixo para cima, onde 1é um movimento do primeiro jogador, 2um movimento do segundo jogador e 0uma posição vazia ou oculta mova pelo seu oponente.

O segundo argumento é um número de turno indexado 0e sua paridade informa qual jogador você é.

O argumento final é um estado arbitrário, inicializado Noneno início de cada jogo, que você pode usar para preservar o estado entre os turnos.

Você deve retornar duas tuplas do índice da coluna que deseja reproduzir e o novo estado a ser retornado no próximo turno.

Pontuação

Uma vitória conta como +1, um empate como 0e uma perda como -1. Seu objetivo é alcançar a maior pontuação média em um torneio round-robin. Vou tentar executar quantas partidas forem necessárias para identificar um vencedor claro.

Regras

Qualquer concorrente deve ter no máximo um bot concorrente ao mesmo tempo, mas não há problema em atualizar sua inscrição se você fizer melhorias. Por favor, tente limitar seu bot a ~ 1 segundo de tempo de raciocínio por turno.

Teste

Aqui está o código fonte do controlador, juntamente com alguns exemplos de bots não concorrentes para referência:

import itertools
import random

def get_strides(board, i, j):
    yield ((i, k) for k in range(j + 1, 7))
    yield ((i, k) for k in range(j - 1, -1, -1))
    yield ((k, j) for k in range(i + 1, 6))
    yield ((k, j) for k in range(i - 1, -1, -1))
    directions = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
    def diag(di, dj):
        i1 = i
        j1 = j
        while True:
            i1 += di
            if i1 < 0 or i1 >= 6:
                break
            j1 += dj
            if j1 < 0 or j1 >= 7:
                break
            yield (i1, j1)
    for d in directions:
        yield diag(*d)

DRAWN = 0
LOST = 1
WON = 2
UNDECIDED = 3

def get_outcome(board, i, j):
    if all(board[-1]):
        return DRAWN
    player = board[i][j]
    strides = get_strides(board, i, j)
    for _ in range(4):
        s0 = next(strides)
        s1 = next(strides)
        n = 1
        for s in (s0, s1):
            for i1, j1 in s:
                if board[i1][j1] == player:
                    n += 1
                    if n >= 4:
                        return WON
                else:
                    break
    return UNDECIDED

def apply_move(board, player, move):
    for i, row in enumerate(board):
        if board[i][move] == 0:
            board[i][move] = player
            outcome = get_outcome(board, i, move)
            return outcome
    if all(board[-1]):
        return DRAWN
    return UNDECIDED

def get_view(board, player):
    view = [list(row) for row in board]
    for i, row in enumerate(view):
        if i % 2:
            continue
        for j, x in enumerate(row):
            if x == 3 - player:
                row[j] = 0
    return view

def run_game(player1, player2):
    players = {1 : player1, 2 : player2}
    board = [[0] * 7 for _ in range(6)]
    states = {1 : None, 2 : None}
    for turn in range(6 * 7):
        p = (turn % 2) + 1
        player = players[p]
        view = get_view(board, p)
        move, state = player(view, turn, states[p])
        outcome = apply_move(board, p, move)
        if outcome == DRAWN:
            return DRAWN
        elif outcome == WON:
            return p
        else:
            states[p] = state
    return DRAWN

def get_score(counts):
    return (counts[WON] - counts[LOST]) / float(sum(counts))

def run_tournament(players, rounds=10000):
    counts = [[0] * 3 for _ in players]
    for r in range(rounds):
        for i, player1 in enumerate(players):
            for j, player2 in enumerate(players):
                if i == j:
                    continue
                outcome = run_game(player1, player2)
                if outcome == DRAWN:
                    for k in i, j:
                        counts[k][DRAWN] += 1
                else:
                    if outcome == 1:
                        w, l = i, j
                    else:
                        w, l = j, i
                    counts[w][WON] += 1
                    counts[l][LOST] += 1
        ranks = sorted(range(len(players)), key = lambda i: get_score(counts[i]), reverse=True)
        print("Round %d of %d\n" % (r + 1, rounds))
        rows = [("Name", "Draws", "Losses", "Wins", "Score")]
        for i in ranks:
            name = players[i].__name__
            score = get_score(counts[i])
            rows.append([name + ":"] + [str(n) for n in counts[i]] + ["%6.3f" % score])
        lengths = [max(len(s) for s in col) + 1 for col in zip(*rows)]
        for i, row in enumerate(rows):
            padding = ((n - len(s)) * ' ' for s, n in zip(row, lengths))
            print(''.join(s + p for s, p in zip(row, padding)))
            if i == 0:
                print()
        print()

def random_player(view, turn, state):
    return random.randrange(0, 7), state

def constant_player(view, turn, state):
    return 0, state

def better_random_player(view, turn, state):
    while True:
        j = random.randrange(0, 7)
        if view[-1][j] == 0:
            return j, state

def better_constant_player(view, turn, state):
    for j in range(7):
        if view[-1][j] == 0:
            return j, state

players = [random_player, constant_player, better_random_player, better_constant_player]

run_tournament(players)

Coisa feliz!

Resultados Provisórios

Name                    Draws Losses Wins  Score  

zsani_bot:              40    5377   94583  0.892 
better_constant_player: 0     28665  71335  0.427 
constant_player:        3     53961  46036 -0.079 
normalBot:              38    64903  35059 -0.298 
better_random_player:   192   71447  28361 -0.431 
random_player:          199   75411  24390 -0.510 
user1502040
fonte
Você poderia explicar por que verifica a visualização [-1] [j] == 0? Não tenho muita certeza de ver onde você os preencheu e meu conhecimento sobre python parece um pouco enferrujado.
Barbarian772
@ Barbarian772 Estou verificando se ainda há espaço nessa coluna. Observe que existem 6 linhas para que a linha superior seja totalmente observada.
user1502040
11
Você não deve contar colocando em colunas já completas como um passe. Muitos conectam 4 jogos terminando com apenas uma coluna não preenchida e se um jogador perder jogando nessa coluna, isso fará com que o jogo empate quando for uma vitória forçada para um jogador.
soktinpk 10/09
@soktinpk Isso não adiciona outra camada de estratégia? Afinal, o Connect-4 é um jogo resolvido, portanto, o fator de pular a curva pode ser suficiente para alterar uma regra que os colaboradores não podem usar apenas os algoritmos padrão.
mypetlion
11
Indexação zero a partir do fundo, são as linhas gravadas (0,2,4,6) ou (1,3,5)? Alguma arte ASCII seria útil.
SIGSTACKFAULT

Respostas:

6

Este bot leva todas as vitórias seguras e volta a bloquear os rivais, adivinhe-os vertical e horizontalmente ou faça movimentos aleatórios.

importar impressão, matemática, coleções, cópia
def zsani_bot_2 (visualizar, virar, estado):
    if state == None: #first turno próprio - sempre para o meio
        state = (1, 2) se turno == 0 else (2, 1) # (my_symbol, seu símbolo)
        #print (pprint.pformat (exibir) + 'Turn:' + str (turn) + 'Player:' + str (state [0]))
        retorno 3, estado

    #locate pontos óbvios
    para i no intervalo (1, 6): # skip first row
        para j no intervalo (len (ver [i])): #TODO: otimizar com zip. Procure clareza agora
            se visualizar [i] [j]! = 0 e visualizar [i-1] [j] == 0:
                visualizar [i-1] [j] = estado [1]
    Pontos_Inimigos = math.floor (turno / 2)
    ++ pontos_inimigos se o estado [0] == mais 2 pontos_inimigos
    pontos_conhecidos = soma ([i.count (estado [1]) para i em exibição])
    falta_pontos = pontos_imigos - pontos_conhecidos

    # garanta que vença em qualquer direção
    para j no intervalo (0, 7): #every column
        para i no intervalo (4, -1, -1):
            se visualizar [i] [j]! = 0:
                break #find o ponto cheio mais alto conhecido
        if (não faltando_pontos ou i + 1 em {1, 3, 5}):
            view1 = copy.deepcopy (visualização)
            tentativa = apply_move (vista1, estado [0], j)
            se a tentativa == GANHOU:
               # print (pprint.pformat (ver) + 'Turn:' + str (turn) + 'Player:' + str (state [0]) + 'movimento vencedor')
                retornar j, estado

    #bloqueie se o inimigo vence em qualquer direção
    para j no intervalo (0, 7):
        para i no intervalo (4, -1, -1):
            se visualizar [i] [j]! = 0:
                break #find o ponto cheio mais alto conhecido
        if (não falta_pontos ou (i + 1 em {1, 3, 5})):
            view1 = copy.deepcopy (visualização)
            tentativa = apply_move (view1, state [1], j)
            se a tentativa == GANHOU:
              # print (pprint.pformat (ver) + 'Turn:' + str (turn) + 'Player:' + str (estado [0]) + 'salvar movimento')
                retornar j, estado

    #block walls
    para i no intervalo (0, 3): #impossible para obter 4 em uma linha quando a coluna estiver cheia
        para j no intervalo (0, 6):
            se visualizar [i] [j]! = 0 e visualizar [i] [j] == visualizar [i + 1] [j] e visualizar [i + 2] [j] == visualizar [i + 3] [j ] == 0:
             # print (pprint.pformat (exibir) + 'Turn:' + str (turn) + 'Player:' + str (estado [0]) + 'mover a coluna')
                retornar j, estado

    #block platform se possui informações perfeitas na linha abaixo e no ponto de entrega
    para i no intervalo (0, 5):
        para j no intervalo (0, 3):
            stats = collections.Counter ([view [i] [j], view [i] [j + 1], view [i] [j + 2], view [i] [j + 3]])
            se estatísticas [0] == 2 e (estatísticas [estado [0]] == 2 ou estatísticas [estado [0]] == 2):
                para k no intervalo (0, 3):
                    se visualizar [i] [j + k] == 0:
                        pausa
                if (i == 0 ou visualize [i-1] [j + k]! = 0) e (não falta_pontos ou i em {1, 3, 5}):
                    #print (pprint.pformat (ver) + 'Turn:' + str (turn) + 'Player:' + str (estado [0]) + 'movimento da plataforma')
                    retornar j + k, estado
                outro:
                    para l na faixa (k, 3):
                        se visualizar [i] [j + l] == 0:
                            pausa
                        if (i == 0 ou visualize [i-1] [j + l]! = 0) e (não falta_pontos ou i em {1, 3, 5}):
                     # print (pprint.pformat (ver) + 'Turn:' + str (turn) + 'Player:' + str (estado [0]) + 'movimento da plataforma')
                            retornar j + l, estado

    #fallback -> random
    enquanto True:
        j = random.randrange (0, 7)
        se visualizar [-1] [j] == 0:
            #print (pprint.pformat (exibir) + 'Turn:' + str (turn) + 'Player:' + str (estado [0]) + 'movimento aleatório')
            retornar j, estado

Obrigado por corrigir o run_game!

Changelog:

  • v2 adiciona bloqueio horizontal - se, em uma linha de 4, houver duas vagas vazias e duas vagas preenchidas pelo mesmo jogador, ele tentará preencher uma delas para ter três seguidas / bloquear a linha do adversário, o que, esperançosamente, ser capitalizado nos seguintes turnos.
Syfer Polski
fonte
3
Bem vindo ao site. Votei em rejeitar a edição para mudar para código, seria melhor deixar como um comentário, para que o OP possa decidir o que fazer com o código.
Ad Hoc Garf Hunter
Não tenho reputação suficiente para comentar no post principal. Como faço para retirar uma edição?
Syfer Polski
Não há necessidade de retirar a edição (acho que você não consegue). No futuro, os comentários serão suficientes, mas, como você disse isso em sua resposta, é provável que o OP atenda. Além disso, acho que o OP verá que você sugeriu e editou mesmo que ele tenha sido rejeitado.
Ad Hoc Garf Hunter
O motivo pelo qual gostaria de retirar a edição é porque perdi uma linha nas alterações, sem a qual o código editado falhará completamente na execução. Incluí-o na sugestão de edição em minha postagem. Obrigado pela ajuda!
Syfer Polski
2

O normalBot se baseia na suposição de que pontos no meio são mais valiosos do que pontos nas extremidades. Assim, ele usa uma distribuição normal centralizada no meio para determinar suas escolhas.

def normalBot(view, turn, state):
    randomNumber = round(np.random.normal(3, 1.25))
    fullColumns = []
    for i in range(7):
        if view[-1][i] != 0:
            fullColumns.append(i)
    while (randomNumber > 6) or (randomNumber < 0) or (randomNumber in fullColumns):
        randomNumber = round(np.random.normal(3, 1.25))
    return randomNumber, state
Bob Cratchit
fonte
-1

Isso é obviamente não competitivo, mas ainda assim muito útil para depuração ... e surpreendentemente divertido, se você conhece bem o seu bot para enganar: D, então estou postando na esperança de inspirar mais envios:

import math, pprint
def manual_bot(view, turn, state):
    if state == None:
        state = (1, 2) if turn == 0 else (2, 1) #(my_symbol, your symbol)

#locate obvious points
    for row in range (1, 6):
        for j in range(len(view[row])):
            if view[row][j] != 0 and view[row-1][j] == 0:
                view[row-1][j] = state[1]

#if you're second, the opponent has one more point than half the turns
    enemy_points = math.ceil(turn/2)
    known_points = sum([row.count(state[1]) for row in view])
    missing_points = enemy_points - known_points

    print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' Missing points: ' + str(missing_points))
    while True:
        try:
            move = int(input("What is your move?(0-6) "))
        except ValueError:
            continue
        if move in {0, 1, 2, 3, 4, 5, 6}:
            return move, state

A grade está de cabeça para baixo (a linha inferior é mais alta). Para receber os anúncios dos vencedores, você precisa corrigir o controlador do jogo, adicionando uma declaração de impressão antes de retornar a vitória:

elif outcome == WON:
    print(pprint.pformat(board) + ' Turn: ' + str(turn) +' Winner: '+ str(p))
    return p

[[0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 0 Jogador: 1 Pontos perdidos: 0
Qual é a sua jogada? (0-6) 3
[[0, 0, 0, 1, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 2 Jogadores: 1 Pontos perdidos: 0
Qual é a sua jogada? (0-6) 2
[[0, 0, 1, 1, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 4 Jogador: 1 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 4
[[0, 0, 1, 1, 1, 0, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 6 Jogador: 1 Pontos perdidos: 2
Qual é a sua jogada? (0-6) 1
[[2, 1, 1, 1, 1, 2, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 6 Vencedor: 1
[[0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 1 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 2
[[0, 0, 2, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 3 Jogador: 2 Pontos perdidos: 2
Qual é a sua jogada? (0-6) 3
[[0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 5 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 4
[[0, 0, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 7 Jogador: 2 Pontos perdidos: 2
Qual é a sua jogada? (0-6) 1
[[0, 2, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turno: 9 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 2
[[0, 2, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 11 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 4
[[0, 2, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 2, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 13 Jogador: 2 Pontos perdidos: 2
Qual é a sua jogada? (0-6) 4
[[0, 2, 2, 1, 2, 0, 0],
 [0, 1, 1, 2, 2, 0, 0],
 [0, 0, 1, 0, 1, 0, 0],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 15 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 3
[[0, 2, 2, 1, 2, 0, 0],
 [0, 1, 1, 2, 2, 0, 0],
 [0, 0, 1, 2, 1, 0, 0],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 17 Jogador: 2 Pontos perdidos: 2
Qual é a sua jogada? (0-6) 5
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 0, 1, 2, 1, 0, 0],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 19 Jogador: 2 Pontos perdidos: 0
Qual é a sua jogada? (0-6) 
Qual é a sua jogada? (0-6) 6
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 0, 1, 2, 1, 0, 2],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 21 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 1
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 0, 2],
 [0, 1, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 23 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 3
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 0, 2],
 [0, 1, 1, 2, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turno: 25 Jogador: 2 Pontos perdidos: 2
Qual é a sua jogada? (0-6) 6
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 0, 2],
 [0, 1, 1, 2, 2, 0, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turno: 27 Jogador: 2 Pontos perdidos: 1
Qual é a sua jogada? (0-6) 5
[[1, 2, 2, 1, 2, 1, 1],
 [1, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 2, 2],
 [0, 1, 1, 2, 2, 0, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turno: 29 Jogador: 2 Pontos perdidos: 0
Qual é a sua jogada? (0-6) 5
[[1, 2, 2, 1, 2, 1, 1],
 [1, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 2, 2],
 [0, 1, 1, 2, 2, 2, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turno: 29 Vencedor: 2
Rodada 1 de 1

Nome Empates Perdas Vitórias Pontuação
manual_bot: 0 0 2 1.000 zsani_bot_2: 0 2 0 -1.000

Syfer Polski
fonte