Pertempuran Grid-Routing

22

CATATAN: Tantangan ini saat ini sudah mati, karena saya tidak dapat menginstal bahasa yang diperlukan untuk menjalankan pertandingan. Jika orang lain punya waktu dan minat untuk melakukannya, saya tidak menentang.

Lihat bagian bawah pos untuk melihat papan peringkat.

Ini adalah tantangan king-of-the-hill semi-kooperatif, di mana bot membangun jalur melalui grafik grid dua dimensi. Bot yang mengontrol node dengan lalu lintas terbanyak adalah pemenangnya. Namun, dibutuhkan lebih dari satu sumber daya bot untuk benar-benar membangun jalur penghubung, sehingga bot harus bekerja bersama - sampai batas tertentu.

Gameplay

Berikut ini, biarlah N > 0jumlah bot yang dimainkan.

Grid

Permainan ini dimainkan pada kisi-kisi bilangan bulat dua dimensi , yang koordinat bawahnya berada . Setiap koordinat dengan memiliki tepi keluar ke tiga koordinat , dan di atas itu, di mana -coordinates diambil modulo . Ini berarti bahwa grid membungkus di tepi timur dan barat. Setiap koordinat bawah adalah sumber , dan setiap koordinat atas adalah sebuah wastafel .⌊4/3N2⌋ × ⌊4/3N2(0,0)(x,y)0 ≤ y < ⌊4/3N2⌋-1(x-1,y+1)(x,y+1)(x+1,y+1)x⌊4/3N2(x,0)(x,⌊4/3N2⌋-1)

Gambar berikut menunjukkan 8 × 8kotak.

Kisi 8x8.

Setiap simpul grafik tidak aktif , aktif , atau rusak . Semua simpul mulai tidak aktif, dan dapat diaktifkan oleh bot, yang kemudian akan menjadi pemiliknya. Juga, bot dapat mematahkan simpul, dan mereka tidak dapat diperbaiki.

Ubah Pesanan

Giliran terdiri dari fase penghancuran dan fase aktivasi . Pada fase penghancuran, setiap bot dapat mematahkan satu simpul tidak aktif. Titik itu rusak sejak saat itu, dan mungkin tidak diaktifkan oleh siapa pun. Pada fase aktivasi, setiap bot dapat mengaktifkan satu titik tidak aktif. Sejak saat itu, mereka memiliki simpul itu, dan itu tidak dapat diaktifkan kembali oleh orang lain. Beberapa bot mungkin memiliki satu simpul, jika mereka semua mengaktifkannya pada belokan yang sama. Dalam setiap fase, pemilihan titik dilakukan secara bersamaan.

Mencetak gol

Satu putaran berlangsung untuk belokan yang tepat . Setelah ini, ronde tersebut dicetak sebagai berikut. Dari setiap simpul sumber aktif, kami melakukanN2N pencarian acak kedalaman-pertama sepanjang simpul aktif (artinya anak-anak dari setiap simpul dikunjungi dalam urutan acak). Jika jalur ditemukan dari sumber ke beberapa wastafel, maka untuk semua simpul di sepanjang jalur itu, setiap pemilik titik mendapatkan satu titik.

Seluruh permainan berlangsung selama 100 putaran, dan bot dengan poin terbanyak secara keseluruhan adalah pemenangnya. Saya dapat menambah angka ini, jika varians skornya terlalu tinggi.

Aturan tambahan

  • Tidak main-main dengan controller atau kiriman lainnya.
  • Paling banyak satu pengajuan per kontestan.
  • Tidak ada sumber daya eksternal, kecuali satu file teks pribadi, yang dihapus pada awal permainan.
  • Jangan mendesain bot Anda untuk mengalahkan atau mendukung lawan tertentu.
  • Berikan perintah untuk mengkompilasi dan menjalankan bot Anda. Kompiler / juru bahasa yang tersedia secara bebas untuk Debian Linux dapat diterima.

Pengendali

Kontroler ditulis dalam Python 3, dan dapat ditemukan di GitHub . Lihat file README untuk instruksi terperinci. Berikut ini API untuk membantu Anda memulai:

  • Bot dimulai pada awal setiap putaran, dan bertahan hingga akhir putaran. Komunikasi dengan pengontrol melalui STDIN dan STDOUT, menggunakan pesan yang diakhiri baris baru.
  • BEGIN [num-of-bots] [num-of-turns] [side-length] adalah input di awal.
  • DESTROY [turn]adalah input pada awal setiap tahap kehancuran. Bot Anda akan merespons dengan baik VERTEX x,yuntuk memilih titik, atau NONE.
  • BROKEN [turn] [your-choice] [other-choices]adalah input pada akhir setiap fase kehancuran. Urutan bot lain diacak pada awal setiap pertandingan, tetapi tetap ditetapkan selama itu. Pilihannya disajikan sebagai x,yatau N.
  • ACTIVATE [turn]dan OWNED [turn] [your-choice] [other-choices]merupakan padanan di atas untuk fase aktivasi, dan memiliki semantik yang sama.
  • SCORE [your-score] [other-scores] adalah input di akhir permainan.
  • Bot Anda memiliki 1 detik untuk menganalisis hasil fase dan memilih titik berikutnya, dan 1 detik untuk berhenti setelah diberi skor. Saya akan menguji pengiriman pada laptop saya yang relatif lama, jadi lebih baik meninggalkan sedikit margin di sini.

Harap ingat untuk membersihkan buffer output Anda.Tidak melakukannya dapat menggantung pengontrol di beberapa lingkungan.

Papan peringkat

Diperbarui 3/13/2015

Peacemaker aktif dan berjalan, dan Funnelweb juga menerima pembaruan. Skor melonjak dengan urutan besarnya. Connector melebihi batas waktu dalam dua game.

