Aqui está um problema interessante que eu pensei no outro dia, que envolve bits de código competindo contra outros bits de código, não apenas em uma propriedade que o código possui, mas jogando um jogo contra esses outros bits de código.

Sua tarefa é criar um programa que adote o estado atual de um quadro Go e determine qual jogada fazer ou passar.

Seu programa aceitará o seguinte como entrada:

• 19 linhas, cada uma com 19 caracteres, representando as peças atualmente no tabuleiro Go. Um caractere de 0representa um quadrado vazio, 1é preto e 2branco.

• Dois números representando o número de peças de prisioneiro que cada jogador possui (preto e branco).

• Um número que representa de quem é a vez de se mover (preto ou branco). Como acima, 1é preto e 2branco.

e produza um dos seguintes:

• Um par de coordenadas a brepresentando as coordenadas nas quais se mover. 1 1é o quadrado superior esquerdo e o primeiro e o segundo números representam o movimento para baixo e para a direita, respectivamente.

• A sequência pass, que representa um movimento para passar.

Por exemplo, o programa pode receber a seguinte entrada:

0000000000000000000
0000000000000000000
0000000000000000000
0001000000000002000
0000000000000000000
0000000000000000000
0001210000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0002000000000001000
0000000000000000000
0000000000000000000
0000000000000000000
0 0 1

que representa um jogo em que apenas alguns movimentos foram jogados.

Em seguida, o programa pode sair 6 5, o que significa "colocar uma pedra preta no ponto 6 da parte superior e 5 na esquerda". Isso capturaria a pedra branca em 7 5. O estado do quadro mudaria para:

0000000000000000000
0000000000000000000
0000000000000000000
0001000000000002000
0000000000000000000
0000100000000000000
0001010000000000000
0000100000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0000000000000000000
0002000000000001000
0000000000000000000
0000000000000000000
0000000000000000000
1 0 2

(Observe que, embora uma pedra branca tenha sido capturada, ela conta como prisioneira do preto.)

Seu código também deve atender às seguintes propriedades:

• Se o seu programa recebe o mesmo estado de entrada, ele sempre deve produzir a mesma saída. Esse é o determinismo da Go AI. Não deve ter um componente aleatório.

• Seu programa não deve levar mais de aproximadamente 60 segundos para determinar qual ação fazer. Esta regra não será aplicada estritamente devido a variações no poder da computação, mas deve ser executada em um período de tempo razoável.

• O código-fonte do seu programa não deve exceder um total de 1 megabyte (1.048.576 bytes).

• Seu programa sempre deve fazer movimentos legais. Seu programa não pode fazer um movimento onde uma pedra já existe e não pode colocar uma peça que resultaria na captura de um grupo de suas próprias pedras. (Uma exceção às regras para os propósitos deste desafio é que é permitido que um programa crie uma posição que estava originalmente lá - porque somente recebe a posição atual de um quadro, não se pode esperar que armazene quais movimentos foram feitos. antes.)

Seu envio será jogado em um torneio all-play-all contra todos os outros envios, em um jogo de Go, onde o estado do tabuleiro começa como vazio, e cada programa se revezam, sendo alimentados com a posição do tabuleiro e fazendo uma jogada .

Cada par de envios jogará duas rodadas - uma rodada com cada jogador sendo preto. Como as IAs nesse problema são completamente determinísticas, duas das mesmas AIs jogando juntas sempre resultarão exatamente no mesmo jogo.

As condições para uma vitória são as seguintes:

• Se o seu programa for reproduzido até o final do jogo, as regras de pontuação do Go serão usadas para determinar o vencedor. Nenhum komi será aplicado.

• Se o seu programa for reproduzido até o ponto em que um estado anterior é atingido, causando um loop infinito, os dois programas serão declarados empatados.

Seu envio será pontuado por quantos pontos ele marcar contra outros envios. Uma vitória vale 1 ponto e um empate vale meio ponto. A finalização com mais pontos é o vencedor geral.

