19
\$\begingroup\$

It's election time, and your job is to beat your competitor in a head-on rivalry! You are both trying to win over a city of 256 people in a 16x16 grid. Right now, the city hasn't been divided into voting regions yet, but that's where your gerrymandering skills come in! You can also campaign in arbitrary areas of the city to gain support.

General

All bots (JS functions) will be run against all other bots once per game. In each game, the city will start out with all voters being neutral. The game will keep track of a number for each voter, determining who they support. From a particular bot's perspective, a positive number means that voter will vote for them, while a negative number is a vote for the opponent. Zero is neutral.

The city is divided into 16 blocks, which are all 4x4 squares. Voting regions are made up of one or more blocks. There are initially 16 of them, with each block having its own region.

Both bots start with $100, and can move once per turn. These moves are run effectively simultaneously, so there is no first turn advantage. Moves fall into four categories:

  • Campaigning: This will cause every person in a specific area to increase their support for the candidate who is campaigning. The amount it changes depends on their neighbors.
  • Polling: This will get each person's support for the candidate in a specific area.
  • Bribing: This will cause a particular person to increase their support for the candidate.
  • Region Merging/Unmerging: This will reshape voting regions.

At the end of each turn, after both candidates have moved, both will recieve $10.

Details

The following moves are allowed. If an invalid move is given (insufficient money or invalid coordinates), the bot's turn will be skipped.

All coordinates should be within 0 <= n < 16, and for the second pair in rectangular bounding areas 0 <= n <= 16 (as these are exclusive).

  • campaign([x, y], [x, y]): Campaign within the boundary determined by the two coordinate pairs
    • Costs $1 per person affected
    • Each person within the area will change their support according to the following rules:
      • For all neighbors orthogonally (including diagonals) adjacent, add 0.1 support for whichever candidate the majority support (weighted), or 0.2 if their total support is at least 2 for that candidate
      • Add 0.25 for the candidate who is campaigning
  • poll([x, y], [x, y]): Poll within the boundary determined by the two coordinate pairs
    • Costs $0.25 per person polled, rounded up
    • On the next turn, the following information is given about each person in the area (after the opponent's move):
      • Their support for the polling candidate, where positive numbers indicate a vote for them, and negative numbers being a vote for the opponent
  • bribe([x, y]): Bribe the person at the location determined by the coordinate pair
    • Costs at least $5
      • For every time a person within the voting block (not the voting region) has been bribed, add $1
    • Add up to 3.5 support for the bribing candidate
      • For every time a person within the voting block has been bribed, the support added is decreased by 0.15
      • Eventually, this can cause bribing someone in a voting block to reduce their support for the candidate
  • merge([x, y], [x, y]): Merge the voting regions determined by the two coordinate pairs
    • Costs $25 for every block in the newly formed region (one block is free)
    • Requires the regions which contain the two people specified to be touching
      • Note that the coordinates correspond to people, not blocks. To reference a block, just multiply its coordinates by 4
  • unmerge([x, y]): Unmerge the voting region determined by the coordinate pair
    • Costs $25 for every block in the region
    • Every block in the region becomes its own region

If both bots attempt a merge or unmerge on the same turn (even if they won't interfere), both turns will be skipped and neither will pay anything. Moves will be processed in the following order (the order of the rest don't matter):

  1. Bribes
  2. Support from neighbors in campaigning
  3. Support from candidates in campigning

Winning

At the end of each turn, after both candidates have moved, all regions will have their votes added. Each person will either vote for one candidate or be neutral, regardless of by how much (i.e., a score of +0.05 or +30 would be identical here). If the following conditons are met, an election will be held and the winner chosen:

  • All regions are made up of less than half neutral voters
  • The number of regions voting for each candidate are not tied

I/O

All bots should be submitted in the form of Javascript functions. The following information will be provided as arguments to the function:

  • An array of voting regions, represented as objects with the following properties:
    • blocks: An array of voting blocks, represented as the coordinates [x, y] of the top-left person (such as [4, 0] or [12, 12])
    • number_neutral: The number of people in the region who are neutral
    • number_you: The number of people in the region voting for the bot
    • number_opponent: The number of people in the region voting for the bot's opponent
    • absolute_average: The average absolute value of people's support for a candidate
      • Higher numbers indicate campaigning or bribing will typically be less effective
      • Exactly 0 would mean every person in the region is neutral
  • The amount of money the bot has
  • An object containing the results of the last move (empty unless it was a poll)
    • An array people will contain objects representing each person polled:
      • position: The person's coordinates, formatted as [x, y]
      • region: The numbered ID of the region the person is in (the region's index in the first argument)
      • support: A number indicating whether the person is neutral (0), voting for the bot (positive), or voting for the bot's opponent (negative)
    • An object amounts containing the following properties:
      • number_neutral: The number of people in the region who are neutral
      • number_you: The number of people in the region voting for the bot
      • number_opponent: The number of people in the region voting for the bot's opponent
      • absolute_average: The average absolute value of people's support for a candidate
  • An object that can be used for storage between turns (but not between rounds/games)

To move, the result one of the functions above should be returned. For example:

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

Rules

  • Bots should take a reasonable amount of time to run
  • Bots should play fairly, no manipulating the controller or other submissions in ways not allowed here
  • Every bot will be run against every other bot once, with the winner being the bot which wins most often
    • In the event of a tie, the earlier bot wins
  • Invalid return values or bots that error will assume no move for the turn
  • Bots must be deterministic

Challenge idea and original sandbox proposal by HyperNeutrino.

Controller: https://radvylf.github.io/political-simulator
Chatroom: Here
Due Date: Thursday, November 5th, 2020, UTC Noon (8:00 AM EST)

\$\endgroup\$
4
  • \$\begingroup\$ How big is a block and what shape is it? (Sorry if that's in the question already, I'm not great at reading more complex questions) \$\endgroup\$
    – user
    Oct 27, 2020 at 23:38
  • 2
    \$\begingroup\$ @user It's a 4x4 square \$\endgroup\$ Oct 28, 2020 at 1:57
  • \$\begingroup\$ "Right now, the city hasn't been divided into voting regions yet" -- Does this mean that the regions array is empty at the start? \$\endgroup\$
    – SunnyMoon
    Oct 28, 2020 at 10:31
  • 2
    \$\begingroup\$ @SunnyMoon No, each region is initially one block. Sorry for the lack of information about blocks/regions, I think I dropped a paragraph by mistake when I was copying over the sandbox post :p \$\endgroup\$ Oct 28, 2020 at 11:57

6 Answers 6

6
\$\begingroup\$

Landgrab

Brief description of strategy:

  1. On the first turn, do a large campaign in the center using up all the initial money.
  2. Otherwise, if there is a region with more than 2 neutral voters, campaign in the region with the most neutral voters.
  3. Otherwise, if there is a region in which me and my opponent have the same number of voters, campaign in that region.
  4. Otherwise, campaign in the region with the most neutral voters.

This relies on the fact that it's much easier to claim neutral voters than voters who are already going to vote for your opponent. It doesn't know about gerrymandering, so might not do very well if someone messes with voting regions, but it's a start.

(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])
   }
}
\$\endgroup\$
4
\$\begingroup\$