Funnelweb: 30911
Connector: 18431
Watermelon: 3488
Annoyance: 1552
Explorer: 735
Checkpoint: 720
Random Builder: 535
FaucetBot: 236
Peacemaker: 80

Log lengkap dengan grafik seni ASCII dapat ditemukan di repositori pengontrol, di graphical_log.txt.

Beberapa pengamatan:

  • Konektor dapat dengan mudah dihentikan dengan mematahkan satu titik di depannya. Saya menduga Gangguan sering melakukan ini. Namun, saat ini tidak masuk akal karena hanya Connector yang dapat membangun jalur.
  • Semangka bisa mendapatkan skor yang layak hanya dengan berada di jalur penghubung (karena DFS sangat mungkin menggunakan simpulnya).
  • Penjelajah suka menanam tanaman merambat dari semangka.
  • Funnelweb yang diperbarui mendapatkan skor yang sangat bagus, karena Connector biasanya menempel di bagian bawah grid.
  • Permainan semakin lama, putaran rata-rata membutuhkan sekitar 25 detik pada mesin saya.
Zgarb
sumber
1
@Alex saya mencoba merancang tantangan sehingga bot bunuh diri tidak akan mengacaukan semuanya. Tiga bot yang dirancang dengan baik harus selalu dapat membangun jalur yang valid, jika mereka bekerja bersama.
Zgarb
2
@Zgarb Bunuh diri seharusnya tidak mengacaukannya, tetapi beberapa troll-bot yang bekerja bersama mungkin juga dapat memblokir semua jalur, merusak permainan.
Geobits
2
@CarpetPython Node aktif tidak dapat dihancurkan.
Zgarb
1
Sepertinya kami tidak mungkin melihat game yang menarik dengan pemain dan aturan saat ini. Saya sarankan Anda mengubah sedikit peraturan untuk menciptakan peluang bagi permainan yang menarik. Mengubah ukuran kisi menjadi 1,5 * N ^ 2 bukannya 2 * N ^ 2 harus bagus dan tidak membingungkan robot yang ada terlalu banyak.
Logic Knight
1
@justhalf Itu benar. Permainan dalam log sebenarnya dimainkan dengan ukuran grid yang dikurangi lebih lanjut 4/3*N^2, dan bahkan di sana, bot memiliki masalah dalam membentuk jalur yang valid. Namun, Connector untuk sementara didiskualifikasi karena kesalahan, dan sekarang setelah diperbaiki, saya berharap game menjadi lebih menarik. Saya akan menjalankan batch lain malam ini.
Zgarb

Jawaban:

7

Konektor (Jawa)

Mencoba membuat jalur pada posisi acak. Karena tidak dapat membuat jalur sendiri, ia mencari sel yang aktif dan menggunakannya. Kredit jatuh ke Geobits, dari siapa aku mencuri beberapa kode. Juga, pengiriman ini belum selesai, karena hanya berhenti melakukan apa pun begitu jalan dibangun.

