构建一个确定性的Go AI

Question

这是我前几天想到的一个有趣的问题，它涉及到一些代码与其他代码的竞争，不只是在代码所拥有的属性中，而是通过与其他代码进行游戏。

您的任务是构建一个程序，该程序接受围棋板的当前状态，并确定要进行或通过的移动。

您的程序将接受以下输入：

• 19行，每一行19个字符，代表当前在围棋板上的部分。0的字符表示一个空方块，1表示黑色，2表示白色。
• 两个数字，代表每个玩家的囚徒数量(黑色，然后白色)。
• 代表该移动的数字(黑色或白色)。如上所述，1是黑色的，2是白色的。

并输出以下内容之一：

• 表示移动坐标的一对坐标a b。1 1是左上角的正方形，第一个和第二个数字分别代表向下和向右移动。
• 字符串pass，它表示传递的移动。

例如，程序可能收到以下输入：

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

这代表了一种游戏，其中只有几个动作已经玩过。

然后程序可能会输出6 5，这意味着“从顶部第6点放一块黑色的石头，从左边放第5点”。这将捕捉到7 5的白石。然后，董事会的状况将改为：

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

(请注意，虽然一颗白色的石头被捕获，但它被视为黑色的囚犯。)

您的代码还必须满足以下属性：

• 如果程序被赋予相同的输入状态，它必须始终产生相同的输出。这是围棋AI的决定论。它不能有随机成分。
• 您的程序不得超过60秒左右，以确定采取什么行动。由于计算能力的变化，这一规则不会被严格应用，但它必须在合理的时间内采取行动。
• 您的程序的源代码不能超过1MB (1,048,576字节)。
• 你的程序必须总是合法的。你的程序不能在石头已经存在的地方移动，也不能放置一块会导致一组自己的石头被捕获的片段。(为这一挑战的目的，规则的一个例外是，允许程序创建一个原来在那里的位置-因为它只是给定了董事会的当前位置，所以不能期望它存储以前已经移动过的位置。)

然后，你的投稿将在一场全场比赛中与所有其他投稿进行对抗，在一场游戏中，董事会的状态从空开始，每个程序轮流被喂食到董事会的位置并移动。

每对投稿将进行两轮-一轮与每名球员是黑色。由于在这个问题上的认可机构是完全确定性的，两个相同的认可机构在一起玩总是会导致完全相同的游戏。

获胜的条件如下：

• 如果你的程序玩到游戏结束，中国的得分规则围棋将被用来确定赢家。不会申请科米的。
• 如果您的程序达到了一个较早的状态，从而导致无限循环，则这两个程序将被声明为已绑定。

你的投稿将以它相对于其他投稿的分数来评分。胜利等于1分，平局等于半分。得分最高的投稿是整体的赢家。

这是一个小山之王的挑战，任何人都可以在任何时候张贴一个新的条目，当这种情况发生时，将定期对排名进行重新评估。

Answer 1

这是我的参赛机会，让这场挑战从地面开始。Python代码：

print "pass"

根据你的规则，玩“传球”是一种有效(尽管很糟糕)的策略。

Answer 2

Java :选择一个点，任何点

只需选择板上的点来测试是否有效。它使用PRNG，但是有一个set种子，所以这是确定性的。它使用不同的块的PRNG循环取决于多少个回合已经通过。

对于每个候选人职位，它会检查这是否是一个有效的移动(但不是一个聪明的移动)。如果不是，它就转移到下一个候选人身上。如果在1000次尝试后找不到有效的移动，它就会通过。

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

Answer 3

一些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")
  }
}

通过阅读维基百科，我认为这将击败当前的解决方案。