Построить детерминированный Go AI

11

Вот одна интересная проблема, о которой я подумал на днях, когда биты кода конкурируют с другими битами кода не только в свойстве, которое имеет код, но и в игре против тех других битов кода.

Ваша задача состоит в том, чтобы создать программу, которая принимает текущее состояние доски Го и определяет, какой ход сделать или пройти.

Ваша программа примет следующее:

  • 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

(Обратите внимание, что хотя белый камень был захвачен, он считается узником черного.)

Ваш код должен дополнительно удовлетворять следующим свойствам:

  • Если вашей программе присваивается одинаковое состояние ввода, она всегда должна выдавать один и тот же вывод. Это детерминизм Go AI. У него не должно быть случайного компонента.

  • Ваша программа не должна занимать более 60 секунд, чтобы определить, что делать. Это правило не будет строго применяться из-за различий в вычислительной мощности, но оно должно быть сделано в разумные сроки.

  • Исходный код вашей программы не должен превышать 1 мегабайт (1 048 576 байт).

  • Ваша программа всегда должна делать легальные шаги. Ваша программа не может сделать ход там, где камень уже существует, и не может поместить фигуру, которая привела бы к захвату группы ее собственных камней. (Единственное исключение из правил для целей этой задачи состоит в том, что программе разрешено создавать позицию, которая была изначально там - поскольку ей дается только текущая позиция доски, нельзя ожидать, что она запомнила, какие ходы были сделаны. перед.)

Ваша заявка будет затем играть в турнире «все играют все» против всех остальных заявок, в игре «Го», где состояние доски начинается как пустое, и каждая программа по очереди получает информацию о позиции доски и делает ход. ,

Каждая пара представлений будет играть два раунда - один раунд с каждым игроком, являющимся черным. Поскольку ИИ в этой задаче являются полностью детерминированными, два одинаковых ИИ, играющие вместе, всегда приводят к одной и той же игре.

Условия для победы таковы:

  • Если ваша программа воспроизводится до конца игры, для определения победителя будут использованы китайские правила начисления очков. Коми не будет применяться.

  • Если ваша программа воспроизводится до достижения более раннего состояния, что приводит к бесконечному циклу, две программы будут объявлены связанными.

Ваша заявка будет оцениваться по количеству баллов по сравнению с другими работами. Выигрыш стоит 1 очко, а ничья - полбалла. Представление с наибольшим количеством очков является абсолютным победителем.


Это вызов царя горы, в котором любой может опубликовать новую заявку в любое время, и турнирная таблица будет периодически пересматриваться, когда это произойдет.

Джо З.
источник
7
Хорошо, жду всех остальных заявок, а затем напишу свою, чтобы победить их - должно быть возможно, так как решения являются детерминированными.
Говард
1
Кажется, что игра в ко, такая, что предыдущая позиция повторяется, разрешена, но приводит к немедленной ничьей (так как это вызывает цикл) Интересно ...
FireFly
2
Похоже, что ваша проблема слишком сложна, и никто не будет усердно работать, чтобы дать достойный ответ (это действительно много работы). Это хорошая проблема, но работать с ней слишком сложно.
Виктор Стафуса
1
Почему бы не использовать меньшую доску? 9x9 достаточно распространено для начинающих игроков. Это значительно сокращает пространство поиска, но оно не настолько мало, что его «избили» еще анализом (я думаю, что самое большое, что было полностью решено, это 5x6).
Geobits
1
Как работает ввод? STDIN или аргументы командной строки?
Ypnypn

Ответы:

7

Вот моя запись, чтобы получить этот вызов с земли. Код Python:

print "pass"

Согласно вашим правилам, всегда играть в «пас» - это правильная (хотя и плохая) стратегия.

Бьорн Линдквист
источник
Ваш код всегда будет проигрывать против любого, кто играет против него. Тем не менее, хороший базовый ответ.
Джо З.
1
@JoeZ. И, судя по всему, он победил: P
Дэвид Малдер,
4

Java: выбрать место, любое место

Просто выбирает места на доске, чтобы проверить на валидность. Он использует PRNG, но с заданным начальным значением, так что он детерминирован. Он использует разные порции цикла 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;
}
Geobits
источник
2

Немного Скала:

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

Из чтения Википедии, я думаю, это побьет текущее решение.

yayestechlab
источник
Фактически он выиграет на 361 очко в обоих случаях.
Джо З.
На самом деле, мне придется забрать это обратно, это не соответствует спецификации. ИИ должен быть без гражданства. На самом деле он должен печатать только одну вещь, учитывая состояние доски, а вы заставили ее напечатать две ( 1 1и pass).
Джо З.
@JoeZ. Починил это. В любом случае не скомпилировал бы.
yayestechlab
На самом деле это всегда будет печататься 1 1, поскольку программа всегда запускается заново каждый раз, когда меняется плата.
Джо З.
1

Ява

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

Выбирает первое пустое место. Выигрывает против любого из ИИ на момент публикации.

Ypnypn
источник
2
Это не гарантирует законный ход. Если первое доступное пространство не имеет свободы, оно не может быть воспроизведено. Например, если бы этот ИИ играл сам по себе: после первого ряда чередующихся фигур он 1 1был бы захвачен белым (теперь пустым) и не мог быть сыгран черным в следующем ходу.
Geobits