Sunting: Jika jalur dibangun, Connector mencoba membuat beberapa jalur di sepanjang jalur yang ada.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Connector {
    private static final int INACTIVE = 0;
    private static final int ACTIVE   = 1;
    private static final int BROKEN   = 2;
    private static final int MINE     = 3;

    private int size = 0;
    private int[][] grid = new int[size][size];
    private Point previousCell = null;
    private final List<Point> path = new ArrayList<>();

    public static void main(String[] args) {
        new Connector().start();
    }

    private void start() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                String input = reader.readLine();
                act(input);
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(0);
            }
        }
    }

    private void act(String input) throws Exception {
        String[] msg = input.split(" ");
        String output = "";
        int turn;
        switch(msg[0]){
        case "BEGIN":
            size = Integer.parseInt(msg[3]);
            grid = new int[size][size];
            break;
        case "DESTROY":
            output = "NONE";
            break;
        case "BROKEN":
            update(msg, true);
            break;
        case "ACTIVATE":
            turn = Integer.parseInt(msg[1]);
            output = activate(turn);
            break;
        case "OWNED":
            update(msg, false);
            break;
        case "SCORE":
            System.exit(0);
            break;
        }
        if (output.length() > 0) {
            System.out.println(output);
        }
    }

    private String activate(int turn) {
        if (turn == 0) {
            Random r = new Random();
            previousCell = new Point(r.nextInt(size), 0);
            return "VERTEX " + previousCell.x + "," + 0;
        }
        Point lastCell = findLastPathCell(previousCell.x, previousCell.y);
        if (lastCell.y == size-1) {
            //path is done
            Point extendingPathPoint = findExtendingPathPoint();
            if (extendingPathPoint == null) {
                return "NONE";
            }
            return "VERTEX " + extendingPathPoint.x + "," + extendingPathPoint.y;
        } else {
            int x = findBestX(lastCell.x, lastCell.y);
            return "VERTEX " + x + "," + (lastCell.y + 1);
        }
    }

    private int findBestX(int x, int y) {
        int bestScore = Integer.MIN_VALUE;
        int bestX = 0;
        for (int i = -1; i <= 1; i++) {
            int newY = y + 1;
            int newX = (x + i + size) % size;
            int score = calcCellScore(newX, newY, 10);
            if (score > bestScore) {
                bestScore = score;
                bestX = newX;
            } else if (score == bestScore && Math.random() < 0.3) {
                bestX = newX;
            }
        }
        return bestX;
    }

    private int calcCellScore(int x, int y, int depth) {
        int newY = y + 1;
        if (depth < 0) {
            return 1;
        }
        if (newY >= size)
            return 100;
        int cellScore = 0;
        for (int i = -1; i <= 1; i++) {
            int newX = (x + i + size) % size;
            if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
                cellScore += 5;
            } else if (grid[newX][newY] == INACTIVE) {
                cellScore += 1;             
            } else {
                cellScore -= 2;
            }
            cellScore += calcCellScore(newX, newY, depth -1);
        }
        return cellScore;
    }

    private Point findLastPathCell(int x, int y) {
        Point thisCell = new Point(x,y);
        int newY = y + 1;
        if (newY >= size) {
            return thisCell;
        }
        List<Point> endCells = new ArrayList<>();
        endCells.add(thisCell);
        path.add(thisCell);
        for (int i = -1; i <= 1; i++) {
            int newX = (x + i + size) % size;
            if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
                endCells.add(findLastPathCell(newX, newY));
            }
        }
        int bestY = -1;
        Point bestPoint = null;
        for (Point p : endCells) {
            if (p.y > bestY) {
                bestY = p.y;
                bestPoint = p;
            }
        }
        return bestPoint;
    }

    private Point findExtendingPathPoint() {
        if (path.size() == 0)
            return null;
        Random rand = new Random();
        for (int i = 0; i < size; i++) {
            Point cell = path.get(rand.nextInt(path.size()));
            for (int j = -1; j <= 1; j += 2) {
                Point newCellX = new Point((cell.x + j + size) % size, cell.y);
                if (grid[newCellX.x][newCellX.y] == INACTIVE)
                    return newCellX;

                Point newCellY = new Point(cell.x, cell.y + j);
                if (cell.y < 0 || cell.y >= size)
                    continue;
                if (grid[newCellY.x][newCellY.y] == INACTIVE)
                    return newCellY;
            }
        }
        return null;
    }

    private void update(String[] args, boolean destroyPhase) {
        for(int i = 2; i < args.length; i++) {
            String[] tokens = args[i].split(",");
            if(tokens.length > 1){
                int x = Integer.parseInt(tokens[0]);
                int y = Integer.parseInt(tokens[1]);
                if (grid[x][y] == INACTIVE) {
                    if (destroyPhase) {
                        grid[x][y] = BROKEN;
                    } else if (i == 2) {
                        grid[x][y] = MINE;
                        path.add(new Point(x,y));
                        previousCell = new Point(x,y);
                    } else {
                        grid[x][y] = ACTIVE;
                    }
                }
            }
        }
    }
}
CommonGuy
sumber
@ Zgarb Maaf, saya membuat bug sambil memperbaiki yang lainnya. Ini berfungsi sekarang
CommonGuy
@ Manu, ada baiknya Anda kembali ke permainan. Ada terlalu banyak pengeksploitasi dan tidak cukup banyak pembangun. Dengan Connector berjalan, game mungkin menjadi lebih menarik (lebih dari 1 game di 100 dengan skor).
Logic Knight
Connector membutuhkan 28 detik untuk merespons di salah satu game terbaru (lihat log). Sepertinya itu berlari ke Semangka dan kesulitan menentukan ke mana harus pergi berikutnya.
Zgarb
Aku berlari beberapa permainan lagi dengan peningkatan Peacemaker, dan Connector melemparkan kesalahan: java.lang.ArrayIndexOutOfBoundsException: -1 at Connector.findExtendingPathPoint(Connector.java:166).
Zgarb
7

Funnelweb, Python 2

versi 1.2 - Kode bergabung lebih baik, menambahkan animasi baru

Dinamai berdasarkan salah satu laba-laba Australia yang kurang bersahabat. Bot ini pertama kali membangun sarang berbentuk corong di baris atas, lalu memikat bot lain ke jalur pembangunan untuk lalu lintas ke sarang.

Berikut ini adalah animasi baru dari game 6 bot pada papan 4 / 3N ^ 2 yang menunjukkan funnelweb dan beberapa bot yang lebih sederhana:

bots6.gif

Kode Python corong:

from random import *
import sys
ME = 0
def pt(x,y): return '%u,%u' % (x % side_len, y)

while True:
    msg = raw_input().split()

    if msg[0] == 'BEGIN':
        turn = 0
        numbots, turns, side_len = map(int, msg[1:])
        R = range(side_len)
        top = side_len - 1
        grid = dict((pt(x, y), []) for x in R for y in R)
        mynodes = set()
        deadnodes = set()
        freenodes = set(grid.keys())
        mycol = choice(R)
        extra = sample([pt(x,top) for x in R], side_len)
        path = [(mycol, y) for y in range(top, top - side_len/6, -1)]
        moves = []
        fence = []
        for x,y in path:
            moves.append( [pt(x,y), pt(x+1,y), pt(x-1,y)] )
            fence.extend( [pt(x+1,y), pt(x-1,y)] )
        for dx in range(2, side_len):
            fence.extend( [pt(x+dx,y), pt(x-dx,y)] )
        for x,y in [(mycol, y) for y in 
                range(top - side_len/6, top - 3*side_len/4, -1)]:
            moves.append( [pt(x,y), pt(x+1,y), pt(x-1,y)] )

    elif msg[0] == 'DESTROY':
        target = 'NONE'
        while fence:
            loc = fence.pop(0)
            if loc in freenodes:
                target = 'VERTEX ' + loc
                break
        print target
        sys.stdout.flush()

    elif msg[0] == 'BROKEN':
        for rid, loc in enumerate(msg[2:]):
            if loc != 'N':
                grid[loc] = None
                deadnodes.add(loc)
                freenodes.discard(loc)
                if loc in extra: extra.remove(loc)

    elif msg[0] == 'ACTIVATE':
        target = 'NONE'
        while moves:
            loclist = moves.pop(0)
            goodlocs = [loc for loc in loclist if loc in freenodes]
            if goodlocs:
                target = 'VERTEX ' + goodlocs[0]
                break
        if target == 'NONE':
            if extra:
                target = 'VERTEX ' + extra.pop(0)
            else:
                target = 'VERTEX ' + pt(choice(R), choice(R))
        print target
        sys.stdout.flush()

    elif msg[0] == 'OWNED':
        for rid, loc in enumerate(msg[2:]):
            if loc != 'N':
                grid[loc].append(rid)
                if rid == ME:
                    mynodes.add(loc)
                freenodes.discard(loc)
                if loc in extra: extra.remove(loc)
        turn += 1

    elif msg[0] == 'SCORE':
        break

