KoTH : 정치 시뮬레이터

Question

선거 시간입니다. 당신의 임무는 정면 경쟁에서 경쟁자를이기는 것입니다! 두 사람 모두 16x16 그리드에서 256 명의 도시를이기려고합니다. 현재이 도시는 아직 투표 지역으로 나뉘 지 않았지만, 그곳에서 게리맨더링 기술이 등장합니다! 지원을 받기 위해 도시의 임의의 지역에서 캠페인을 할 수도 있습니다.

일반

모든 봇 (JS 기능)은 게임당 한 번씩 다른 모든 봇에 대해 실행됩니다. 각 게임에서 도시는 모든 유권자가 중립적으로 시작됩니다. 게임은 각 유권자의 숫자를 추적하여 그들이 누구를지지하는지 결정합니다. 특정 봇의 관점에서 양수는 유권자가 그들에게 투표한다는 것을 의미하고 음수는 상대방에게 투표한다는 것을 의미합니다. 0은 중립입니다.

도시는 모두 4x4 정사각형 인 16 개의 블록으로 나뉩니다. 투표 지역은 하나 이상의 블록으로 구성됩니다. 처음에는 16 개가 있으며 각 블록에는 자체 영역이 있습니다.

두 봇 모두 $ 100부터 시작하며 턴당 한 번 이동할 수 있습니다. 이러한 움직임은 동시에 효과적으로 실행되므로 선회 이점이 없습니다. 동작은 네 가지 범주로 나뉩니다.

• 캠페인 : 특정 지역의 모든 사람이 캠페인을 진행하는 후보에 대한 지원을 강화합니다. 변화량은 이웃에 따라 다릅니다.
• 투표 : 특정 분야의 후보자에 대한 각 개인의 지원을받습니다.
• 뇌물 : 특정 사람이 후보자에 대한 지원을 늘릴 수 있습니다.
• 지역 병합 / 병합 해제 : 투표 지역의 모양을 변경합니다.

각 차례가 끝날 때 두 후보가 모두 이동하면 둘 다 $ 10를 받게됩니다.

세부

다음 이동이 허용됩니다. 유효하지 않은 이동 (돈 부족 또는 유효하지 않은 좌표)이 주어지면 봇의 차례를 건너 뜁니다.

모든 좌표는 0 <= n < 16, 및 직사각형 경계 영역의 두 번째 쌍에 대해 있어야합니다 0 <= n <= 16( 배타적 이므로 ).

• campaign([x, y], [x, y]): 두 좌표 쌍에 의해 결정된 경계 내의 캠페인
  • 영향을받는 사람당 비용 $ 1
  • 지역 내의 각 사람은 다음 규칙에 따라 지원을 변경합니다.
    • 인접한 모든 이웃 (대각선 포함)에 대해 다수지지 (가중)가있는 후보에 대해 0.1지지를 추가하거나 해당 후보에 대해 총지지가 2 이상인 경우 0.2를 추가합니다.
    • 캠페인중인 후보에 0.25를 추가합니다.
• poll([x, y], [x, y]): 두 좌표 쌍에 의해 결정된 경계 내에서 폴링
  • 설문 조사에 참여한 사람당 $ 0.25, 반올림
  • 다음 턴에 해당 지역의 각 사람에 대한 다음 정보가 제공됩니다 (상대 이동 후).
    • 투표 후보에 대한지지, 양수는 투표를 나타내고 음수는 반대 투표를 나타냅니다.
• bribe([x, y]): 좌표 쌍에 의해 결정된 위치에서 사람에게 뇌물 제공
  • 최소 $ 5 비용
    • 투표 블록 (내 사람마다 들어 있지 투표 영역) 매수 된 $ 1을 추가
  • 뇌물 수수 후보에 대해 최대 3.5 개의 지원 추가
    • 투표 블록 내의 사람이 뇌물을받을 때마다 추가 지원은 0.15 감소합니다.
    • 결국, 이것은 투표 블록에있는 누군가에게 뇌물을 주어 후보자에 대한지지 를 감소시킬 수 있습니다.
• merge([x, y], [x, y]): 두 좌표 쌍에 의해 결정된 투표 영역 병합
  • 새로 형성된 지역의 모든 블록에 대해 $ 25 비용 (한 블록은 무료)
  • 접촉하도록 지정된 두 사람이 포함 된 영역이 필요합니다.
    • 좌표는 블록이 아니라 사람에 해당합니다. 블록을 참조하려면 해당 좌표에 4를 곱하면됩니다.
