Improve fairness of snake starting location

[Dkendal]

No description provided.

[cbinners]

Do we have opinions on how this should be done? I was thinking we have a few options:

1. Spawn with symmetry -- with 2 players, food and players spawn symmetrically across either the x or y axis, or in 4 quadrants, or something similar if the board is divisible in some meaningful way.

2. Spawn with n-manhatten distance away from any other snakes, and m-distance from a wall.

Obviously, option 1 has issues with odd number of snakes / food, but could be interesting for providing minimal variance, if that's a goal.

[joram]

I agree with concerns of option 1.

I think there are a couple points we want to address.

• spawning on edges/corners
• unfairly spawning near food

I enjoy the idea of spawning near secondary voroinoi vertices, where the primary are the food. That's overly complex though.

Other suggestion: pool of all vertices. Remove edge verts. Remove food adjacent verts. Then random pick from the remaining for a spawn point, remove it and it's adjacent. Repeat for each spawn point needed

[Dkendal]

@cbinners I agree with your points and I think that any solution would have to end being validated by that. @joram I like the idea of using Voroinoi vertices, I think that could work for finding vertices to place food at after placing all snakes. In either situation there is challenge of how you fairly place the snakes, even if you simplify the game by removing food.

In my mind, a solution for this got be verified by checking the following:

For a given game, define N snakes and M pieces of food. Each snake, and each piece of food is a point, which is a (int, in) tuple.

For each snake, map over the list of other snakes, and produce a a set that contains the distance (Manhattan or Euclidean) between this snake and the snake being iterated over. Repeat this mapping for each snake but with each piece of food.

The result is each snake will have a set of distances of to food, and distance to other snakes.

I think this is a reasonable formulation for fairness, what do you think?

One way to achieve this could be by seeding a graph with random locations for snakes and food, and then converting it to a force directed bipartite graph, where one set of points contains food points, and the other snakes.

The above graph is an example of this layout and it satisfies the previous validation. It however has the issue of not scaling out to fill the playing space and could be difficult to covert to a matrix quantification.

The prior mentioned Voroinoi diagram would satisfy this as well if the playing field is subdivided into N number polygons first, where N is the number of snakes, but it does have the disadvantage of loosing the ability to specify the number of food pellets, as that will be automatically calculated by the number of Voroinoi vertices.

If anyone wants to do exploration on this, see if there are any relevant white papers, or would like to attempt an implementation, please do!

[joram]

I will try and write a p.r. for this, although you may have feedback on it since I've never written elixir before. If anyone wants to write another one, we could compare, and have more options.

I was thinking with the voroinoi solution, we could define the food first, then using those vertices, the corners, and a fixed extra number evenly distributed along the edges, we could guarantee at least a minimum of secondary vertices (citation needed), if that's the case, there's a list of possible spawn points greater than the number of snakes, if that can be guaranteed, we can take the needed subset. My graph theory is rusty, so I will do a little research. I'll try and get an initial p.r. up by early next week.

[john-swu]

I am working on this still, just having trouble getting it running locally.

[exzizt]

On the topic of snakes and starting positions, is the fact that some snakes can never have a head-on collision an intended feature? Showing a picture describes it better than I can (...think of a chess/checkerboard--no matter what, these snakes can never have a head-on collision):

This is something I noticed in the 2017 engine as well.

[cbinners]

@exzizt we can mitigate this issue by restricting our starting positions to be a subset of the diagonals from an offset + 2n. Below, this would be all x positions.

x . x . x . x 
. x . x . x .
x . x . x . x
. x . x . x .
x . x . x . x

Some pseudocode (in javascript):

// Store the starting locations
const locations  = [];

// Generate an initial offset
const startOffset = Math.round(Math.random()); // Generate initial 0 or 1 offset

for (let y = 0; y < board.height; y++) {
    // Get the x-offset for the current row
    let offset = (startOffset + y) % 2;

    // Add the valid starting location at every other point
    for (let x = offset; x < board.width; x += 2) {
        locations.push([x, y]);
    }
}

// ... further reduce locations for fairness conditions, etc.

@Dkendal I haven't had time to look into the board generation here, but maybe @joram can integrate something like this (in elixir, of course) into your PR?

[joram]

I never thought about that issue.
could we not simplify it to

let is_valid = (x+y)%2;

?

[joram]

added it to my p.r.