Laba-laba dijalankan bersama python funnelweb.py.

Ksatria Logika
sumber
Mengubah algoritma dan mengujinya. Itu harus dijalankan sekarang.
Logic Knight
Bagus sekali sekarang!
Zgarb
6

Pos pemeriksaan, Jawa

Bot ini mencoba membuat pos pemeriksaan sehingga setiap jalur yang valid melewati salah satu simpul saya. Karena ada N 2 belokan dan papan 2N 2 melintang, saya dapat mengaktifkan / memecah setiap node pada satu garis horizontal tunggal (dengan asumsi saya di sana terlebih dahulu). Lakukan ini dalam pola bolak-balik ( xrusak, omilik saya):

xoxoxoxoxoxox...

Jika Anda ingin membuat jalur, Anda harus melewati pos pemeriksaan saya :)

Sekarang, ada beberapa masalah yang mungkin dihadapi. Pertama, itu tidak akan bekerja dengan baik sama sekali kecuali ada banyak jalan. Karena ia tidak membuat setiap jalur produktif dirinya sendiri, ia benar-benar benar-benar bergantung pada adanya beberapa pesaing. Bahkan beberapa pesaing yang bergabung untuk membuat jalur tunggal tidak akan banyak membantu, karena ia hanya mendapat skor satu tempat untuk setiap jalur yang ditemukan. Apa yang dia butuhkan untuk bersinar mungkin beberapa bot membuat beberapa jalur yang berbeda. Meskipun begitu, skornya mungkin tidak terlalu tinggi, tetapi itu adalah ide yang saya miliki dalam obrolan, jadi ...

Jika salah satu spasi pada baris diblokir / diklaim sudah, saya hanya mencari tempat terdekat yang dapat saya gunakan (lebih disukai pada xbaris yang sama , hanya bergeser secara vertikal).


import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Checkpoint {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true)
            try {
                String input = reader.readLine();
                act(input);
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(0);
            }
    }

    static void act(String input) throws Exception{
        String[] msg = input.split(" ");
        String output = "";
        int turn;
        boolean found = false;
        switch(msg[0]){
        case "BEGIN":
            size = Integer.parseInt(msg[3]);
            grid = new int[size][size];
            target = size/2;
            break;
        case "DESTROY":
            turn = Integer.parseInt(msg[1]);
            for(int x=0;x<size;x+=2)
                for(int y=0;y<size&&!found;y++)
                    if(grid[(x+turn*2)%size][(y+target)%size]==INACTIVE){
                        output = "VERTEX " + ((x+turn*2)%size) + "," + ((y+target)%size);
                        found = true;
                    }
            if(output.length() < 1)
                output = "NONE";
            break;
        case "BROKEN":
            for(int i=2;i<msg.length;i++){
                String[] tokens = msg[i].split(",");
                if(tokens.length>1){
                    int x = Integer.parseInt(tokens[0]);
                    int y = Integer.parseInt(tokens[1]);                    
                    if(grid[x][y]==INACTIVE)
                        grid[x][y] = BROKEN;
                }
            }
            break;
        case "ACTIVATE":
            turn = Integer.parseInt(msg[1]);
            for(int x=1;x<size;x+=2)
                for(int y=0;y<size&&!found;y++)
                    if(grid[(x+turn*2)%size][(y+target)%size]==INACTIVE){
                        output = "VERTEX " + ((x+turn*2)%size) + "," + ((y+target)%size);
                        found = true;
                    }
            if(output.length() < 1)
                output = "NONE";
            break;
        case "OWNED":
            for(int i=2;i<msg.length;i++){
                String[] tokens = msg[i].split(",");
                if(tokens.length>1){
                    int x = Integer.parseInt(tokens[0]);
                    int y = Integer.parseInt(tokens[1]);
                    if(i==2){
                        if(grid[x][y]==INACTIVE)
                            grid[x][y] = MINE;
                    }else{
                        if(grid[x][y]==INACTIVE)
                            grid[x][y]=ACTIVE;
                    }
                }
            }
            break;
        case "SCORE":
            System.exit(0);
            break;
        }
        if(output.length()>0)
            System.out.println(output);
    }

    static int size = 2;
    static int target = size/2;
    static int[][] grid = new int[size][size];

    static final int INACTIVE = 0;
    static final int ACTIVE   = 1;
    static final int BROKEN   = 2;
    static final int MINE     = 3;
}

Untuk mengkompilasi, itu javac Checkpoint.java. Untuk menjalankan java Checkpoint,. Anda ingin menambahkan / mengubah jalur untuk mencerminkan di mana pun itu.

Geobit
sumber
5

Semangka, Jawa