• unmerge([x, y]): 좌표 쌍으로 결정된 투표 영역 병합 해제
  • 지역의 모든 블록에 대해 $ 25 비용
  • 지역의 모든 블록은 자체 지역이됩니다.

두 봇이 같은 턴에 병합 또는 병합 해제를 시도하면 (방해하지 않더라도) 두 턴을 모두 건너 뛰고 둘 다 지불하지 않습니다. 이동은 다음 순서로 처리됩니다 (나머지 순서는 중요하지 않음).

1. 뇌물
2. 캠페인에 대한 이웃의 지원
3. 캠핑 후보자의 지원

승리

각 턴이 끝날 때 두 후보가 모두 이동 한 후 모든 지역의 투표가 추가됩니다. 각 사람은 한 명의 후보자에게 투표하거나 얼마나 많은지에 관계없이 중립적입니다 (예 : 여기서 +0.05 또는 +30의 점수는 동일합니다). 다음 조건이 충족되면 선거가 실시되고 우승자가 선택됩니다.

• 모든 지역은 절반 미만의 중립 유권자로 구성됩니다.
• 각 후보에 투표 한 지역 수는 동률이 아닙니다.

I / O

모든 봇은 자바 스크립트 함수의 형태로 제출되어야합니다. 함수에 대한 인수로 다음 정보가 제공됩니다.

• 다음 속성을 가진 객체로 표현되는 투표 지역의 배열 :
  • blocks: [x, y]왼쪽 상단 사람 의 좌표 로 표시되는 투표 블록 배열 (예 : [4, 0]또는 [12, 12])
  • number_neutral: 중립적 인 지역의 사람들의 수
  • number_you: 봇에 투표 한 지역의 사람 수
  • number_opponent: 봇의 상대에게 투표 한 지역의 사람 수
  • absolute_average: 후보자 지원의 평균 절대 값
    • 숫자가 높을수록 캠페인이나 뇌물이 일반적으로 덜 효과적임을 나타냅니다.
    • 정확히 0은 해당 지역의 모든 사람이 중립임을 의미합니다.
• 봇이 가지고있는 금액
• 마지막 이동의 결과를 포함하는 개체 (투표가 아닌 경우 비어 있음)
  • 배열 people에는 폴링 된 각 사람을 나타내는 개체가 포함됩니다.
    • position: 사람의 좌표, 형식은 [x, y]
    • region: 사람이있는 지역의 번호가 매겨진 ID (첫 번째 인수의 지역 색인)
    • support: 그 사람이 중립 (0)인지, 봇에게 투표했는지 (긍정적), 봇의 상대에게 투표했는지 (부정적)를 나타내는 숫자
  • amounts다음 속성을 포함 하는 개체 :
    • number_neutral: 중립적 인 지역의 사람들의 수
    • number_you: 봇에 투표 한 지역의 사람 수
    • number_opponent: 봇의 상대에게 투표 한 지역의 사람 수
    • absolute_average: 후보자 지원의 평균 절대 값
• 턴 사이 (라운드 / 게임 사이에는 아님) 보관에 사용할 수있는 개체

이동하려면 위의 함수 중 하나의 결과가 반환되어야합니다. 예를 들면 :

{
    "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]
        );
    }
}

규칙

• 봇은 실행하는 데 적절한 시간이 걸립니다.
• 봇은 공정하게 플레이해야하며 여기에서 허용되지 않는 방식으로 컨트롤러 또는 기타 제출물을 조작해서는 안됩니다.
• 모든 봇은 다른 모든 봇에 대해 한 번 실행되며, 가장 자주이기는 봇이 승자가됩니다.
  • 동점 인 경우 이전 봇이 승리합니다.
• 잘못된 반환 값 또는 오류가 턴 동안 이동이 없다고 가정하는 봇
• 봇은 결정적이어야합니다.

HyperNeutrino의 도전 아이디어와 독창적 인 샌드 박스 제안.

제어 장치: https://redwolfprograms.github.io/political-simulator
채팅방 : 여기
마감일 : 2020 년 11 월 5 일 목요일, UTC 정오 (오전 8시 EST)

