KoTH: Political Simulator

Question

Nadeszły wybory, a Twoim zadaniem jest pokonanie konkurenta w bezpośredniej rywalizacji! Oboje próbujecie zdobyć 256-osobowe miasto w siatce 16x16. W tej chwili miasto nie zostało jeszcze podzielone na regiony do głosowania, ale tu właśnie przydają się twoje umiejętności związane z gerrymanderingiem! Możesz także prowadzić kampanię w dowolnych obszarach miasta, aby zdobyć poparcie.

Generał

Wszystkie boty (funkcje JS) będą uruchamiane przeciwko wszystkim innym robotom raz na grę. W każdej grze miasto zaczyna się od wszystkich wyborców neutralnych. Gra będzie śledzić liczbę dla każdego wyborcy, określając, kogo popierają. Z punktu widzenia konkretnego bota liczba dodatnia oznacza, że ​​głosujący będzie na niego głosował, natomiast liczba ujemna to głos na przeciwnika. Zero jest neutralne.

Miasto jest podzielone na 16 bloków, z których wszystkie składają się z kwadratów 4x4. Regiony do głosowania składają się z co najmniej jednego bloku. Początkowo jest ich 16, a każdy blok ma swój własny region.

Oba boty zaczynają od 100 $ i mogą poruszać się raz na turę. Te ruchy są wykonywane jednocześnie, więc nie ma przewagi w pierwszej turze. Ruchy dzielą się na cztery kategorie:

• Kampania: To spowoduje, że każda osoba na określonym obszarze zwiększy swoje poparcie dla kandydata, który prowadzi kampanię. To, ile się zmienia, zależy od sąsiadów.
• Ankieta: Dzięki temu każda osoba uzyska poparcie dla kandydata w określonej dziedzinie.
• Przekupstwo: spowoduje to, że dana osoba zwiększy swoje poparcie dla kandydata.
• Łączenie / rozdzielanie regionów: zmieni to kształt regionów objętych głosowaniem.

Pod koniec każdej tury, po przeniesieniu się obu kandydatów, obaj otrzymają 10 $.

Detale

Dozwolone są następujące ruchy. Jeśli zostanie podany nieprawidłowy ruch (niewystarczające pieniądze lub nieprawidłowe współrzędne), tura bota zostanie pominięta.

Wszystkie współrzędne powinny znajdować się w obrębie 0 <= n < 16, a dla drugiej pary w prostokątnych obszarach ograniczających 0 <= n <= 16(ponieważ są one wyłączne ).

• campaign([x, y], [x, y]): Kampania w granicach wyznaczonych przez dwie pary współrzędnych
  • Kosztuje 1 dolara za osobę dotkniętą chorobą
  • Każda osoba w okolicy zmieni swoje wsparcie zgodnie z następującymi zasadami:
    • Dla wszystkich sąsiadów sąsiadujących prostopadle (w tym przekątnych) dodaj 0,1 poparcia dla dowolnego kandydata, którego poparcie większości (ważone) lub 0,2, jeśli ich łączne poparcie wynosi co najmniej 2 dla tego kandydata
    • Dodaj 0,25 dla kandydata prowadzącego kampanię
• poll([x, y], [x, y]): Sonda w granicach wyznaczonych przez dwie pary współrzędnych
  • Kosztuje 0,25 USD na ankietowaną osobę, po zaokrągleniu w górę
  • W następnej turze o każdej osobie w obszarze (po ruchu przeciwnika) podawane są następujące informacje:
    • Poparcie dla ankietowanego, gdzie liczby dodatnie oznaczają głos na niego, a liczby ujemne - głos na przeciwnika
• bribe([x, y]): Przekup osobę w miejscu określonym przez parę współrzędnych
  • Kosztuje co najmniej 5 USD
    • Za każdym razem, gdy osoba w bloku głosującym ( nie w regionie głosowania) została przekupiona, dodaj 1 $
  • Dodaj do 3,5 wsparcia dla przekupującego kandydata
    • Za każdym razem, gdy osoba z bloku wyborczego została przekupiona, dodane poparcie zmniejsza się o 0,15
    • Ostatecznie może to spowodować przekupienie kogoś w bloku wyborczym, aby zmniejszyć jego poparcie dla kandydata
• merge([x, y], [x, y]): Scal regiony głosowania określone przez dwie pary współrzędnych
  • Kosztuje 25 $ za każdy blok w nowo utworzonym regionie (jeden blok jest darmowy)
  • Wymaga dotykania regionów, w których znajdują się dwie określone osoby
    • Zwróć uwagę, że współrzędne odpowiadają ludziom, a nie blokom. Aby odnieść się do bloku, wystarczy pomnożyć jego współrzędne przez 4