Mencoba menggambar semangka di grid.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Watermelon {

    private static int numberOfBots;
    private static int numberOfTurns;
    private static int sideLength;

    private static int turn = 0;

    private static int[][] theGrid;

    private static final int INACTIVE = -2;
    private static final int BROKEN   = -1;
    private static final int MINE     =  0;
    private static final int ACTIVE   =  1;

    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static PrintStream out = System.out;

    public static void main(String[] args) throws IOException {
        while (true){
            String[] input = in.readLine().trim().split(" ");
            String instruction = input[0];
            switch (instruction){
                case "BEGIN":
                    begin(input);
                    break;
                case "DESTROY":
                    destroy(input);
                    break;
                case "BROKEN":
                    broken(input);
                    break;
                case "ACTIVATE":
                    activate(input);
                    break;
                case "OWNED":
                    owned(input);
                    break;
                default:
                    return;
            }
            out.flush();
        }
    }

    private static void begin(String[] input) {
        numberOfBots = Integer.parseInt(input[1]);
        numberOfTurns = Integer.parseInt(input[2]);
        sideLength = Integer.parseInt(input[3]);
        theGrid = new int[sideLength][sideLength];
        for (int x = 0; x < sideLength; x++){
            for (int y = 0; y < sideLength; y++){
                theGrid[x][y] = INACTIVE;
            }
        }
    }

    private static void owned(String[] input) {
        turn = Integer.parseInt(input[1]);
        for (int i = input.length - 1; i >= 2; i--){
            if (input[i].equals("N")){
                continue;
            }
            String[] coordinates = input[i].split(",");
            int x = Integer.parseInt(coordinates[0]);
            int y = Integer.parseInt(coordinates[1]);
            int player = i - 2;
            if (player == 0){
                theGrid[x][y] = MINE;
            } else {
                theGrid[x][y] = ACTIVE;
            }
        }
    }

    private static void activate(String[] input) {
        turn = Integer.parseInt(input[1]);
        double[][] values = new double[sideLength][sideLength];
        List<Point> pointList = new ArrayList<>();
        for (int x = 0; x < sideLength; x++){
            for (int y = 0; y < sideLength; y++){
                if (theGrid[x][y] == MINE || theGrid[x][y] == ACTIVE){
                    for (int x1 = 0; x1 < sideLength; x1++){
                        for (int y1 = 0; y1 < sideLength; y1++){
                            double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
                            values[x1][y1] += 1 / (distance + 1);
                        }
                    }
                }
                pointList.add(new Point(x, y));
            }
        }
        pointList.sort(Comparator.comparingDouble((Point a) -> values[a.x][a.y]).reversed());
        for (Point point : pointList){
            if (theGrid[point.x][point.y] == INACTIVE){
                out.println("VERTEX " + point.x + "," + point.y);
                return;
            }
        }
        out.println("NONE");
    }

    private static void broken(String[] input) {
        turn = Integer.parseInt(input[1]);
        for (int i = 2; i < input.length; i++){
            if (input[i].equals("N")){
                continue;
            }
            String[] coordinates = input[i].split(",");
            int x = Integer.parseInt(coordinates[0]);
            int y = Integer.parseInt(coordinates[1]);
            theGrid[x][y] = BROKEN;
        }
    }

    private static void destroy(String[] input) {
        turn = Integer.parseInt(input[1]);
        double[][] values = new double[sideLength][sideLength];
        List<Point> pointList = new ArrayList<>();
        for (int x = 0; x < sideLength; x++){
            for (int y = 0; y < sideLength; y++){
                if (theGrid[x][y] == MINE){
                    for (int x1 = 0; x1 < sideLength; x1++){
                        for (int y1 = 0; y1 < sideLength; y1++){
                            double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
                            values[x1][y1] -= 1 / (distance + 1);
                        }
                    }
                }
                if (theGrid[x][y] == ACTIVE){
                    for (int x1 = 0; x1 < sideLength; x1++){
                        for (int y1 = 0; y1 < sideLength; y1++){
                            double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
                            values[x1][y1] += 1 / (distance + 1) / (numberOfBots - 1);
                        }
                    }
                }
                pointList.add(new Point(x, y));
            }
        }
        pointList.sort(Comparator.comparingDouble((Point a) -> values[a.x][a.y]).reversed());
        for (Point point : pointList){
            if (theGrid[point.x][point.y] == INACTIVE){
                out.println("VERTEX " + point.x + "," + point.y);
                return;
            }
        }
        out.println("NONE");
    }
}
TheNumberOne
sumber
5

FaucetBot (dalam R)

Membuat bottleneck di baris kedua, dan mengaktifkan node di jalur di belakangnya.

infile <- file("stdin")
open(infile)
repeat{
    input <- readLines(infile,1)
    args <- strsplit(input," ")[[1]]
    if(args[1]=="BEGIN"){
        L <- as.integer(args[4])
        M <- N <- matrix(0,nrow=L,ncol=L)
        x0 <- sample(2:(L-1),1)
        }
    if(args[1]=="DESTROY"){
        if(args[2]==0){
            X <- x0
            Y <- 2
            }else{
                free <- which(M[,2] == 0)
                mine <- which(N[,2] == 1)
                X <- free[which.min(abs(free-mine))]
                Y <- 2
                }
        if(length(X)){cat(sprintf("VERTEX %s,%s\n",X-1,Y-1))}else{cat("NONE\n")}
        flush(stdout())
        }
    if(args[1]=="BROKEN"){
        b <- strsplit(args[args!="N"][-(1:2)],",")
        o <- strsplit(args[3],",")[[1]]
        b <- lapply(b,as.integer)
        if(o[1]!="N") N[as.integer(o[1])+1,as.integer(o[2])+1] <- -1
        for(i in seq_along(b)){M[b[[i]][1]+1,b[[i]][2]+1] <- -1}
        }
    if(args[1]=="ACTIVATE"){
        if(args[2]==0){
            broken <- which(M[,2] == -1)
            free <- which(M[,2] == 0)
            X <- free[which.min(abs(broken-free))]
            Y <- 2
            }else{
                y <- 3
                X <- NULL
                while(length(X)<1){
                    lastrow <- which(N[,y-1]==1)
                    newrow <- unlist(sapply(lastrow,function(x)which(M[,y]==0 & abs((1:L)-x)<2)))
                    if(length(newrow)){
                        X <- sample(newrow,1)
                        Y <- y
                        }
                    y <- y+1
                    if(y>L){X <- x0; Y <- 1}
                    }
                }
        cat(sprintf("VERTEX %s,%s\n",X-1,Y-1))
        flush(stdout())
        }
    if(args[1]=="OWNED"){
        b <- strsplit(args[args!="N"][-(1:2)],",")
        o <- strsplit(args[3],",")[[1]]
        b <- lapply(b,as.integer)
        if(o[1]!="N") N[as.integer(o[1])+1,as.integer(o[2])+1] <- 1
        for(i in seq_along(b)){M[b[[i]][1]+1,b[[i]][2]+1] <- 1}
        }
    if(args[1]=="SCORE") q(save="no")
    }