Answer 1

Abotcus

Randgrab만큼 좋거나 더 나은 기능을하기 위해 많은 멋진 기능이 필요하지 않습니다! Abotcus는 처음에 영역을 잡은 다음 간단한 공식을 적용하여 각 블록에 가중치를 부여하고 가장 가중치가 높은 블록을 선택합니다. 불필요한 부분이있는 것 같으면 더 많은 멋진 기능을 추가 할 것으로 예상했기 때문입니다.하지만 그럴 필요는 없었습니다. ¯ \ _ (ツ) _ / ¯

(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

Landgrab

전략에 대한 간략한 설명 :

1. 첫 번째 턴에는 초기 돈을 모두 사용하여 중앙에서 대규모 캠페인을 수행하십시오.
2. 그렇지 않고 중립 투표자가 2 명 이상인 지역이있는 경우 가장 중립적 인 투표자가있는 지역에서 캠페인을 진행합니다.
3. 그렇지 않고 나와 내 상대가 같은 수의 유권자를 가진 지역이 있다면 그 지역에서 캠페인을 벌이십시오.
4. 그렇지 않으면 가장 중립적 인 유권자들이있는 지역에서 캠페인을 벌이십시오.

이것은 이미 상대방에게 투표하려는 유권자보다 중립 유권자를 주장하는 것이 훨씬 쉽다는 사실에 의존합니다. 게리맨더링에 대해 알지 못하기 때문에 누군가 투표 지역을 엉망으로 만들면 잘 안 될 수도 있지만 시작입니다.

(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

좌파 정책

v1.1

지도의 왼쪽을 잡은 다음 오른쪽을 게리 맨더합니다. 이를 달성하면 교착 상태를 피하기 위해 천천히 오른쪽으로 캠페인을 진행합니다.

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

현재는 예제 봇을 능가합니다. 전략이 너무 느려서 많이 이기지 못합니다.

Answer 4

Randgrab

무작위성을 높이기 위해 Landgrab의 진화로 시작된 다음 현재 다른 모든 참가자를 능가 할 때까지 점점 더 많은 기능을 추가했습니다 (Landgrab, Leftist Policy 1.1 및 Greedy 캠페인 9).

기능은 다음과 같습니다.

• 돈을 절약하기 위해 처음에 더 적은 토지 확보
• 돈이 충분하면 인접 지역을 한꺼번에 잡아
• 이미 승리 할 충분한 리드가 있고 상대가 아직 캠페인을 진행하지 않은 영역의 우선 순위를 제거합니다.
• 투표가 가장 가까운 지역의 우선 순위를 지정합니다 (원하는 경우 "스윙 상태").
• 3x3를 할 때 주장 할 네 모서리 중 하나를 무작위로 선택하는 것을 포함하여 더 많은 무작위성
• r모든 임의성을 제어 하는 꽤 혼란스러운 (그러나 여전히 결정적입니다!) 변수

약점은 다음과 같습니다.

• 미결정 상태의 우선 순위를 충분히 높게 지정하지 않음
• 캠페인 이외의 기능을 이용하지 않음
• 부분적으로 수정되었지만 지역 변경으로 인해 버릴 수 있습니다.
• 경계에 잘 맞지 않는 주장으로 인해 버릴 수 있음

(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

욕심쟁이 캠페인 지역별 9 개

• 매 턴마다 최소한 $ 10이 있습니다. 이를 통해 3x3 영역을 캠페인 할 수 있습니다.
• 각 지역에 9 조만 필요하기 때문에. 우리는 상위 3x3 캠페인을 실시하지만 오른쪽 또는 하단에있는 것은 포기합니다.
• 매 턴마다 우리는 욕심 많은 캠페인 위치를 선택합니다. 다음 차례에 더 많은 지역이 우리를 지원할수록 좋습니다.

(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

자유의 제

좌파 정책의 영적 후계자. 캠페인은 전체 왼쪽이 하나가 된 다음 오른쪽 상단 블록 모두를 함께 게리맨더링 한 다음 왼쪽을 보호하는 것으로 돌아갑니다. 왼쪽이 가려 졌다는 확신이 들면 오른쪽으로 이동합니다.

    (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])
        }
    }

아이러니하게도 좌파 정책이 이길 수있는 유일한 방법입니다!