Berikut ini adalah masalah menarik yang saya pikirkan di hari lain, yang melibatkan potongan kode yang bersaing dengan potongan kode lainnya tidak hanya di properti yang dimiliki kode tersebut, tetapi dengan memainkan permainan melawan potongan kode lainnya.

Tugas Anda adalah membangun program yang mengambil status Go board saat ini, dan menentukan langkah apa yang harus dilakukan atau untuk dilalui.

Program Anda akan menerima yang berikut sebagai masukan:

• 19 baris, masing-masing dengan 19 karakter, mewakili bagian yang saat ini ada di papan Go. Karakter 0mewakili kotak kosong, 1hitam, dan 2putih.

• Dua angka yang mewakili jumlah potongan tahanan yang dimiliki masing-masing pemain (hitam, kemudian putih).

• Satu angka yang mewakili giliran siapa yang akan bergerak (hitam atau putih). Seperti di atas, 1berwarna hitam, dan 2putih.

dan output salah satu dari berikut ini:

• Sepasang koordinat yang a bmewakili koordinat untuk bergerak. 1 1adalah kotak kiri atas, dan angka pertama dan kedua mewakili masing-masing bergerak ke bawah dan ke kanan.

• String pass, yang mewakili gerakan untuk lulus.

Misalnya, program dapat menerima input berikut:

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

yang mewakili permainan di mana hanya beberapa gerakan telah dimainkan.

Kemudian program akan menampilkan 6 5, yang berarti "letakkan batu hitam di titik 6 dari atas dan 5 dari kiri". Ini akan menangkap batu putih di 7 5. Keadaan dewan akan berubah menjadi:

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

(Perhatikan bahwa meskipun batu putih ditangkap, itu dianggap sebagai tahanan hitam.)

Kode Anda juga harus memenuhi properti berikut:

• Jika program Anda diberi status input yang sama, itu harus selalu menghasilkan output yang sama. Ini adalah determinisme dari AI AI. Itu tidak boleh memiliki komponen acak.

• Program Anda tidak boleh lebih dari sekitar 60 detik untuk menentukan langkah apa yang harus dilakukan. Aturan ini tidak akan diterapkan secara ketat karena variasi dalam daya komputasi, tetapi harus bergerak dalam jumlah waktu yang wajar.

• Kode sumber program Anda harus tidak melebihi total 1 megabyte (1.048.576 byte).

• Program Anda harus selalu membuat langkah hukum. Program Anda tidak dapat bergerak di mana batu sudah ada, dan tidak dapat menempatkan sepotong yang akan menghasilkan sekelompok batu yang ditangkap. (Satu pengecualian untuk aturan untuk keperluan tantangan ini adalah bahwa suatu program diizinkan untuk membuat posisi yang semula ada - karena hanya diberi posisi papan saat ini, tidak dapat diharapkan untuk menyimpan gerakan yang telah dibuat. sebelum.)

Kiriman Anda kemudian akan bermain di turnamen semua-main-semua melawan semua kiriman lainnya, dalam permainan Go di mana kondisi dewan dimulai sebagai kosong, dan setiap program bergiliran diberi makan posisi papan dan bergerak .

Setiap pasangan kiriman akan bermain dua putaran - satu putaran dengan masing-masing pemain berwarna hitam. Karena AI dalam masalah ini sepenuhnya deterministik, dua AI yang sama yang bermain bersama akan selalu menghasilkan game yang persis sama dimainkan.

Ketentuan untuk menang adalah sebagai berikut:

• Jika program Anda dimainkan hingga akhir pertandingan, aturan pemberian skor Tiongkok akan digunakan untuk menentukan pemenang. Tidak ada komi akan diterapkan.

• Jika program Anda bermain ke titik bahwa keadaan sebelumnya tercapai, sehingga menyebabkan loop tak terbatas, kedua program akan dinyatakan telah diikat.

Kiriman Anda akan dinilai berdasarkan berapa banyak skor yang diperoleh dibandingkan kiriman lainnya. Kemenangan bernilai 1 poin, dan seri bernilai setengah poin. Pengajuan dengan poin terbanyak adalah pemenang keseluruhan.

Ini adalah tantangan besar, di mana siapa pun dapat memposting entri baru kapan saja, dan kedudukan akan dievaluasi kembali secara berkala ketika ini terjadi.

Inilah entri saya untuk mengatasi tantangan ini. Kode python:

print "pass"

Menurut aturan Anda, selalu bermain "lulus" adalah strategi yang valid (meskipun buruk).

Java: Pilih satu tempat, tempat apa saja

Cukup pilih tempat di papan tulis untuk menguji validitas. Ia menggunakan PRNG, tetapi dengan set seed sehingga itu deterministik. Ia menggunakan potongan yang berbeda dari siklus PRNG tergantung pada berapa banyak putaran telah berlalu.

Untuk setiap posisi kandidat, ini memeriksa untuk melihat bahwa itu adalah langkah yang valid (tetapi bukan bahwa itu langkah yang cerdas ). Jika tidak, ia pindah ke kandidat berikutnya. Jika tidak dapat menemukan langkah yang valid setelah 1000 kali mencoba, itu akan berlalu.

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;
}

Beberapa 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")
  }
}

Dari membaca Wikipedia, saya pikir ini akan mengalahkan solusi saat ini.

Jawa

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++;
      }
    }
  }
}

Memilih ruang kosong pertama. Menang melawan salah satu AI pada saat posting.