Jika saya tidak mengacau, konfigurasi akhir harus seperti:

........    .a..aa..
..aaa...    ..aaa...
.xxaxx..    xxxaxxx.    etc.
........    ........

Perintah adalah Rscript FaucetBot.R.

plannapus
sumber
5

Pembuat perdamaian, Jawa

Berdasarkan kode Manu.

Zona konflik pencarian pembuat perdamaian (yaitu kebanyakan titik puncak BROKEN atau ACTIVE) dan mengaktifkan titik acak terdekat.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.IntStream;

public class Peacemaker {
    private static final int INACTIVE = 0;
    private static final int ACTIVE   = 1;
    private static final int BROKEN   = 2;
    private static final int MINE     = 3;

    private int size = 0;
    private int[][] grid = new int[size][size];
    private int startingPoint = 0;

    public static void main(String[] args) {
        new Peacemaker().start();
    }

    private void start() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                String input = reader.readLine();
                act(input);
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(0);
            }
        }
    }

    private void act(String input) throws Exception {
        String[] msg = input.split(" ");
        String output = "";
        int turn;
        switch(msg[0]){
        case "BEGIN":
            size = Integer.parseInt(msg[3]);
            grid = new int[size][size];
            break;
        case "DESTROY":
            output = "NONE";
            break;
        case "BROKEN":
            update(msg, true);
            break;
        case "ACTIVATE":
            turn = Integer.parseInt(msg[1]);
            output = activate(turn);
            break;
        case "OWNED":
            update(msg, false);
            break;
        case "SCORE":
            System.exit(0);
            break;
        }
        if (output.length() > 0) {
            System.out.println(output);
        }
    }

    private String activate(int turn) {
        Random r = new Random();
        if (turn == 0) {
            startingPoint = r.nextInt(size);
            return "VERTEX " + startingPoint + "," + 0;
        } else {

            Point point = searchConflicts();

            int posX = point.x;
            int posY = point.y;

            while (grid[posX][posY] != INACTIVE) {
                 int previousX = (posX - 1 < 0 ? size - 1 : posX - 1);
                 int nextX = (posX + 1 > size - 1 ? 0 : posX + 1);
                 int previousY = (posY - 1 < 0 ? size - 1 : posY - 1);
                 int nextY = (posY + 1 > size - 1 ? 0 : posY + 1);

                 int choice = r.nextInt(4);
                 switch (choice) {
                     case 0: posX = previousX; break;
                     case 1: posX = nextX; break;
                     case 2: posY = previousY; break;
                     case 3: posY = nextY; break;
                 }
            }

            return "VERTEX " + posX + "," + posY;
        }
    }

    private Point searchConflicts() {

        int previousCellScore = 0;
        int cellX = 0;
        int cellY = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j ++) {
                if (previousCellScore < adjacentCellsScore(i, j)) {
                    cellX = i; cellY = j;
                    previousCellScore = adjacentCellsScore(i, j);
                }
            }
        }
        return new Point(cellX, cellY);
    }

    /*  Format of adjacent cells :
     * 
     *   0 1 2
     *   3 . 4
     *   5 6 7
     */
    private int adjacentCellsScore(int x, int y) {

        int[] scores = new int[8];

        int previousX = (x - 1 < 0 ? size - 1 : x - 1);
        int nextX = (x + 1 > size - 1 ? 0 : x + 1);
        int previousY = (y - 1 < 0 ? size - 1 : y - 1);
        int nextY = (y + 1 > size - 1 ? 0 : y + 1);

        scores[0] = calcScore(previousX, nextY);
        scores[1] = calcScore(x, nextY);
        scores[2] = calcScore(nextX, nextY);
        scores[3] = calcScore(previousX, y);
        scores[4] = calcScore(nextX, y);
        scores[5] = calcScore(previousX, previousY);
        scores[6] = calcScore(x, previousY);
        scores[7] = calcScore(nextX, previousY);

        return IntStream.of(scores).reduce(0, (a, b) -> a + b);
    }

    private int calcScore(int x, int y) {
        int activeScore = 2;
        int mineScore = 1;
        int inactiveScore = 0;
        int brokenScore = 3;

        if (grid[x][y] == ACTIVE) 
            return activeScore;
        else if (grid[x][y] == MINE)
            return mineScore;
        else if (grid[x][y] == INACTIVE) 
            return inactiveScore;
        else if (grid[x][y] == BROKEN) 
            return brokenScore;
        else
            return 0;
    }


    private void update(String[] args, boolean destroyPhase) {
        for(int i = 2; i < args.length; i++) {
            String[] tokens = args[i].split(",");
            if(tokens.length > 1){
                int x = Integer.parseInt(tokens[0]);
                int y = Integer.parseInt(tokens[1]);
                if (grid[x][y] == INACTIVE) {
                    if (destroyPhase) {
                        grid[x][y] = BROKEN;
                    } else if (i == 2) {
                        grid[x][y] = MINE;
                    } else {
                        grid[x][y] = ACTIVE;
                    }
                }
            }
        }
    }       
}
Thrax
sumber
@ Zgarb Terima kasih, saya harus menyelesaikan masalah ini sekarang.
Thrax
Peacemaker bekerja sekarang, dan termasuk dalam leaderboard. Namun, sepertinya tidak terlalu berpengaruh, jadi mungkin masih ada beberapa bug yang tersisa.
Zgarb
Sebenarnya, melihat kode Anda, saya pikir masalahnya ada di whileloop activatemetode. Anda menghentikan pencarian begitu Anda menemukan titik yang bukan milik Anda dan tidak rusak - tetapi bisa dimiliki oleh orang lain, sehingga Anda tidak dapat mengaktifkannya.
Zgarb
@Zgarb Saya salah membaca spesifikasi dan berpikir banyak pemain bisa mengaktifkan titik yang sama kapan saja. Saya kira saya hanya perlu mengubah pencarian saya dan mencari vertex tidak aktif saja.
Thrax
2