Leftist Policy

v1.1

Grabs the left side of the map, then gerrymanders the right side. Having accomplished that, it will slowly campaign the right side to avoid deadlock.

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

Currently only beats the example bot. The strategy is just too slow to win much.

\$\endgroup\$
1
  • \$\begingroup\$ This bot might do better in a game with a similar format, but with a fixed amount of turns instead of go until someone wins. \$\endgroup\$
    – aerik
    Oct 29, 2020 at 23:17
4
\$\begingroup\$

Randgrab

Started as an evolution of Landgrab to increase randomness, then slowly added more and more features until it currently beats all other contestants (Landgrab, Leftist Policy 1.1, and Greedy campaign 9).

Features include:

  • Grabbing less land at the start to save money
  • Grabbing adjacent areas at once if we have enough money
  • De-priortize areas where we already have enough lead to win and the opponent hasn't campaigned yet
  • Prioritize areas where the vote is closest (the "swing states," if you will)
  • More randomness, including choosing at random any one of the four corners to claim when doing a 3x3
  • A pretty chaotic (but still deterministic!) r variable which controls all randomness

Weaknesses include:

  • Not prioritizing undecided states highly enough
  • Not taking advantage of any non-campaign functions
  • Can be thrown off by region changes, although this has been partially corrected for
  • Can be thrown off by claims which don't align to borders well
(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]);
    }
}
\$\endgroup\$
3
\$\begingroup\$

Abotcus

Turns out you don't need so many fancy features to be just as good as or better than Randgrab! Abotcus grabs an area at the start, then afterwards applies a straightforward formula to weight each block and picks the block with the best weight. If it looks like there's some unnecessary stuff in there, it's because I expected to add a lot more fancy features... but I just didn't need to ¯\_(ツ)_/¯

(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);
    }
}
```
\$\endgroup\$
3
\$\begingroup\$

Greedy campaign 9 per each region

  • Each turn, we have at least $10. This make it possible to campaign a 3x3 area.
  • Since we only need 9 gird in each region. We just campaign top 3x3 but give up the ones on right or bottom.
  • Every turn, we choice campaign position greedy: The more region support us in next turn, The better.
(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]);
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice bot! Note that randomness is disallowed, though. Luckily, it doesn't seem to affect your bot much when the Math.floor(Math.random() * best.length) is replaced with 0 (or some other deterministic value). \$\endgroup\$ Oct 29, 2020 at 13:16
  • 1
    \$\begingroup\$ @RedwolfPrograms edited. random removed by using turn % best.length \$\endgroup\$
    – tsh
    Oct 30, 2020 at 1:11
2
\$\begingroup\$

Liberal Agenda

The spiritual successor of Leftist Policy. Campaigns the whole left side turn one, then gerrymanders both of the top right blocks together, then goes back to protecting the left side. Once it's extremely confident it has the left covered, it moves on to the right.

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

Ironically, it's the only thing Leftist Policy can beat!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.