• unmerge([x, y]): Rozdziel region głosowania określony przez parę współrzędnych
  • Kosztuje 25 $ za każdy blok w regionie
  • Każdy blok w regionie staje się własnym regionem

Jeśli oba boty spróbują połączyć lub rozłączyć się w tej samej turze (nawet jeśli nie będą przeszkadzać), obie tury zostaną pominięte i żadne z nich nic nie zapłaci. Ruchy będą przetwarzane w następującej kolejności (kolejność pozostałych nie ma znaczenia):

1. Łapówki
2. Wsparcie sąsiadów w prowadzeniu kampanii
3. Wsparcie kandydatów w kampingingu

Zwycięski

Pod koniec każdej tury, po przeniesieniu się obu kandydatów, do wszystkich regionów zostaną dodane głosy. Każda osoba albo głosuje na jednego kandydata, albo będzie neutralna, niezależnie od tego, o ile (tj. Wynik +0,05 lub +30 byłby tutaj identyczny). Jeśli zostaną spełnione następujące warunki, odbędą się wybory i zostanie wybrany zwycięzca:

• Wszystkie regiony składają się z mniej niż połowy neutralnych wyborców
• Liczba regionów głosujących na każdego kandydata nie jest równa

I / O

Wszystkie boty należy zgłaszać w postaci funkcji Javascript. Następujące informacje zostaną przekazane jako argumenty funkcji:

• Tablica regionów głosowania reprezentowanych jako obiekty o następujących właściwościach:
  • blocks: Tablica bloków do głosowania, reprezentowana jako współrzędne [x, y]osoby w lewym górnym rogu (np. [4, 0]Lub [12, 12])
  • number_neutral: Liczba neutralnych osób w regionie
  • number_you: Liczba osób w regionie głosujących na bota
  • number_opponent: Liczba osób w regionie głosujących na przeciwnika bota
  • absolute_average: Średnia wartość bezwzględna poparcia społecznego dla kandydata
    • Wyższe liczby wskazują, że kampanie lub przekupywanie będą zazwyczaj mniej skuteczne
    • Dokładnie 0 oznaczałoby, że każda osoba w regionie jest neutralna
• Ilość pieniędzy, jaką posiada bot
• Obiekt zawierający wyniki ostatniego ruchu (pusty, chyba że była to ankieta)
  • Tablica peoplebędzie zawierała obiekty reprezentujące każdą odpytywaną osobę:
    • position: Współrzędne osoby w formacie [x, y]
    • region: Numerowany identyfikator regionu, w którym znajduje się osoba (indeks regionu w pierwszym argumencie)
    • support: Liczba wskazująca, czy osoba jest neutralna (0), głosuje na bota (pozytyw), czy głosuje na przeciwnika bota (negatyw)
  • Obiekt amountszawierający następujące właściwości:
    • number_neutral: Liczba neutralnych osób w regionie
    • number_you: Liczba osób w regionie głosujących na bota
    • number_opponent: Liczba osób w regionie głosujących na przeciwnika bota
    • absolute_average: Średnia wartość bezwzględna poparcia społecznego dla kandydata
• Przedmiot, który można wykorzystać do przechowywania między turami (ale nie między rundami / grami)

Aby przenieść, wynik należy zwrócić jedną z powyższych funkcji. Na przykład:

{
    "Example": (regions, money, result, storage) => {
        storage.block = ((storage.block || 0) + 1) % 16;
    
        return campaign(
            [(storage.block / 4 | 0) * 4, (storage.block % 4) * 4],
            [(storage.block / 4 | 0) * 4 + 4, (storage.block % 4) * 4 + 4]
        );
    }
}

Zasady

• Uruchomienie botów powinno zająć rozsądną ilość czasu
• Boty powinny grać uczciwie, nie wolno manipulować kontrolerem ani innymi zgłoszeniami w sposób niedozwolony tutaj
• Każdy bot zostanie raz zmierzony z każdym innym botem, a zwycięzcą zostanie bot, który wygrywa najczęściej
  • W przypadku remisu wygrywa wcześniejszy bot
• Nieprawidłowe wartości zwracane lub boty, które błędnie zakładają brak ruchu w turze
• Boty muszą być deterministyczne

Pomysł na wyzwanie i oryginalna propozycja piaskownicy od HyperNeutrino.

Kontroler: https://redwolfprograms.github.io/political-simulator
Pokój rozmów: tutaj
Termin: czwartek, 5 listopada 2020 r., UTC w południe (8:00 EST)

Answer 1

Abotcus