Pembangun Acak, Python 3

Ini adalah contoh bot bodoh yang tidak pernah menghancurkan apa pun, dan mencoba mengaktifkan simpul acak setiap belokan. Perhatikan bahwa tidak perlu memeriksa apakah titik tidak aktif; controller menangani itu.

import random as r

while True:
    msg = input().split()
    if msg[0] == "BEGIN":
        side_len = int(msg[3])
    elif msg[0] == "DESTROY":
        print("NONE")
    elif msg[0] == "ACTIVATE":
        print("VERTEX %d,%d"%(r.randrange(side_len), r.randrange(side_len)), flush=True)
    elif msg[0] == "SCORE":
        break

Jalankan dengan perintah

python3 random_builder.py

Anda mungkin perlu mengganti python3dengan pythonbergantung pada instalasi Python Anda. Untuk melakukan ini, cukup edit bots.txtfile. Saya memperbarui controller, dan tidak perlu lagi mengacaukan path file.

Zgarb
sumber
Karena Anda menggunakan python 3, alih-alih sys.stdout.flush()Anda bisa melakukannya flush=Truesebagai argumen print.
matsjoyce
@matsjoyce Terima kasih, saya tidak tahu itu. Saya akan mengedit versi repositori nanti.
Zgarb
2

Explorer, Python 3

Strategi aktivasi:

Membuat peta panas berdasarkan keadaan setiap simpul (aktif / tidak aktif / rusak) dan memilih simpul yang akan memiliki nilai peta panas terbesar yang diharapkan per orang jika akan memilih yang itu.

Strategi penghancuran:

Jangan pernah menghancurkan apa pun karena itu tidak banyak membantu bot.

import sys

class bd:

    def __init__(s, l):

        s.l=l
        s.b=[]
        s.v=[]
        s.m=[]
        s.bm=[]
        s.utd=False #up_to_date
        s.bmc=1

        for i in range(s.l):
            s.b+=[[]]
            s.v+=[[]]
            s.m+=[[]]
            s.bm+=[[]]
            for k in range(s.l):
                s.b[i]+=[0]
                s.v[i]+=[0]
                s.m[i]+=[0]
                s.bm[i]+=[s.bmc]

    def update(s):
        s.utd=True

        vu=[]
        vd=[]
        for i in range(s.l):
            vu+=[[]]
            vd+=[[]]
            for k in range(s.l):
                vu[i]+=[1]
                vd[i]+=[1]

        #spread up
        for i in range(s.l):
            vu[i][0]*=s.bm[i][0]

        for k in range(1,s.l):
            for i in range(s.l):
                sumv=vu[(i-1)%s.l][k-1]+vu[(i)%s.l][k-1]+vu[(i+1)%s.l][k-1]  
                vu[i][k]*=sumv*s.bm[i][k]/3

        #spread down
        t=s.l-1
        for i in range(s.l):
            vd[i][t]*=s.bm[i][t]

        for k in range(s.l-2,-1,-1):
            for i in range(s.l):
                sumv=vd[(i-1)%s.l][k+1]+vd[(i)%s.l][k+1]+vd[(i+1)%s.l][k+1]  
                vd[i][k]*=sumv*s.bm[i][k]/3

        #mult
        for i in range(s.l):
            for k in range(s.l):
                if s.b[i][k]==-1 or s.m[i][k]==1:
                    s.v[i][k]=float(-1)
                else:
                    s.v[i][k]=vu[i][k]*vd[i][k]/(s.b[i][k]+1)

    def add_act(s,al):
        s.utd=False

        for ind, ap in enumerate(al):
            i,k=ap
            s.b[i][k]+=1            
            s.bm[i][k]=2*s.bmc            
            #doesn't work alone WHY???
            if ind==0: s.m[i][k]=1

    def add_ina(s,il):
        s.utd=False

        for ind, ip in enumerate(il):
            i,k=ip
            s.b[i][k]=-1
            s.bm[i][k]=0                    

    def get_newact(s):
        s.update()
        vm=-28
        pm=None
        for i in range(s.l):
            for k in range(s.l):
                if s.v[i][k]>vm:
                    vm=s.v[i][k]
                    pm=(i,k)
        #doesn't work alone WHY???
        s.m[pm[0]][pm[1]]=1
        return pm


b=None