Esse é um desafio do tipo rei da colina, no qual qualquer pessoa pode postar uma nova entrada a qualquer momento, e as classificações serão reavaliadas periodicamente quando isso acontecer.

Aqui está a minha entrada para tirar esse desafio do chão. Código Python:

print "pass"

De acordo com suas regras, sempre jogar "passe" é uma estratégia válida (embora ruim).

Java: Escolha um local, qualquer local

Simplesmente escolhe pontos no quadro para testar a validade. Ele usa o PRNG, mas com uma semente definida, é determinista. Ele usa diferentes partes do ciclo PRNG, dependendo de quantas voltas passaram.

Para cada posição de candidato, ele verifica se é uma jogada válida (mas não se trata de uma jogada inteligente ). Se não for, passa para o próximo candidato. Se não conseguir encontrar uma movimentação válida após 1000 tentativas, ela será aprovada.

import java.util.Random;
import java.util.Scanner;

public class GoNaive {

    int[][] board;
    boolean[] checked;
    int me;

    public static void main(String[] args) {
        new GoNaive().run();
    }

    void run(){
        int turns = init();
        Random rand = new Random(seed);

        for(int i=0;i<turns*tries;i++)
            rand.nextInt(size*size);

        for(int i=0;i<tries;i++){
            int pos = rand.nextInt(size*size);
            for(int c=0;c<size*size;c++)
                checked[c]=false;
            if(board[pos%size][pos/size] == 0)
                if(hasLiberties(pos, me)){
                    System.out.print((pos%size+1) + " " + (pos/size+1));
                    System.exit(0);
                }
        }
        System.out.print("pass");
    }

    boolean hasLiberties(int pos, int color){
        if(checked[pos])
            return false;
        checked[pos] = true;

        int x = pos%size, y=pos/size, n;

        if(x>0){
            n = board[x-1][y];
            if(n==0 || (n==me && hasLiberties(y*size+x-1, color)))
                return true;
        }
        if(size-x>1){
            n = board[x+1][y];
            if(n==0 || (n==me && hasLiberties(y*size+x+1, color)))
                return true;
        }
        if(y>0){
            n = board[x][y-1];
            if(n==0 || (n==me && hasLiberties((y-1)*size+x, color)))
                return true;
        }
        if(size-y>1){
            n = board[x][y+1];
            if(n==0 || (n==me && hasLiberties((y+1)*size+x, color)))
                return true;
        }
        return false;
    }

    int init(){
        int turns = 0;
        board = new int[size][size];
        checked = new boolean[size*size];
        turns = 0;
        Scanner s = new Scanner(System.in);
        String line;
        for(int i=0;i<size;i++){
            line = s.nextLine();
            for(int j=0;j<size;j++){
                board[j][i] = line.charAt(j)-48;
                if(board[j][i] > 0)
                    turns++;
            }
        }
        String[] tokens = s.nextLine().split(" ");
        turns += Integer.valueOf(tokens[0]);
        turns += Integer.valueOf(tokens[1]);
        me = Integer.valueOf(tokens[2]);
        s.close();
        return turns;
    }

    final static int size = 19;
    final static int seed = 0xdeadface;
    final static int tries = 1000;
}

Alguns Scala:

package go;

class Go {
  def main(args : Array[String]) {
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    System.out.printLn("1 1")
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    readLine()
    System.out.printLn("pass")
  }
}

Ao ler a Wikipedia, acho que isso superará a solução atual.

Java

public class Go {
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    for (int i = 0; i < 361;) {
      char c = s.nextChar();
      if (c != '\n') {
        if (c == '0') {
          System.out.println((i % 19 + 1) + " " + (i / 19 + 1));
          System.exit(0);
        }
        i++;
      }
    }
  }
}

Escolhe o primeiro espaço vazio. Ganha contra qualquer um dos AIs no momento da postagem.