Okazuje się, że nie potrzebujesz tak wielu wymyślnych funkcji, aby być tak samo dobre lub lepsze niż Randgrab! Abotcus chwyta obszar na początku, a następnie stosuje prostą formułę do ważenia każdego bloku i wybiera blok o najlepszej wadze. Jeśli wygląda na to, że jest tam trochę niepotrzebnych rzeczy, to dlatego, że spodziewałem się dodać o wiele więcej wymyślnych funkcji ... ale po prostu nie musiałem ¯ \ _ (ツ) _ / ¯

(regions, money, result, storage) => {
    
    if(money == 100) {return campaign([9,1],[15,15])}
    
    var map = [[,,,],[,,,],[,,,],[,,,]];
    var weights = [[,,,],[,,,],[,,,],[,,,]];
    var blocks = [];
    
    for(var r of regions) {
        for(var b of r.blocks) {
            map[b[1]/4][b[0]/4] = b;
            weights[b[1]/4][b[0]/4] = weight(r.number_you, r.number_opponent, r.number_neutral, r.absolute_average)/r.blocks.length;
            blocks.push([b, weights[b[1]/4][b[0]/4]]);
        }
    }
    
    blocks.sort((a,b) => {
        return b[1]-a[1];
    });
    
    var start_block = blocks[0][0];
    
    console.log(blocks);
    
    if(money >= 16) {
        return campaign(start_block, [start_block[0]+4, start_block[1]+4]);
    } else {
        return campaign(start_block, [start_block[0]+3, start_block[1]+3]);
    }
    
    function weight(own, opp, neut, avg) {
        var tot = own+opp+neut;
        var cat = 0;
        if(opp > tot/2) {
            cat = 1;
        } else if(own > tot/2) {
            cat = 5;
        }
        return 1/(1+avg+cat);
    }
}
```

Answer 2

Grabież ziemi

Krótki opis strategii:

1. W pierwszej turze przeprowadź dużą kampanię w centrum, wykorzystując wszystkie początkowe pieniądze.
2. W przeciwnym razie, jeśli w regionie jest więcej niż 2 neutralnych wyborców, rozpocznij kampanię w regionie z największą liczbą neutralnych wyborców.
3. W przeciwnym razie, jeśli jest region, w którym ja i mój przeciwnik mamy taką samą liczbę wyborców, rozpocznij kampanię w tym regionie.
4. W przeciwnym razie kampania w regionie z najbardziej neutralnymi wyborcami.

Polega to na tym, że znacznie łatwiej jest ubiegać się o neutralnych wyborców niż wyborców, którzy będą głosować na Twojego przeciwnika. Nie wie o gerrymanderingu, więc może nie radzić sobie zbyt dobrze, jeśli ktoś miesza się z regionami głosowania, ale to początek.

(regions, money, result, storage) => {
   if(money == 100) { return campaign([2, 2], [12, 12]); }
   var best = regions[0];
   var tied;
   for (var i = 0; i < regions.length; i++) {
      if(regions[i].number_neutral > best.number_neutral) {
         best = regions[i];
      }
      if(regions[i].number_neutral == 0 && regions[i].number_you == regions[i].number_opponent) {
        tied = regions[i];
      }
   }
   var b;
   if (tied && best.number_neutral > 2) {
     b = tied.blocks[money % tied.blocks.length];
   } else {
     b = best.blocks[money % best.blocks.length];
   } 
   if (money >= 16) {
        return campaign(b, [b[0] + 4, b[1] + 4])
   } else if (money % 2 == 0) {
        return campaign(b, [b[0] + 3, b[1] + 3])
   } else {
        return campaign([b[0] + 1, b[1] + 1], [b[0] + 4, b[1] + 4])
   }
}

Answer 3

Polityka lewicowa

v1.1

Chwyta lewą stronę mapy, a następnie porusza się po prawej stronie. Uzyskując to, będzie powoli prowadzić kampanię po prawej stronie, aby uniknąć impasu.

(regions, money, result, storage) => {
        storage.phase = storage.phase || 0;
        storage.merge = storage.merge || 0;

        if (storage.phase == 0){
            storage.phase+=2;
            return campaign([1,2],[5,14]);
        }

        if (storage.phase <= 6) {
            var result = campaign([storage.phase,1],[storage.phase+1,15]);
            if(money >= 14) storage.phase++;
            return result;
            
        }


        if(storage.phase == 7){

            if(storage.merge < 4){
                var result; 
                if(money >= 25){ 
                    result = merge([9,(storage.merge*4)+1],[15,(storage.merge)*4+1])
                    storage.merge++;
                    storage.phase = 1
                }
                return result;
            }
            else if(regions.filter(r => r.blocks[0][0] <= 5)
                           .filter(r => r.number_you > r.number_opponent + r.number_neutral).length >= regions.length / 2){ 
                area = (storage.merge % 4)*4;
                if(money >= 18){
                    storage.merge++;
                    storage.phase = 1;
                    return campaign([9,area],[15,area+3]);
                }
            }
            else{
                
                storage.phase = 1;
                var result = campaign([storage.phase,1],[storage.phase+1,15]);
                if(money >= 14) storage.phase++;
                return result;
            }
        }
    }

Obecnie bije tylko przykładowego bota. Strategia jest po prostu zbyt powolna, aby dużo wygrać.

Answer 4

Randgrab

Rozpoczęto jako ewolucję Landgrab w celu zwiększenia losowości, a następnie powoli dodawano coraz więcej funkcji, aż obecnie pokonuje wszystkich innych zawodników (Landgrab, Leftist Policy 1.1 i Greedy Campaign 9).

Dodatki zawarte:

• Chwytanie mniej ziemi na początku, aby zaoszczędzić pieniądze
• Zajmowanie od razu sąsiednich terenów, jeśli mamy wystarczająco dużo pieniędzy
• Zmniejsz priorytyzację obszarów, w których mamy już wystarczającą przewagę, by wygrać, a przeciwnik jeszcze nie prowadził kampanii
• Priorytetyzuj obszary, w których głosowanie jest najbliższe („stany zmiany”, jeśli wolisz)
• Więcej losowości, w tym losowy wybór jednego z czterech rogów do przejęcia podczas wykonywania 3x3
• Dość chaotyczna (ale wciąż deterministyczna!) rZmienna, która kontroluje całą losowość

Słabe strony obejmują:

• Niewystarczające traktowanie priorytetów niezdecydowanych państw
• Brak korzystania z funkcji spoza kampanii
• Może zostać odrzucony przez zmiany regionu, chociaż zostało to częściowo poprawione
• Mogą zostać odrzucone przez roszczenia, które nie są dobrze dopasowane do granic

(regions, money, result, storage) => {
    if(money == 100) {return campaign([4, 4], [12, 12]);}
    var r = money + money * regions.length;
    regions.forEach(reg => r += reg.blocks[0][0] * reg.number_neutral + reg.blocks[0][1] * reg.number_you + money * reg.number_opponent + reg.blocks.length * reg.absolute_average);
    r = Math.floor(r);
    var tied = [];
    var best = [regions[r % regions.length]];
    var closest = [regions[(2*r) % regions.length]];
    for (var i = 0; i < regions.length; i++) {
        if(regions[i].number_neutral > best[0].number_neutral && !(regions[i].number_you > 8 && regions[i].number_opponent == 0)) {
            best = [regions[i]];
        } else if(regions[i].number_neutral == best[0].number_neutral && !(regions[i].number_you > 5 && regions[i].number_opponent == 0)) {
            best.push(regions[i]);
        }
        if(regions[i].number_neutral == 0 && regions[i].number_you == regions[i].number_opponent) {
            tied.push(regions[i]);
        }
        if(regions[i].number_opponent > regions[i].number_you && regions[i].absolute_average < closest[0].absolute_average) {
            closest = [regions[i]];
        } else if(regions[i].number_opponent > regions[i].number_you && regions[i].absolute_average == closest[0].absolute_average) {
            closest.push(regions[i]);
        }
    }
    var b;
    var choice;
    if (tied.length > 0 && best[0].number_neutral > 4) {
        choice = tied;
    } else {
        choice = (best[0].number_neutral > 2 ? best : closest);
    }
    console.log(choice);
    bt = choice[r % choice.length];
    b = bt.blocks[r % bt.blocks.length];
    var x = Math.floor(r/2) % 2;
    var y = Math.floor(r/4) % 2;
    if (money >= 18 && choice) {
        for(var i = 0; i < choice.length; i++) {
            for(var j = 0; j < choice[i].blocks.length; j++) {
                var c = choice[i].blocks[j];
                if(c[0] == b[0]-4 && c[1] == b[1]) {
                    return campaign([c[0]+1, c[1]], [b[0]+3, b[1]+3]);
                } else if(c[0] == b[0]+4 && c[1] == b[1]) {
                    return campaign([b[0]+1, b[1]], [c[0]+3, c[1]+3]);
                } else if(c[0] == b[0] && c[1] == b[1]-4) {
                    return campaign([c[0], c[1]+1], [b[0]+3, b[1]+3]);
                } else if(c[0] == b[0] && c[1] == b[1]+4) {
                    return campaign([b[0], b[1]+1], [c[0]+3, c[1]+3]);
                }
            }
        }
    }
    if (money >= 16) {
        return campaign(b, [b[0] + 4, b[1] + 4]);
    } else {
        return campaign([b[0] + x, b[1] + y], [b[0] + 3 + x, b[1] + 3 + y]);
    }
}

Answer 5

Chciwa kampania 9 na każdy region

• W każdej turze mamy co najmniej 10 $. Umożliwia to kampanię na obszarze 3x3.
• Ponieważ potrzebujemy tylko 9 pasów w każdym regionie. Po prostu prowadzimy kampanię na górze 3x3, ale rezygnujemy z tych po prawej lub u dołu.
• W każdej turze chciwi wybieramy pozycję kampanii: im bardziej region nas wesprze w następnej turze, tym lepiej.

(regions, money, result, storage) => {
  const turn = storage.turn = storage.turn + 1 || 1;
  const gh = money < 21 ? 1 : 2;
  const h = 4 * gh - 1;
  const gw = 77 <= money ? 3 : 49 <= money ? 2 : 1;
  const w = 4 * gw - 1;
  const candidate = [];
  for (let i = 0; i <= 4 - gw; i++) {
    for (let j = 0; j <= 4 - gh; j++) {
      let s = gw * gh;
      for (let k = 0; k < gw; k++) {
        for (let l = 0; l < gh; l++) {
          let bx = i + k, by = j + l;
          let region = regions.find(r => r.blocks.some(block => block == [bx * 4, by * 4] + ''));
          let { number_neutral: n, number_opponent: o, number_you: y } = region;
          if (y <= o) {
            if (n + y > o) s += 1;
            if (n + y == o) s += 0.5;
            if (n + y < o) s += 0.5 ** (o - y - n / 2);
          } else {
            if (n + o > y) s += 0.5;
            if (n + o < y) s += -(0.5 ** (y - o - n / 2));
            if (n + o == y) s += 0.25;
          }
        }
      }
      candidate.push({ s, x: i, y: j });
    }
  }
  const ts = Math.max(...candidate.map(c => c.s));
  const best = candidate.filter(c => c.s === ts);
  const { x: tx, y: ty } = best[turn % best.length];
  return campaign([tx * 4, ty * 4], [tx * 4 + w, ty * 4 + h]);
}

Answer 6

Liberal Agenda

Duchowy następca lewicowej polityki. Kampania cała lewa strona obraca się o jedną, potem gerrymanders razem oba górne prawe bloki, po czym wraca do ochrony lewej strony. Gdy jest już bardzo pewny, że ma zakrytą lewą stronę, przesuwa się w prawo.

    (regions, money, result, storage) => {
        storage.merge = (storage.merge||0)
        if(money >= 100){
            return campaign([1,1],[7,15])
        }
        else {
            var map = [];
            regions.forEach(reg => {
                reg.blocks.forEach(b => {
                    map.push({
                        "pos": b,
                        "abs_avg":reg.absolute_average,
                        "num_you":reg.number_you / reg.blocks.length,
                        "num_opp":reg.number_opponent / reg.blocks.length,
                        "num_neu":reg.number_neutral / reg.blocks.length,
                        "won": (reg.number_neutral>=reg.number_you+reg.number_opponent) ? 0 : reg.number_you/ reg.blocks.length - reg.number_opponent / reg.blocks.length
                    });
                });
            });
            map = map.sort((a,b)=>a.abs_avg-b.abs_avg).sort((a,b)=>a.won - b.won);
            var leftmap = map.filter(b=>b.pos[0]<8)
            if(money >= 25){
                if(storage.merge == 0){
                    storage.merge++
                    return merge([8,0],[12,0])
                }
                return campaign([leftmap[0].pos[0],leftmap[0].pos[1]],[leftmap[0].pos[0]+4,leftmap[0].pos[1] + 4])
            }
            
            if(leftmap.every(b=> b.abs_avg > 3)) return campTarget3by3(map[0].pos).filter(b=>b.won<1)
            return campTarget3by3(leftmap[0].pos)
        }

        function campTarget3by3(pos){
            var a1,a2,b1,b2
            if(pos[0]==0){
                a1 = 1
                b1 = 4
            }
            else {
                a1 = pos[0]
                b1 = pos[0] + 3
            }
            if(pos[1]==0){
                a2 = 1
                b2 = 4
            }
            else {
                a2 = pos[1]
                b2 = pos[1] + 3
            }

            return campaign([a1,a2],[b1,b2])
        }
    }

Jak na ironię, to jedyna rzecz, którą lewicowa polityka może pokonać!