while True:
    inp=input()
    msg = inp.split()
    if msg[0] == "BEGIN":        
        b = bd(int(msg[3]))
    elif msg[0] == "DESTROY":
        print("NONE")
    elif msg[0] == "BROKEN":
        pl=[]
        for m in msg[2:]:
            if m!='N':
                pl+=[tuple(map(int,m.split(',')))]
        b.add_ina(pl)
    elif msg[0] == "ACTIVATE":
        at=b.get_newact()
        print("VERTEX %d,%d"%(at[0], at[1]))
    elif msg[0] == "OWNED":
        pl=[]
        for m in msg[2:]:
            if m!='N':
                pl+=[tuple(map(int,m.split(',')))]        
        b.add_act(pl)
    elif msg[0] == "SCORE":
        break       

    sys.stdout.flush()
randomra
sumber
1

Gangguan, Bash

#!/bin/bash

declare -A avail
broken=
owned=

while read c p
    case "$c" in
        ACTIVATE|BROKEN) v=broken;;
        *) v=owned
    esac
    case "$c" in
        BEGIN)
            read b t n <<<"$p"
            list=$(
                eval "echo {0..$((n-1))},{0..$((n-1))}\$'\\n'" |
                shuf
            )
            for i in $list; do
                avail[$i]=1
            done;;
        DESTROY|ACTIVATE)
            for t in $(
                for i in ${!v}; do
                    [ "$i" != N ] &&
                    if [ "$c" = ACTIVATE ]; then
                        echo $(((${i%,*}+2)%n)),${i#*,}
                        echo $(((${i%,*}-2+n)%n)),${i#*,}
                    else
                        echo ${i%,*},$(((${i#*,}+1)%n))
                        echo ${i%,*},$(((${i#*,}-1+n)%n))
                    fi
                done |
                shuf
            ) $list; do
                [ "${avail[$t]}" ] && echo VERTEX $t && break
            done ||
            echo NONE;;
        BROKEN|OWNED)
            read x m $v <<<"$p";
            for i in $m ${!v}; do
                unset avail[$i]
            done;;
        SCORE)! :
    esac
do :;done

Mencoba membuat hasilnya terlihat lebih menarik.

Jalankan dengan bash annoyance.sh.

jimmy23013
sumber
1
Bot Anda mencetak semua inputnya ke STDERR. Ini tidak dilarang atau apa pun, hanya gangguan (pun intended).
Zgarb
@ Zgarb Maaf, saya menyisipkan versi yang salah. Tetap.
jimmy23013
1

Manusia Tengah

Saya melihat beberapa bot dibangun dari atas, dan beberapa dari bawah. Ini adalah yang pertama (saya pikir) untuk memulai di tengah dan bekerja naik turun.

(tidak diuji dengan controller, jadi jika dosisnya tidak berfungsi, beri tahu saya.)

class Node

  def self.set_size s
    @@grid = Array.new(s,Array.new(s,0))
  end

  def initialize x,y
    @x=x
    @y=y
  end

  def offset dx,dy
    return Node.new @x+dx,@y+dy
  end

  def state
    return -1 if @x<0 || @y<0 || @x>=@@grid.length || @y>=@@grid.length
    @@grid[@x][@y]
  end

  def state= n
    return -1 if @x<0 || @y<0 || @x>=@@grid.length || @y>=@@grid.length
     @@grid[@x][@y]=n
  end

  def active?
    state > 0
  end

  def open?
    state == 0
  end
  attr_reader :x,:y

  def to_s
    "VERTEX #{@x},#{@y}"
  end


  def scan_down
    ans = nil
    [0,-1,1].each do|offset|
      n = Node.new @x+offset,@y-1
      ans = (ans||n) if n.open?
      ans = (n.scan_down||ans) if n.active?
    end
    return ans
  end

  def scan_up
    ans = nil
    [0,-1,1].each do|offset|
      n = Node.new @x+offset,@y+1
      ans = (ans||n) if n.open?
      ans = (n.scan_up||ans) if n.active?
    end
    return ans
  end

end

input = gets.split
input.shift

BotCount = input.shift.to_i
Turns = input.shift.to_i
GridSize = input.shift.to_i

Node.set_size GridSize

midRow = GridSize/2

toDestroy = (0...GridSize).map{|i|Node.new i,midRow}
toDestroy.reject!{|n| n.x==midRow}

chain = []
Turns.times do
  gets;
  toDestroy.each{|x|
    if x.active?
      toDestroy.push x.offset 0,1
      toDestroy.push x.offset 1,1
      toDestroy.push x.offset -1,1
    end
  }
  toDestroy.reject!{|x|!x.open?}
  puts toDestroy.sample
  input = gets.split
  input.shift;input.shift
  input.each{|str|
    a,b = str.split ','
    (Node.new a.to_i,b.to_i).state=1
  }
  gets;

  if chain.length == 0
    n = Node.new midRow,midRow
    until n.open?
      n = Node.new n.x+1,midRow
    end
    puts chain[0]=n
  elsif rand>0.5
    n=nil
    loop do
      h=chain[0]
      n = h.scan_down
     break if !n
      chain.shift
    end
    h.unshift n
    puts n
  else
    loop do
      h=chain[-1]
      n = h.scan_up
      h.pop if !n
      brake if n
    end
    chain.push n
    puts n
  end

  input = gets.split
  input.shift;input.shift
  input.each{|str|
    a,b = str.split ','
    (Node.new a,b).state=-1
  }

end
gets
exit
MegaTom
sumber
Terima kasih atas kirimannya! Sayangnya, tantangan ini tidak aktif selama hampir setengah tahun, dan saat ini saya tidak dapat menjalankan sebagian besar bot, karena saya tidak memiliki akses ke komputer tempat saya dapat menginstal bahasa.
Zgarb
1
@ Zgarb saya mengerti. mungkin suatu hari nanti saya akan menjawab tantangan dalam kerangka waktu yang masuk akal ...
MegaTom