text:
Chess Analysis with Limited Information
In this challenge, you are given a limited amount of information about a particular game of chess, and you need to predict who won the game.
You are given two sets of data:

Piece counts (What pieces are still alive)
Board colors (The color of pieces on the board)

More importantly, you don't know where the pieces are located. You need to determine who you think will win.
Games are selected from all events listed on PGNMentor from 2010 to now.  I've selected 10% of all of the board positions from each game that ends in a win or a loss.  Board positions will always be at least 30 moves into the game.  The test cases can be found here.  (White wins are listed first, followed by black wins)
Input
The piece count will be a string consisting of a character for each piece: king, queen, rook, knight, bishop, or pawn.  Lowercase means black, uppercase is white.  The board will be a string of 64 characters (8 rows by 8 columns). B represents a black piece, W represents a white piece, and . represents an empty spot.  Sample:
W..WB......W.BB....W..B..W.WWBBB..W...B....W..BBWWW...BB.W....B.,BBKPPPPPPPQRRbbkpppppppqrr

would represent the following board
...B.BB.
.BBBBBBB
.B.B....
B..W....
WWWW.W..
....W.W.
...W..WW
W.....W.

and where both colors have 2 Bishops, 1 King, 7 Pawns, 1 Queen, 2 Rooks
Output
You need to return a floating-point number between 0 and 1 (inclusive) to determine how likely it is that white wins.  Sample:
0.3     (30% chance that white wins)

More details:

Each test case is worth 1 point. Your score will be 1 - (1-Output)^2 if white wins, or 1 - (Output)^2 if black wins.
Your final score will be the sum across all test cases.
If I feel that submissions are hardcoding the input, I reserve the right to change the test cases.  (If I do change them, they will have the SHA-256 hash 893be4425529f40bb9a0a7632f7a268a087ea00b0eb68293d6c599c6c671cdee)
Your program must run test cases independently.  No saving information from one test case to the next.
If you are using machine learning, I highly recommend training on the first 80% of the data, and testing using the remaining 20%.  (Or whatever percentages you use). I use the games multiple times in the data, but I put the same games together sequentially.
UPDATE: I've added over a million test cases for testing and learning purposes.  They are split into black and white parts because of github repo size limits.

Good luck and have fun!

This conversation has been moved to chat.

Do the new test cases contain the old ones, or are the two sets disjoint?

I have no idea. I got them from different sites, so it is possible they both included the same set of games.

GNU sed + bc, 4336 5074.5 points, 64 75 %
Update: the OP gave a new way to calculate the score of the prediction for an individual test case. Using Wolfram Alpha, I plotted both sets of formulas to see the differences.
The current way brings a strong incentive to output actual probabilities, and not just the extremes, 0 and 1, for which the new formulas give the same maximum score as before. This is why the unchanged algorithm below, has now a better prediction rate, in fact a great rate given its simplicity.
However, there's also a drawback associated with the new formulas, as explained in 'Edit 1'.

This is a simple estimation based only on the material advantage / disadvantage, ignoring the actual placement of the pieces. I was curious how this will perform. The reason I use sed, and not some language that can do this in one line, is because it is my favorite esoteric language.
/:/d                                             # delete the two headers
s:.*,::                                          # delete board positions
s:$:;Q9,R5,B3,N3,P1,K0,q-9,r-5,b-3,n-3,p-1,k-0:  # add relative piece value table
:r                                               # begin replacement loop
s:([a-Z])((.*)\1([^,]+)):\4+\2:                  # table lookup: letter-value repl.
tr                                               # repeat till last piece
s:;.*::                                          # delete value table
s:.*:echo '&0'|bc:e                              # get material difference: bc call
/^0$/c0.5                                        # print potential draw score
/-/c0                                            # print potential black win score
c1                                               # print potential white win score

Standard piece values used:

9 - Queen
5 - Rook
3 - Knight
3 - Bishop
1 - Pawn
0 - King

I calculate the material for both sides and subtract black's material from that of white. The output for each test case is based on that difference as follows:

if difference > 0, then output = 1 (potential white win)
if difference = 0, then output = 0.5 (potential draw).

This is my only fractional output, hence the reason of the improvement as explained above.

if difference < 0, then output = 0 (potential black win)

The prediction rate for this method was 64 %. Now it is 75 % with the new formulas.

 I initially expected it to be higher, say 70 %, but as a chess player myself I can understand the result, since I've lost so many games when I was +1 / +2, and won that many when I was down in material. It's all about the actual position. (Well, now I got my wish!)

Edit 1: the drawback
The trivial solution is to output 0.5 for each test case, because this way you scored half a point regardless who won. For our test cases, this meant a total score of 3392.5 points (50 %).
But with the new formulas, 0.5 (which is an output you'd give if you're undecided who wins) is converted to 0.75 points. Remember that the maximum score you can receive for a test case is 1, for 100% confidence in the winner. As such, the new total score for a constant 0.5 output is 5088.75 points, or 75 %! In my opinion, the incentive is too strong for this case.
That score is better, though marginally, than my material advantage based algorithm. The reason for that is because the algorithm gives a probability of 1 or 0 (no incentive), assumed wins or losses, more times (3831) than it gives 0.5 (incentive), assumed draws (2954). The method is simple in the end, and as such it doesn't have a high percentage of correct answers. The boost from the new formula to constant 0.5, manages to reach that percentage, artificially.
Edit 2:
It is a known fact, mentioned in chess books, that it is usually better to have a bishop pair than a knight pair. This is especially true in the middle to end stage of the game, where the test cases are, since it's more likely to have an open position where a bishop's range is increased.
Therefore I did a second test, but this time I replaced the bishops's value from 3 to 3.5. The knight's value remained 3. This is a personal preference, so I didn't make it my default submission. The total score in this case was 4411 points (65 %). Only 1 percentage point increase was observed.
With the new formulas, the total score is 4835 points (71 %). Now the weighted bishop underperforms. But, the effect is explained because the weighted method now gives even more times assumed wins or losses (5089), than assumed draws (1696).

+1 for providing a reasonable baseline solution. I was also wondering how well this would perform.

@MartinEnder Thank you. My idea of increasing the bishop's value, mentioned last time, produced only a 1% success rate increase (see Update 2). I think the standard values did include that effect after all.

Hey, as per xnor's comment, would you mind if I change the scoring to be the squared absolute difference?

Awesome.  Also, thanks for answering!  I always worry that my tougher questions won't ever get an answer.

@NathanMerrill I updated my answer to use the new scoring as asked. Sorry for the long analysis, but I was indeed really curious.

This answer interestingly gives the optimal score if p (the probability that white wins) is assumed to be 0.5 (equal chance of winning) regardless of the pieces and boards.

Hey, I've added a ton more test cases if you are interested.

Java 8 + Weka, 6413 points, 94.5%
This answer uses a machine learning approach. You need to retrieve the Weka library, notably weka.jar and PackageManager.jar.
Here, I use a multilayer perceptron as classifier; you can replace mlp with any Classifier class of Weka to compare results.
I have not tinkered much with the parameters of the MLP, and simply eyeballed them (one hidden layer of 50 neurons, 100 epochs, 0.2 learning rate, 0.1 momentum).
I threshold the output value of the MLP, so the output really is either 1 or 0 as defined in the challenge. That way the number of correctly classified instances as printed by Weka is directly our score.
Feature vector construction
I turn each instance from a string to a vector of 76 elements, where:

The first 64 elements represent the cells of the board, in the same order as in the string, where 1 is a white piece, -1 is a black piece and 0 is an empty cell.
The last 12 elements represent each type of piece (6 per player); the value of those elements is the number of pieces of that type on the board (0 being "no piece of that type"). One could apply normalization to refit those values between -1 and 1 but this is probably not very helpful here.

Number of training instances
If I use all test cases given to train my classifier, I have managed to get 6694 (i.e. 98.6588%) correctly classified instances. This is obviously not surprising because testing a model on the same data you used to train it is way too easy (because in that case it is actually good that the model overfits).
Using a random subset of 80% of the instances as training data, we obtain the 6413 (i.e. 94.5173%) correctly classified instances figure reported in the header (of course since the subset is random you might get slightly different results). I am confident that the model would work decently well on new data, because testing on the remaining 20% of the instances (that weren't used for training) gives 77.0818% correct classification, which shows that the models generalizes decently well (assuming the instances we are given here are representative of the new test cases we would be given).
Using half the instances for training, and the other half for testing, we get 86.7502% on both training and testing data, and 74.4988% on only the test data.
Implementation
As I've said, this code requires weka.jar and PackageManager.jar from Weka.
One can control the percentage of data used in the training set with TRAIN_PERCENTAGE.
The parameters of the MLP can be changed just below TRAIN_PERCENTAGE. One can try other classifiers of Weka (e.g. SMO for SVMs) by simply replacing mlp with another classifier.
This program prints to sets of results, the first one being on the entire set (including the data used for training) which is the score as defined in this challenge, and the second one being on only the data that was not used for training.
One inputs the data by passing the path of the file containing it as an argument to the program.
import weka.classifiers.Classifier;
import weka.classifiers.Evaluation;
import weka.classifiers.functions.MultilayerPerceptron;
import weka.core.Attribute;
import weka.core.DenseInstance;
import weka.core.Instance;
import weka.core.Instances;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

public class Test {

    public static void main(String[] arg) {

        final double TRAIN_PERCENTAGE = 0.5;

        final String HIDDEN_LAYERS = "50";
        final int NB_EPOCHS = 100;
        final double LEARNING_RATE = 0.2;
        final double MOMENTUM = 0.1;

        Instances instances = parseInstances(arg[0]);
        instances.randomize(new java.util.Random(0));
        Instances trainingSet = new Instances(instances, 0, (int) Math.floor(instances.size() * TRAIN_PERCENTAGE));
        Instances testingSet = new Instances(instances, (int) Math.ceil(instances.size() * TRAIN_PERCENTAGE), (instances.size() - (int) Math.ceil(instances.size() * TRAIN_PERCENTAGE)));

        Classifier mlp = new MultilayerPerceptron();
        ((MultilayerPerceptron) mlp).setHiddenLayers(HIDDEN_LAYERS);
        ((MultilayerPerceptron) mlp).setTrainingTime(NB_EPOCHS);
        ((MultilayerPerceptron) mlp).setLearningRate(LEARNING_RATE);
        ((MultilayerPerceptron) mlp).setMomentum(MOMENTUM);

        try {
            // Training phase
            mlp.buildClassifier(trainingSet);
            // Test phase
            System.out.println("### CHALLENGE SCORE ###");
            Evaluation test = new Evaluation(trainingSet);
            test.evaluateModel(mlp, instances);
            System.out.println(test.toSummaryString());
            System.out.println();
            System.out.println("### TEST SET SCORE ###");
            Evaluation test2 = new Evaluation(trainingSet);
            test2.evaluateModel(mlp, testingSet);
            System.out.println(test2.toSummaryString());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static Instances parseInstances(String filePath) {
        ArrayList<Attribute> attrs = new ArrayList<>(); // Instances constructor only accepts ArrayList
        for(int i = 0 ; i < 76 ; i++) {
            attrs.add(new Attribute("a" + String.valueOf(i)));
        }
        attrs.add(new Attribute("winner", new ArrayList<String>(){{this.add("white");this.add("black");}}));
        Instances instances = new Instances("Rel", attrs, 10);
        instances.setClassIndex(76);

        try {
            BufferedReader r = new BufferedReader(new FileReader(filePath));
            String line;
            String winner = "white";
            while((line = r.readLine()) != null) {
                if(line.equals("White:")) {
                    winner = "white";
                } else if(line.equals("Black:")) {
                    winner = "black";
                } else {
                    Instance instance = new DenseInstance(77);
                    instance.setValue(attrs.get(76), winner);
                    String[] values = line.split(",");
                    for(int i = 0 ; i < values[0].length() ; i++) {
                        if(values[0].charAt(i) == 'B') {
                            instance.setValue(attrs.get(i), -1);
                        } else if(values[0].charAt(i) == 'W') {
                            instance.setValue(attrs.get(i), 1);
                        } else {
                            instance.setValue(attrs.get(i), 0);
                        }
                    }
                    // Ugly as hell
                    instance.setValue(attrs.get(64), values[1].length() - values[1].replace("k", "").length());
                    instance.setValue(attrs.get(65), values[1].length() - values[1].replace("q", "").length());
                    instance.setValue(attrs.get(66), values[1].length() - values[1].replace("r", "").length());
                    instance.setValue(attrs.get(67), values[1].length() - values[1].replace("n", "").length());
                    instance.setValue(attrs.get(68), values[1].length() - values[1].replace("b", "").length());
                    instance.setValue(attrs.get(69), values[1].length() - values[1].replace("p", "").length());
                    instance.setValue(attrs.get(70), values[1].length() - values[1].replace("K", "").length());
                    instance.setValue(attrs.get(71), values[1].length() - values[1].replace("Q", "").length());
                    instance.setValue(attrs.get(72), values[1].length() - values[1].replace("R", "").length());
                    instance.setValue(attrs.get(73), values[1].length() - values[1].replace("N", "").length());
                    instance.setValue(attrs.get(74), values[1].length() - values[1].replace("B", "").length());
                    instance.setValue(attrs.get(75), values[1].length() - values[1].replace("P", "").length());

                    instances.add(instance);
                }
            }
        } catch (Exception e) { // who cares
            e.printStackTrace();
        }
        return instances;
    }
}

How do you encode the input?

@NathanMerrill I'm not sure I understand your question

How are you passing the test case as input to the neural network?  Are you just passing in the raw string?

@NathanMerrill Edited with a paragraph on the feature vector construction.

How does weka know you are trying to predict the winner?

The 94.5% is the result on the training data? I don't think that number is meaningful as neural network also works as some kind of hard-coding mechanism if the parameter space is large enough. Note that if the probability that white wins is close to 0.5 (which is quite true if we are not given any information), the optimal expected score should be only slightly larger than 75%, which your result on test data seems to match quite well, but not the result on training data. The result by @user1502040 seems more reliable (on validation set) and realistic.

@justhalf This is exactly why (1) I did not use 100% of the set to train (2) have commented on OP's question to tell them that they should use a secret set of data to test all answers. I don't know how you can pull that 75% percent figure out of thin air. user1502040 uses 90% of all data for training instead of 80% as I do.

Sorry I didn't reference my claim earlier. The 75% figure is based on my comment in the question, responding to xnor call for confirmation on the optimal score. An optimal system that outputs the true probability will get a score of 75% if p=0.5 as can be seen in the plot I gave in the comment. If p!=0.5 (which is likely here) then the optimal score will be higher than 75%. And yes, the comparison is not fair with user1502040 since more data is used there.

Hey, I've added a ton more test cases if you are interested.

Python 3 - 84.6%, 5275 points on a validation set
If we cheat and use all the data, we can achieve an accuracy of 99.3%, and a score of 6408
Just a simple large MLP with dropout using Keras
import collections
import numpy as np
import random

import keras
from keras.models import Sequential
from keras.layers import Dense, Dropout
from keras.layers.noise import GaussianDropout
from keras.optimizers import Adam

np.random.seed(0)
random.seed(0)

def load_data():
    with open('test_cases.txt', 'r') as f:
        for line in f:
            yield line.split(',')

def parse_data(rows):
    black_pieces = "kpbkrq"
    white_pieces = black_pieces.upper()
    for i, row in enumerate(rows):
        if len(row) >= 2:
            board = row[0]
            board = np.array([1 if c == 'W' else -1 if c == 'B' else 0 for c in board], dtype=np.float32)
            pieces = row[1]
            counts = collections.Counter(pieces)
            white_counts = np.array([counts[c] for c in white_pieces], dtype=np.float32)
            black_counts = np.array([counts[c] for c in black_pieces], dtype=np.float32)
            yield (outcome, white_counts, black_counts, board)
        else:
            if 'White' in row[0]:
                outcome = 1
            else:
                outcome = 0

data = list(parse_data(load_data()))
random.shuffle(data)
data = list(zip(*data))
y = np.array(data[0])
x = list(zip(*data[1:]))
x = np.array([np.concatenate(xi) for xi in x])

i = len(y) // 10

x_test, x_train = x[:i], x[i:]
y_test, y_train = y[:i], y[i:]

model = Sequential()
model.add(Dense(512, activation='relu', input_shape=(76,)))
model.add(GaussianDropout(0.5))
model.add(Dense(512, activation='relu'))
model.add(GaussianDropout(0.5))
model.add(Dense(512, activation='relu'))
model.add(GaussianDropout(0.5))
model.add(Dense(1, activation='sigmoid'))

model.compile(loss='mean_squared_error', optimizer=Adam())

use_all_data = False

x_valid, y_valid = x_test, y_test

if use_all_data:
    x_train, y_train = x_test, y_test = x, y
    validation_data=None
else:
    validation_data=(x_test, y_test)

batch_size = 128

history = model.fit(x_train, y_train, batch_size=batch_size, epochs=50, verbose=1, validation_data=validation_data)

y_pred = model.predict_on_batch(x_test).flatten()
y_class = np.round(y_pred)
print("accuracy: ", np.sum(y_class == y_test) / len(y_test))

score = np.sum((y_pred - (1 - y_test)) ** 2) * (len(y) / len(y_test))
print("score: ", score)

How much data do you use for training to get the 84.6% figure?

I used a 90-10 split as shown in the code

Hey, I've added a ton more test cases if you are interested.

Python 3 - 94.3% accuracy, 6447 points on a validation set of 20% of the data
Uses 3 neural networks, a nearest neighbours regressor, a random forest, and gradient boosting. These predictions are combined with a random forest which also has access to the data.
import collections
import numpy as np
import numpy.ma as ma
import random

import keras
from keras.models import Sequential
from keras.layers import Dense, Dropout, BatchNormalization, Activation, Conv2D, Flatten
from keras.layers.noise import GaussianDropout
from keras.callbacks import EarlyStopping
from keras.optimizers import Adam
from sklearn.neighbors import KNeighborsRegressor
from sklearn.ensemble import RandomForestRegressor
from sklearn.ensemble import GradientBoostingRegressor
import tensorflow

tensorflow.set_random_seed(1)
np.random.seed(1)
random.seed(1)

def load_data():
    with open('test_cases.txt', 'r') as f:
        for line in f:
            yield line.split(',')

def parse_data(rows):
    black_pieces = "kqrnbp"
    white_pieces = black_pieces.upper()
    for i, row in enumerate(rows):
        if len(row) >= 2:
            board = row[0]
            board = np.array([1 if c == 'W' else -1 if c == 'B' else 0 for c in board], dtype=np.float32)
            pieces = row[1]
            counts = collections.Counter(pieces)
            white_counts = np.array([counts[c] for c in white_pieces], dtype=np.float32)
            black_counts = np.array([counts[c] for c in black_pieces], dtype=np.float32)
            yield (outcome, white_counts, black_counts, board)
        else:
            if 'White' in row[0]:
                outcome = 1
            else:
                outcome = 0

data = list(parse_data(load_data()))
random.shuffle(data)
data = list(zip(*data))
y = np.array(data[0])
x = list(zip(*data[1:]))
conv_x = []
for white_counts, black_counts, board in x:
    board = board.reshape((1, 8, 8))
    white_board = board > 0
    black_board = board < 0
    counts = [white_counts, black_counts]
    for i, c in enumerate(counts):
        n = c.shape[0]
        counts[i] = np.tile(c, 64).reshape(n, 8, 8)
    features = np.concatenate([white_board, black_board] + counts, axis=0)
    conv_x.append(features)
conv_x = np.array(conv_x)
x = np.array([np.concatenate(xi) for xi in x])
s = x.std(axis=0)
u = x.mean(axis=0)
nz = s != 0
x = x[:,nz]
u = u[nz]
s = s[nz]
x = (x - u) / s

i = 2 * len(y) // 10

x_test, x_train = x[:i], x[i:]
conv_x_test, conv_x_train = conv_x[:i], conv_x[i:]
y_test, y_train = y[:i], y[i:]

model = Sequential()

def conv(n, w=3, shape=None):
    if shape is None:
        model.add(Conv2D(n, w, padding="same"))
    else:
        model.add(Conv2D(n, w, padding="same", input_shape=shape))
    model.add(BatchNormalization())
    model.add(Activation('relu'))

conv(128, shape=conv_x[0].shape)
conv(128)
conv(128)
conv(128)
conv(128)
conv(128)
conv(128)
conv(128)
conv(128)
conv(128)
conv(2, w=1)
model.add(Flatten())
model.add(GaussianDropout(0.5))
model.add(Dense(256))
model.add(BatchNormalization())
model.add(Activation('relu'))
model.add(GaussianDropout(0.5))
model.add(Dense(1))
model.add(BatchNormalization())
model.add(Activation('sigmoid'))

model.compile(loss='mse', optimizer=Adam())

model5 = model

model = Sequential()
model.add(Dense(50, input_shape=(x.shape[1],)))
model.add(Activation('sigmoid'))
model.add(Dense(1))
model.add(Activation('sigmoid'))

model.compile(loss='mse', optimizer=Adam())

model0 = model

model = Sequential()
model.add(Dense(1024, input_shape=(x.shape[1],)))
model.add(BatchNormalization())
model.add(Activation('relu'))
model.add(GaussianDropout(0.5))
model.add(Dense(1024))
model.add(BatchNormalization())
model.add(Activation('relu'))
model.add(GaussianDropout(0.5))
model.add(Dense(1024))
model.add(BatchNormalization())
model.add(Activation('relu'))
model.add(GaussianDropout(0.5))
model.add(Dense(1))
model.add(Activation('sigmoid'))

model.compile(loss='mse', optimizer=Adam())

model4 = model

use_all_data = False

x_valid, y_valid = x_test, y_test

if use_all_data:
    x_train, y_train = x_test, y_test = x, y
    validation_data=None
else:
    validation_data=(x_test, y_test)

def subsample(x, y, p=0.9, keep_rest=False):
    m = np.random.binomial(1, p, size=len(y)).astype(np.bool)
    r = (x[m,:], y[m])
    if not keep_rest:
        return r
    m = ~m
    return r + (x[m,:], y[m])

epochs=100

x0, y0, x_valid, y_valid = subsample(conv_x_train, y_train, keep_rest=True)
model5.fit(x0, y0, epochs=epochs, verbose=1, validation_data=(x_valid, y_valid), callbacks=[EarlyStopping(patience=1)])

x0, y0, x_valid, y_valid = subsample(x_train, y_train, keep_rest=True)
model0.fit(x0, y0, epochs=epochs, verbose=1, validation_data=(x_valid, y_valid), callbacks=[EarlyStopping(patience=1)])

x0, y0, x_valid, y_valid = subsample(x_train, y_train, keep_rest=True)
model4.fit(x0, y0, epochs=epochs, verbose=1, validation_data=(x_valid, y_valid), callbacks=[EarlyStopping(patience=1)])

model1 = RandomForestRegressor(n_estimators=400, n_jobs=-1, verbose=1)
model1.fit(*subsample(x_train, y_train))

model2 = GradientBoostingRegressor(learning_rate=0.2, n_estimators=5000, verbose=1)
model2.fit(*subsample(x_train, y_train))

model3 = KNeighborsRegressor(n_neighbors=2, weights='distance', p=1)
model3.fit(*subsample(x_train, y_train))

models = (model0, model1, model2, model3, model4, model5)

model_names = [
    "shallow neural net",
    "random forest",
    "gradient boosting",
    "k-nearest neighbors",
    "deep neural net",
    "conv-net",
    "ensemble"
]

def combine(predictions):
    clip = lambda x: np.clip(x, 0, 1)
    return clip(np.array([y.flatten() for y in predictions]).T)

def augment(x, conv_x):
    p = combine([m.predict(x) for m in models[:-1]] + [models[-1].predict(conv_x)])
    return np.concatenate((x, p), axis=1)

model = RandomForestRegressor(n_estimators=200, n_jobs=-1, verbose=1)
model.fit(augment(x_train, conv_x_train), y_train)

def accuracy(prediction):
    class_prediction = np.where(prediction > 0.5, 1, 0)
    return np.sum(class_prediction == y_test) / len(y_test)

predictions = [m.predict(x_test).flatten() for m in models[:-1]] + [models[-1].predict(conv_x_test).flatten()]+ [model.predict(augment(x_test, conv_x_test))]

for s, p in zip(model_names, predictions):
    print(s + " accuracy: ", accuracy(p))

def evaluate(prediction):
    return np.sum(1 - (prediction - y_test) ** 2) * (len(y) / len(y_test))

for s, p in zip(model_names, predictions):
    print(s + " score: ", evaluate(p))

Hey, I've added a ton more test cases if you are interested.

Woah you went out on this.

Note the java answer here that "beats" yours appears to report % on the entire data set and only gets 77% on the data it didn't train with.

Python 3 - 4353.25/6785 points - 64%
So I worked on this mostly yesterday. My first post golfing, and I've only been using python a week or so now, so forgive me if not everything is optimized.
def GetWhiteWinPercent(a):
finalWhiteWinPercent=0
i=a.index(',')

#position
board=a[:i]
blackBoardScore=0
whiteBoardScore=0
for r in range(i):
    if board[r] == 'B': blackBoardScore += abs(7 - (r % 8))
    if board[r] == 'W': whiteBoardScore += r % 8
if   whiteBoardScore > blackBoardScore: finalWhiteWinPercent += .5
elif whiteBoardScore < blackBoardScore: finalWhiteWinPercent += .0
else: finalWhiteWinPercent+=.25

#pieces
pieces=a[i:]
s = {'q':-9,'r':-5,'n':-3,'b':-3,'p':-1,'Q':9,'R':5,'N':3,'B':3,'P':1}
pieceScore = sum([s.get(z) for z in pieces if s.get(z) != None])
if   pieceScore < 0: finalWhiteWinPercent += 0
elif pieceScore > 0: finalWhiteWinPercent += .5
else: finalWhiteWinPercent += .25

return finalWhiteWinPercent

I ended up along the same path as seshoumara's answer to begin with. But the large number of test cases that had even counts of pieces left me dissatisfied.
So I googled traits that dictate who is winning in chess (I don't play the game myself) and noticed board position, specifically center control, is big. That's where this bit comes in.
for r in range(i):
    if board[r] == 'B': blackBoardScore += abs(7 - (r % 8))
    if board[r] == 'W': whiteBoardScore += r % 8
if   whiteBoardScore > blackBoardScore: finalWhiteWinPercent += .5
elif whiteBoardScore < blackBoardScore: finalWhiteWinPercent += .0
else: finalWhiteWinPercent+=.25

Both of those halves combined are used to find the score (0.0, 0.25, 0.50, 0.75, 1.0)
Very interesting that this board position extra doesn't seem to increase the chance at all of guessing the winner.
If you drop the test cases into some files, here's the testing.
whiteWins=0
blackWins=0
totalWins=0
for line in open('testcases2.txt','r'):
    totalWins += 1
    blackWins += 1 - GetWhiteWinPercent(line)
for line in open('testcases.txt','r'):
    totalWins += 1
    whiteWins += GetWhiteWinPercent(line)

print(str(whiteWins+blackWins) +'/'+str(totalWins))

I know this isn't a golf challenge, but any tips or advice in that regard is appreciated!

My answer?  You mean seshoumara's answer?  Also, you don't need to golf this (unless you want to).  This isn't a [tag:code-golf] challenge.

You can save many bytes by only using one-character variable names. (Although it doesn't really matter because this isn't code-golf)

Woops! Editing that now. At work, this is what I get for skimming!

Please don't golf it. It's better to keep the code readable when it's not code-golf.

Control of the middle of the board does not mean occupying the middle of the board, but attacking the middle of the board.  If you wanted to add some complexity around that, it may improve your score.

Out of interest I tried assigning weights to each square to indicate how valuable it was for white or black, i.e. how well occupation of the square correlated with victory. For instance, a black piece on f1 often means black wins. To predict a board I just find the piece with the most valuable prediction, and use that as the result. It's only 58.7% accurate though.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Find the optimal pattern
Given a string s composed of lowercase letters, such as
aabaaababbbbaaba

and a positive integer n, such as 4, output a length-n string t such that when t is repeated to the length of s, they have as many chars in common as possible. For the given example, the optimal output would be aaba, because it has thirteen chars in common with the target string:
s: aabaaababbbbaaba
t: aabaaabaaabaaaba (aaba)
   ^^^^^^^^  ^ ^^^^

and no possible t has more. However, for aaaaaab, there are two possible outputs: aaaa and aaba, which each have 6 chars in common with the target string:
s: aaaaaab
t: aaaaaaaa (aaaa)
   ^^^^^^

s: aaaaaab
t: aabaaaba (aaba)
   ^^ ^^^^

Either aaaa or aaba can be outputted, or both if you'd like. Note that s is not ever repeated; the trailing a in both repeated values of t is simply ignored.
Test cases
Inputs -> Valid outputs
1 a -> a
1 aa -> a
2 aa -> aa
1 ab -> a b
2 ab -> ab
1 abb -> b
2 abb -> ab bb
2 ababa -> ab
2 abcba -> ab
2 aabbbbb -> bb  (ab is not a valid output here)
3 aababba -> aab abb
3 aababbaa -> aab
3 asdasfadf -> asf
3 asdasfadfsdf -> asf adf
2 abcdefghijklmnopqrstuvwxyzyx -> yx
2 supercalifragilisticexpialidocious -> ic ii
3 supercalifragilisticexpialidocious -> iri ili ioi
4 supercalifragilisticexpialidocious -> scii
5 supercalifragilisticexpialidocious -> iapic
2 eeeebaadbaecaebbbbbebbbbeecacebdccaecadbbbaceebedbbbddadebeddedbcedeaadcabdeccceccaeaadbbaecbbcbcbea -> bb be
10 bbbbacacbcedecdbbbdebdaedcecdabcebddbdcecebbeeaacdebdbebaebcecddadeeedbbdbbaeaaeebbedbeeaeedadeecbcd -> ebbbdbeece ebdbdbeece
20 aabbbaaabaaabaaaabbbbabbbbabbbabbbbbabbaaaababbbaababbbaababaaaabbaaabbaabbbabaaabbabbaaabbaaaaaaaba -> aabbbbaaabbabbbaabba

Rules

You may assume the input will only ever be a non-empty string of lowercase letters and a positive integer no greater than the length of the string.
You may take the inputs in any standard format and in either order.
You may output a single string, or more than one in the form of an array, separated by newlines or spaces, etc.
Your code must finish for each test-case in less than 1 minute on any fairly modern computer.
This is code-golf, so make your code as short as possible.

This challenge is Zgarb-quality. Nice work!

I'm assuming only trailing characters are ignored? So you aren't allowed to ignore leading characters like this: 2 abb -> ba where it's built up as (b)[ab]a: leading (b) is ignored, [ab] are matching.

@KevinCruijssen Right, the pattern must start repeating at the beginning.

Jelly, 11 bytes
sZµṢŒrUṀṪµ€

Try it online!
Wasn't expecting to beat Dennis on this one, so tried to FGITW it (after trying several possibilities; there's more than one way to make 11). I came in shorter, much to my surprise.
Takes the string then the count as command-line arguments. Outputs on stdout.
Explanation
sZµṢŒrUṀṪµ€
s            Split {the first input} into {the second input}-sized groups
 Z           Transpose
  µ      µ€  On each of the transposed groups:
   Ṣ           Sort it;
    Œr         Run-length encode it;
      U        Rearrange it to the form {count, letter};
       Ṁ       Take the largest element (i.e. largest count)
        Ṫ      Take the second element of the pair (i.e. just the letter)

This uses the insight that the letter in each position of the pattern must be the most common letter corresponding to that position. We can find the letters corresponding to a particular pattern via splitting into pattern-sized groups, and transposing. The main reason this solution is so long is that Jelly doesn't seem to have a short way to find the mode of a list (I made several attempts, but they're all at least six bytes long).
Jelly, 10 bytes, based on @Dennis' solution
⁸ċ$ÞṪ
sZÇ€

Try it online!
This is a combination of @Dennis' solution and my own; there was a five-byte mode in that solution, which I stole for this solution. (I already had solutions based on ⁸ċ, but couldn't get below six bytes with it; I hadn't thought of using Þ.)
Explanation
µ…µ€ and Ç€ (with the … on the previous line) are both three bytes long (the latter needs a newline), and equivalent. Normally I use the former, but the latter's more flexible, as it allows you to use ⁸ to mention the argument.
This makes it possible to sort (Þ) by the number of occurrences in ⁸ (⁸ċ), then take the last element (Ṫ), to find the mode in just five characters.

Nice job outgolfing Dennis with his own language! :P

Mathematica, 51 bytes
#&@@@Commonest/@(PadRight@Partition[#2,UpTo@#])&

Input and output are lists of characters.
Also based on the modes of the lines of the transpose. I believe they called the built-in for the mode of a list Commonest solely to spite code golfers.

At least it's a byte shorter than MostCommon...

Python 3, 99, 73 61 bytes
-12, thx to @Rod
lambda s,n:''.join(max(s,key=s[i::n].count)for i in range(n))

Same idea, but rewrote it to eliminate the import statement.
lambda s,n:''.join(max(s,key=lambda c:s[i::n].count(c))for i in range(n))

Original
from collections import*
lambda s,n:''.join(Counter(s[i::n]).most_common(1)[0][0]for i in range(n))

Explanation:
s[i::n]                  a slice of every nth character of s, starting at position i

Counter(s[i::n])         counts the characters in the slice
  .most_common()         returns a list of (character, count) pairs, sorted by decreasing count
    [0][0]               grabs the letter from the first pair (i.e., the most common letter
      for i in range(n)  repeat for all starting positions

''.join                  combines the most common letters into a single string

you can switch to python2.7 and drop the ''.join() to return a list of strings

@Rod Dropping ''.join(...) would make it return a generator, not sure if that's allowed output.

@L3viathan it need to be python2.7 to work, added to the other comment

Can you write some explanation of how this works?

Also you can replace key=lambda c:s[i::n].count(c) with key=s[i::n].count (probably)

@Rod A list of strings is only allowed in the question for if you return all possible solutions. That's what I took it to mean.

Python 2, 106
Now it's a different answer! I was thinking about one(almost)-liner from the beggining. Now even shorter, based on zip usage by @Rod.
Thanks to @L3viathan and @Rod for clarification about using lambdas as answer
Try it online
lambda S,N:max(combinations(S,N),key=lambda s:sum(x==y for x,y in zip(S,s*len(S))))
from itertools import*

Explanation:
combinations(S,N) creates all combinations length N from characters of S
max() have argument key which takes as input function to use to compare elements
lambda s:sum(x==y for x,y in zip(S,s*len(S))) passed as such function
This lambda counts number of matching characters in list of tuples, produces by zip(S,s*len(S))
s - one of combinations and it's multipled by len(S) which creates string that is guaranteed longer than S
zip creates tuples of characters of each string S and s*len(S) and ignores all characters that can't be matched (in case of one string longer than another)
So max chooses combination, that produce maximum sum

you don't need to use [] on list comprehension inside functions, also you are using 1 for ... if <cond> you can use directly <cond> for ... since it will be used on sum, python will take True as 1 and False as 0

@Rod Thank you! If I would sqeeze my answer more, it will transform into your answer, approach is same :D So I'm trying something different right now

Yep, just saying so you can use on your future answers :3

@Rod I'm still learning python and find that PPCG is a good place to learn tricks and little nuances. At least for python. Btw, I've just beat you :D

¯\(ツ)/¯

Switching to a lambda will save 7 bytes.

@L3viathan and it will not output anything. Would it be valid entry?

@DeadPossum He meant this (note the footer and the header) and yes, a function is a valid answer, if its a lambda you don't even need the f= (unless it's recursive)

@Rod Oh, that's great! Not intuitive, but I'll accept that :)

JavaScript (ES6), 104 101 94 bytes
(n,s)=>s.replace(/./g,(_,i)=>[...s].map((c,j,a)=>j%n-i||(a[c]=-~a[c])>m&&(m++,r=c),m=r=``)&&r)

Saved 3 bytes twice thanks to @Arnauld. 97-byte solution that works with all non-newline characters:
(n,s)=>s.replace(/./g,(_,i)=>[...s].map((c,j)=>j%n-i||(o[c]=-~o[c])>m&&(m++,r=c),m=r=``,o={})&&r)

The previous 104-byte solution works with newline characters too:
(n,s)=>[...Array(n)].map((_,i)=>[...s].map((c,j)=>j%n-i||(o[c]=-~o[c])>m&&(m++,r=c),m=0,o={})&&r).join``

Very nice. I golfed a solution for reference when adding test cases and came up at 122 bytes, looping through every char, saving the counts in an array of objects, then building the string from that array.

Rather than initializing o to a new object, could you just reuse the array passed to map by using its 3rd parameter?

@Arnauld Hmm, I guess that works because the question guarantees lowercase letters, so I won't confuse the array elements with the counts...

I think (n,s)=>s.replace(/./g,(_,i)=>i<n?[...s].map((c,j,a)=>j%n-i||(a[c]=-~a[c])>m&&(m++,r=c),m=0)&&r:'') should save 3 more bytes. (Or 4 bytes by using currying syntax.)

@Arnauld Not bad, but I shaved a further two bytes off. (And also fixed my byte counts; a trailing newline was throwing them off.)

... and another two bytes bite the dust.

... or perhaps I should say they byte the dust...

Jelly, 12 11 bytes
s@ZċþZMḢ$€ị

Try it online!
How it works
s@ZċþZMḢ$€ị  Main link. Arguments: n (integer), s (string)

s@           Split swapped; split s into chunks of length n.
  Z          Zip/transpose, grouping characters that correspond to repetitions.
   ċþ        Count table; for each slice in the previous result, and each character
             in s, count the occurrences of the character in the group.
             This groups by character.
     Z       Zip/transpose to group by slice.
        $€   Map the two-link chain to the left over the groups.
      M        Find all maximal indices.
       Ḣ       Head; pick the first.
          ị  Index into s to retrieve the corresponding characters.

Does Jelly have comments?

No, it does not.

Pyth, 11 bytes
meo/dNd.TcF

Takes input as s,n and outputs as a list of characters.
Explanation
meo/dNd.TcF
         cFQ   Split s into chunks of length n.
       .T      Transpose.
m o/dNd        Sort characters in each string by frequency.
 e             Take the most common.

Japt, 16 15 bytes
Saved 1 byte thanks to @obarakon
Ç=VëUZ)¬ñ!èZ o

14 bytes of code + 1 byte for the -P flag. Try it online!
Ungolfed and explanation
 Ç   =VëUZ)¬ ñ!èZ o
UoZ{Z=VëUZ)q ñ!èZ o}
                          Implicit: U = input number, V = input string
Uo                        Create the range [0...U).
  Z{               }      Map each item Z by this function:
      VëUZ                  Take every U'th char of V, starting at index Z.
    Z=    )                 Call the result Z.
           q                Split the result into chars.
             ñ!èZ           Sort each char X by the number of occurrences of X in Z.
                  o         Pop; grab the last item (the most common char).
                      -P  Join the results (array of most common chars) into a string.

I think you can replace gJ with o

@obarakon That's genius, thanks!

Python 2, 132 bytes
from itertools import*
p,k=input()
b=l=len(p)
for i in combinations(p,k):
 x=sum(x!=y for x,y in zip(p,i*l))
 if x<b:b,o=x,i
print o

Try it online!

05AB1E, 17 bytes
Iôð«øvy{.¡é®èÙJðÜ

Try it online!
Explanation
Iô                 # split 2nd input in chunks of 1st input size
  ð«               # append a space to each
    ø              # zip
     vy            # for each y in the zipped list
       {           # sort the string
        .¡         # group into chunks of consecutive equal elements
          é        # sort by length
           ®è      # pop the last element (the longest)
             Ù     # remove duplicate characters from the string
              J    # join the stack into one string
               ðÜ  # remove any trailing spaces

PHP, 245 Bytes
function p($c,$s,$r=""){global$a;if(($c-strlen($r)))foreach(str_split(count_chars($s,3))as$l)p($c,$s,$r.$l);else{for($v=str_pad("",$w=strlen($s),$r);$z<$w;)$t+=$v[$z]==$s[$z++];$a[$t][]=$r;}}p($argv[1],$argv[2]);ksort($a);echo join(" ",end($a));

Online Version
Breakdown
function p($c,$s,$r=""){
    global$a;
    if(($c-strlen($r)))  # make permutation
        foreach(str_split(count_chars($s,3))as$l)
            p($c,$s,$r.$l); #recursive
    else{
        for($v=str_pad("",$w=strlen($s),$r);$z<$w;)
        $t+=$v[$z]==$s[$z++]; #compare strings
        $a[$t][]=$r; # insert value in array
    }
}
p($argv[1],$argv[2]); #start function with the input parameter
ksort($a); # sort result array
echo join(" ",end($a)); #Output

Haskell, 84 bytes
import Data.Lists
f n=map(argmax=<<(length.).flip(filter.(==))).transpose.chunksOf n

Usage example:
f 10 "bbbbacacbcedecdbbbdebdaedcecdabcebddbdcecebbeeaacdebdbebaebcecddadeeedbbdbbaeaaeebbedbeeaeedadeecbcd"
"ebbbdbeece"

Split input string into chunks of length n, transpose and ffind for each sublist the most frequent element.

Röda, 68 bytes
f s,n{seq 0,n-1|{|i|sort s/"",key={|c|x=s[i::n]x~=c,"";[#x]}|head}_}

Try it online!
It's a function that prints the output without trailing newline.
This was inspired by this answer.

Husk, 9 bytes
►ȯΣz=¹¢Ṗ²

Try it online!
Zgarb-quality questions need a Zgarb language answer.
Explanation
►ȯΣz=¹¢Ṗ²
     ¹ Ṗ² length n powerset of string
►ȯ        max by:
      ¢   repeating each subsequence infinitely
   z=¹    and check equality with the input
  Σ       sum the results
          this will return the most optimal pattern.

Japt -P, 11 bytes
òV ÕËü ñÊ¬Ì

Try it
òV ÕËü ñÊ¬Ì     :Implcit input of string U & integer V
òV              :Partitions of U of length V
   Õ            :Transpose
    Ë           :Map
     ü          :  Group & sort
       ñ        :  Sort by
        Ê       :    Length
         ¬      :  Join
          Ì     :  Last character
                :Implicitly join & output

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Island Golf #1: Circumnavigation
This is the first in a series of Island Golf challenges. Next challenge
Given an island in ASCII-art, output an optimal path to circumnavigate it.
Input
Your input will be a rectangular grid consisting of two characters, representing land and water. In the examples below, land is # and water is ., but you may substitute any two distinct characters you wish.
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........

There will always be at least one land tile. The land tiles will all be contiguous (i.e. there's only one island). The water tiles will also be contiguous (i.e. there are no lakes). The outer border of the grid will all be water tiles. Land tiles will not be connected diagonally: i.e., you will never see something like
....
.#..
..#.
....

Output
Your code must output the same grid, with a shortest circumnavigation drawn on it. In the examples below, the circumnavigation path is drawn with o, but you may substitute any character as long as it is distinct from your land and water characters.
A circumnavigation is a simple closed curve, drawn entirely on water tiles, that fully encircles all land tiles on the grid. Diagonal connections are allowed. For instance, this is a circumnavigation of the above island (but not a shortest one):
.ooooo.....
o..##.oo...
o.#####.o..
o.#######o.
o#########o
ooo#######o
..o#####.#o
..oo####..o
....oooooo.

The length of a circumnavigation is computed as follows: For every pair of adjacent tiles on the path, if they are connected horizontally or vertically, add 1; if they are connected diagonally, add √2. The length of the above path is 22 + 7√2 (≈ 31.9).
A shortest circumnavigation is a circumnavigation with the shortest possible length. Your program should output any one path that satisfies this condition. For most islands, there will be multiple possible solutions. Here is one solution for the above island, with length 10 + 13√2 (≈ 28.4):
...oo......
..o##oo....
.o#####oo..
.o#######o.
o#########o
.o.#######o
..o#####.#o
...o####.o.
....ooooo..

Details
Your solution may be a full program or a function. Any of the default input and output methods are acceptable.
Your input and output may be a multiline string or a list of strings. If your language has a character type distinct from single-character strings, you may substitute "list of characters" for "string" in the previous sentence. If your language needs to input the height and/or width of the grid, you may do so. Your output may (optionally) have a single trailing newline. As mentioned above, you may use any three distinct characters in place of #.o (please specify in your submission which characters you're using).
Test cases
A. Islands with unique shortest circumnavigations:
...
.#.
...

.o.
o#o
.o.

......
.####.
......

.oooo.
o####o
.oooo.

......
......
..##..
...#..
......
......

......
..oo..
.o##o.
..o#o.
...o..
......

.......
.#####.
...#...
...#...
.#####.
.......

.ooooo.
o#####o
o..#..o
o..#..o
o#####o
.ooooo.

.......
...#...
...#...
.#####.
...#...
...#...
.......

...o...
..o#o..
.o.#.o.
o#####o
.o.#.o.
..o#o..
...o...

.......
.#####.
.##..#.
..#..#.
.......

.ooooo.
o#####o
o##..#o
.o#..#o
..oooo.

B. Example of an island with multiple possible solutions:
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........

Possible outputs:
....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##.o..
..ooo...

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##.o..
..ooo...

C. Large test case as a Gist

This is code-golf: the shortest code in each language wins.

The shortest circumnavigation for the 3rd test case is the 'loaf' pattern in Conway's Game of Life!

Mathematica (version 9), 165 bytes
The nice, short ConvexHullMesh function that Greg Martin used was only introduced in Mathematica version 10, so I thought I'd make an attempt without it, using my ancient Mathematica version 9. I managed to get it slightly shorter, though! It's a function that takes and returns a list of strings (with ., # and o as the symbols).
""<>#&/@("o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#/.{0->"."})&[Characters@#/.{"."->0,"#"->1}]&

Explanation:

First, Characters@# /. {"."->0, "#"->1} turns the input into a matrix of 0s and 1s.
"o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"# then uses Mathematica's powerful (but extremely byte-heavy…) image processing capabilities to first fill in the island's convex hull (which is the shape you'd get if you stretched a piece of string around it), and then take its boundary. We then multiply this matrix by the string "o" to get a matrix of 0s and "o"s (thanks to Mathematica's impressive adaptability about types), and add this to "#" times the matrix of the island.
Finally, ""<>#& /@ (... /. {0->"."}) turns this matrix of "o"s, "#"s and 0s into a matrix of "o"s, "#"s and "."s, and joins each row into a string.

When we test this on example B, we get the output
{"....oo..",
 "...o##o.",
 "..o####o",
 ".o###..o",
 "o#####o.",
 "o#####o.",
 ".o##oo..",
 "..oo...."}

[Edit, thanks to Greg Martin:] If we're allowed to use arrays of characters instead of lists of strings, we can trim this down to 144 bytes:
"o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#/.{0->"."}&[#/.{"."->0,"#"->1}]&

Nicely done! I never knew about MorphologicalComponents[#, Method->"ConvexHull"]  :)  You can save even more bytes by assuming that the input is already split into characters, and by returning a 2D array of characters as well.

@GregMartin, I didn't know about that use of MorphologicalComponents either until today!

@DLosc, The function is the whole thing, not just f. (Well, strictly speaking it's the stuff after the semicolon.) To call the function, type the entire thing into a Mathematica window, followed by [, your input, and ], so it should look something like f@m_:=m(1-m[[2,2]]) . . . #/.{"."->0,"#"->1}]&[{"...", ".#.", "..."}] (abridged for space).

@DLosc Well, that's because the code's broken. I think I've fixed it now, though! (I've got no idea what happened there; sorry…)

(But go upvote Notatree's solution, it's better!)
Mathematica, 168 bytes
(x_~n~y_:=Min[Norm[x-#]&/@y];i=#;p=i~Position~#&;t=p["#"|"."]~Select~#&;(i~Part~##="o")&@@@t[#~n~t[ConvexHullMesh[Join[s=p@"#",#+{.1,.1}&/@s]]~RegionMember~#&]==1&];i)&

Pure function taking a 2D array of characters as input and returning a 2D array of characters. An easier-to-read version:
1  (x_~n~y_ := Min[Norm[x - #] & /@ y];
2  i = #; p = i~Position~# &;
3  t = p["#" | "."]~Select~# &;
4  (i~Part~## = "o") & @@@
5    t[#~n~
6      t[ConvexHullMesh[
7        Join[s = p@"#", # + {.1, .1} & /@ s]]
8      ~RegionMember~# &] == 1 &];
9  i) &

Line 1 defines a function n that produces the (smallest) distance between a point x in the plane and a set y of other points. Line 2 initializes the variable i to the input, both to resolve a currying ambiguity later and to be able to modify it to produce the eventual output; line 2 also defines a function p that returns the coordinates of all occurrences of its input in i.
On line 3, p["#" | "."] represents every single coordinate from the input map (since all its characters are either "#" or "."), so t is a function that selects only those coordinates that satisfy a yet-unspecified property. On line 4, i~Part~## = "o" is going to change a bunch of entries of i to the character "o"; those characters will be selected from the set of possible coordinates according to the stuff on lines 5-8. And line 9 just returns the answer once it's computed.
Okay, infrastructure done, now to the actual computation. ConvexHullMesh is Mathematica's built-in for computing the convex hull of a set of points (the smallest convex polygon containing those points). Morally speaking, this should "fill in" the coves and fjords of the island (which is s = p@"#"), to rule them out of our cicrumnavigation. There's a little problem with ConvexHullMesh when that set of points is all in a line (thank you, test case #2), which we resolve by appending a slightly offset version of s to itself in line 7. This output is a polygon, so lines 7-9 (t[...~RegionMember~# &]) produces a list of the points with integer coordinates in that polygon. Finally, line 5 and the end of line 9 calculate all points that are at a distance exactly 1 (hence not 0) from this set of integer points; that set becomes the circumnavigating path.
Below is the output for the large test case at the OP's link. Notice at the upper left, the unusual choices of when to go west versus southwest hint at the fact that it's shadowing an invisible line of slope -2/3 between two peninsulas (said line segment being part of the convex hull's boundary).
........................
.............o..........
...........oo#ooooooo...
..........o#.#.##...#o..
........oo.#.#.###.##o..
.......o..########.##o..
.....oo...############o.
...oo#....############o.
..o#.###.##############o
.o##.##################o
.o####################o.
.o.##################.o.
.o##################..o.
.o..################..o.
o###################..o.
o#####################o.
o.##################.o..
o####################o..
o#...##############.o...
o##...#############o....
o#.....###....#oooo.....
.oooooo#ooooooo.........
.......o................

Does Mathematica usually represent strings as 1D arrays of characters? If not, then you'll need to take/return a 1D array of strings instead. (Also, looking forward to the explanation! I don't think I'll be able to run this without having Mathematica, right?)

Mathematica has a string data type, but it seems that an array of characters is also valid for the purposes of this site (i.e., I learned this when I started on PPCG, but I forget the legalities of why). Yes, unfortunately, Mathematica is non-free and thus not accessible to many people :(

@GregMartin I always try out Mathematica solutions at sandbox.open.wolframcloud.com

Current consensus says that lists of single-character strings can't be used in place of a string. As far as I can tell, the "characters" in Mathematica are just single-character strings, like in Python. The situation is different in a language like Java, which has a separate char type; in that case, a char array could be used in place of a string.

I certainly want to abide by whatever current consensus is. However, it's not clear to me that that linked answer is definitive evidence. The answer with the most votes seems to indicate that lists of single-character strings is ok. Certainly the posted answers all overlap in what seems to be a non-obvious way.

Here's how I read it: The main upvoted answer was posted in 2014. The answer I linked was posted in 2016, as an attempt to clarify the ambiguity in the earlier answer. So I read the negative score on the newer answer as people saying, "No, we don't want the older answer to mean that lists of single-char strings are okay." But regardless of meta, I'm disallowing lists of single-char strings in this question (and I clarified the wording to reflect that).

Python 3, 779 bytes (indenting with tabs)
This is the whole program. It reads input from stdin and prints it to stdout. Stdin must end with EOF.
Example run with the big input: https://ideone.com/XIfYY0
import itertools,sys
L=list
C=itertools.count
d=L(map(L,filter(None,sys.stdin.read().split('\n'))))
X=len(d[0])
Y=len(d)
R=range
def P(r):return all(d[y][x]=='.'for x,y in r)
def S(f):
    for n in C(0):
        if P(f(n)):l=n
        else:break
    for n in C(l+1):
        if P(f(n)):return l,n
def f(V,a,*b):return L(eval('lambda '+a+':('+i+')',V)for i in b)
V=locals()
def D(n):
    y=min(n,Y-1);x=n-y
    while y>=0and x<X:yield(x,y);x+=1;y-=1
def E(n):
    x=max(0,n-Y);y=x+Y-n
    while y<Y and x<X:yield(x,y);x+=1;y+=1
F=f(V,'p','(p,y)for y in R(0,Y)','(x,p)for x in R(0,X)')+[D,E]
r=f(V,'x,y','x','y','x+y','x-y+Y')
B=L(map(S,F))
for x in R(0,X):
    for y in R(0,Y):
        z=L(zip(r,B))
        if all(g(x,y)in R(a,b+1)for g,(a,b)in z)and any(g(x,y)in e for g,e in z):d[y][x]='o'
print('\n'.join(''.join(x)for x in d))

The idea is simple: it computes smallest octagonal bounds, and draws cells which are inside all of the computed bounds and intersect at least one of the edges.

You don't really need to use sys.stdin as input. input(), getting multiline would do the job and cost less bytes

May be able to replace R(0,x) with R(x)

+1 for not using a built-in.

Nice! Some more golfing tips: save 5 bytes each by using lambdas to define P and f; L(generator expression) => [generator expression]; F, r, and B appear to be used only once apiece and thus can be inlined.

JavaScript (ES6), 369 343 bytes
f=s=>(a=s.split`
`.map(s=>[...s]),m=Array(8),a.map((b,i)=>b.map((c,j)=>c>'#'||[i-j,i,j+i,j,j-i,-i,-i-j,-j].map((d,k)=>d>m[k]||(m[k]=d-1)))),[o,p,q,r,t,u,v,w]=m,g=(i,j,k,l,...p)=>i-k|j-l?a[i][j]=g(i+(k>i)-(k<i),j+(l>j)-(l<j),k,l,...p):1/p[0]?g(k,l,...p):'o',g(p,p-o,p,q-p,q-r,r,r-t,r,-u,t-u,-u,u-v,w-v,-w,o-w,-w,p,p-o),a.map(b=>b.join``).join`
`)

Explanation: The string is split into a character array (I'm unclear as to whether character array input is acceptable). The array is then iterated over and the positions of all the land squares are located. The bounding lines given by the equations x - y = o, x = p, x + y = q, y = r, y - x = t, -x = u, -x - y = v, -y = w are determined such that the maximum possible parameter is chosen where all the land lies beyond the line. This has the effect of enclosing the island in an octagon. The coordinates of the corners of the octagon are readily calculated from the parameters and the cells on its edge are filled in. The array is then joined back into a string. The reason an octagon suffices is as follows:
   /o#     /o#     /o#
 |/o #   |/o #   |/ o#
 *o###   * o #   *  o#
/|o #   /|o #   /| o#
 |o#     |o#     |o#

Consider a corner of the octagon. At some point along the two edges the path will be limited by the land because we constructed the octagon to touch the land as closely as possible. If there is no land at the corner itself, the path could take the alternate routes as shown on the right, but that is still the same number of orthogonal and diagonal steps, so the distance is unchanged.

What does ´...p´ do?

@RobertFraser The technical name is array destructuring. In this case however, it just acts as a rest of arguments parameter.

@Neil Actually, the technical name is rest parameter. The same syntax is used for the spread operator. (You use both as ...p in different places.) Destructuring is something else (though the spread operator can be used in destructuring).

@BrianMcCutchon You're right, I meant spread operator, but destructuring works in argument lists anyway.

Python 3.5, 224, 263, 234 218 bytes
Golfed off another 16 bytes by getting rid of the nested function and making it a one-liner.
def h(s,k=0,i=0):w=s.find('\n')+1;x=s.find('X')-w;k=k or x;d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2;u=s[:k]+'o'+s[k+1:];return['X'>s[k]and i<8and(h(u,k+d[i+2],i+2)or h(u,k+d[i+1],i+1)or h(u,k+d[i],i))or'',s][s[k]>'X'and k==x]

Golfed off 29 bytes:
def f(s):
 w=s.find('\n')+1;x=s.find('X')-w;d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2
 def h(s,k,i):u=s[:k]+'o'+s[k+1:];return['X'>s[k]and i<8and(h(u,k+d[i+2],i+2)or h(u,k+d[i+1],i+1)or h(u,k+d[i],i))or'',s][s[k]>'X'and k==x]
 return h(s,x,0)

Input is a single string using '~' for ocean, 'X' for land, and 'o' for the boundary. (Using 'X' saves a byte for '>' instead of '==')
Less golfed version with comments:
def f(s):
    w=s.find('\n')+1                         # width of one row
    x=s.find('X')-w                          # starting point
    d=[1,w+1,w,w-1,-1,-w-1,-w,-w+1]*2        # delta to add to current index to move in
                                             # the 8 directions: E, SE, S, SW, W, NW,
                                             # N, NE. Make it long to avoid
                                             # lots of modulo operations in
                                             #    the recursive calls

    def h(s,k,i):                            # s is the island string, k the current
                                             # position, i the direction index
        if s[k]>'X'and k==x:                 # if back at the begining,
            return s                         #   return the map

        elif 'X'>s[k] and i<8:               # if there is water here, and haven't
                                             #  looped around,
            u=s[:k]+'o'+s[k+1:]              #  make a new map with an 'o' in the
                                             #  current spot

            r = h(u,k+d[i+2],i+2)            # try a 90 degree right turn
            if r: return r

            r = h(u,k+d[i+1],i+1)            # try a 45 degree turn
            if r: return r

            r= h(u,k+d[i],i)                 # try straight ahead
            if r: return r

        return ''                            # this path failed

    return h(s,x,0)

@DLosc fixed. (should I delete the old answer?)

Nice! (Yes, you should remove the old answer--if anyone wants to see it, they can look at the post's revision history.)

C# 7 - 414 369 327 bytes
Edit: switched to 1D looping, computing i and j on the fly
Edit: changed input method, collapsed lookup table, and switched to well defined initial bounds ...and removed the pointless space in the last outer for-loop
using C=System.Console;class P{static void Main(){var D=C.In.ReadToEnd().Replace("\r","");int W=D.IndexOf('\n')+1,H=D.Length,z=H,k,q,c;int P()=>z%W*(k%3-1)+z/W*(k/3-1)+H;var B=new int[9];for(;z-->0;)for(k=9;k-->0&D[z]%7<1;)if(B[k]<=P())B[k]=P()+1;for(;++z<H;C.Write(q>9?'o':D[z]))for(q=k=9;k-->0;)q*=(c=P()-B[k])>0?0:c<0?1:2;}}

Try It Online
Complete program, takes input to standard in, prints it to standard out, uses #, ., and o. For each cell, it computes a 'profile' (which is the distance over 8 directions (it appears to compute a ninth for convenience, but this is always 0), and records a maximum of each of these. It then writes out the whole map again, and replaces any cell which is both on a boundary and not outside any with a 'o'. The commented code below explains how it all works.
As per my answer to Save the Geese from Extinction, this produces the smallest octagon (valid circumnavigation with largest area) which bounds the island.
Note: that for once in my life I'm using something from the current decade, and this code requires C# 7 to compile. If you do not have C# 7, there is one line that will need to be replaced, which is clearly marked in the code.
Example usage and output:
type t7.txt | IslandGolf1.exe

.........ooooooooooo....
........o....#......o...
.......o...#.#.##...#o..
......o....#.#.###.##.o.
.....o....########.##..o
....o.....############.o
...o.#....############.o
..o#.###.##############o
.o##.##################o
o.####################.o
o..##################..o
o.##################...o
o...################...o
o###################...o
o#####################.o
o.##################..o.
o####################o..
o#...##############.o...
o##...#############o....
o#.....###....#...o.....
.o.....#.........o......
..ooooooooooooooo.......

Formatted and commented code:
using C=System.Console;

class P
{
    static void Main()
    {
        // \n 10
        // # 35
        // . 46
        // o 111

        var D=C.In.ReadToEnd().Replace("\r",""); // map

        int W=D.IndexOf('\n')+1, // width
            H=D.Length, // length
            z=H, // position in map (decomposed into i and j by and for P)
            k, // bound index
            q, // bound distance, and later cell condition (0 -> outside, 8 -> inside, >8 -> on boudary)
            c; // (free), comparison store

        // 'indexes' into a profile for the point z at index k
        // effectively {i=z%W,j=z/W,-i,-j,i+j,j-i,-i-j,i-j,0}[k] (inside order is a bit different) (0 const is always treated as 'inside bounds')
        // each non-zero-const entry describes the distance in one of the 8 directions: we want to maximise these to find the 'outer bounds'
        // the non-zero-const bounds describe 8 lines, together an octogen
        int P()=>z%W*(k%3-1)+z/W*(k/3-1)+H; // new C#7 local method syntax (if you don't have C#7, you can test this code with the line below instead)
        //k=0;System.Func<int>P=()=>z%W*(k%3-1)+z/W*(k/3-1)+H; // old lambda syntax (must pre-assign k to make static checker happy)

        var B=new int[9]; // our current bounds, each is initially null (must only call P() when on a #)
        // B[k] starts off a 0, P() has a +H term, and W+(H/W)<H for W >= 3, so B[k] is assigned the first time we compare it (H-i-j always > 0)

        for(;z-->0;) // for each cell
            for(k=9;k-->0& // for each bound
                D[z]%7<1;) // if this cell is #
                if(B[k]<=P())B[k]=P()+1; // update bound if necessary (add one so that we define the bound _outside_ the hashes)
        // z=-1
        for(;++z<H; // for each cell
                C.Write(q>9?'o':D[z])) // print the cell (if q > 9, then we are on the bounds, otherwise, spit out whatever we were before)
            // check we are not 'outside' any of the bounds, and that we are 'on' atleast one of them
            for(q=k=9;k-->0;) // for each bound
                q*=(c=P()-B[k])>0?0: // outside bound (q=0)    (??0 is cheaper than (int) or .Value)
                    c<0?1: // inside (preserve q)
                    2; // on bound (if q != 0, then q becomes > 9)
    }
}

largest octagon? or smallest?

@SargeBorsch thanks, fixed the text.


text:
Not so good roads in Rnccia
Here in the absolutely made up country Rnccia we have a lot of good stuff, but the roads aren't good. There are lots of holes and only half of them get fixed. Even then, only half of the fixes are well done. Your task is to embrace the bad roads of this country and draw them for me.
Input
You receive two positive integers as input. One represents the length of the road, and the second represents the number of lanes in each direction. The length of the road is guaranteed to be an even number.
Output
Output or return an ASCII-art image of the road with as many holes as will fit. Read the next two sections to see how the road and holes should be generated.
Road layout

Every road has a straight line of minuses(-) above and below it.
Every road has the same number of lanes in both directions.
Every road has a line of equal signs(=) down the middle.
Lanes have dashed lines between them (excep the special middle line from rule #3). One minus, one whitespace and so on. Starting with the minus.

Examples of roads:
Road with one lane in both sides:

--------------

==============

--------------

Road with two lanes in both sides:

--------------

- - - - - - -

==============

- - - - - - -

--------------

Hole layout

Every road has 7n total holes. n is the ceiling of the number of holes that will fit on the road divided by seven.
Every road has 4n unfixed holes. An unfixed hole is represented as double O (OO).
Every road has 2n holes that are fixed and represented as double # (##).
Every road also has n holes that are fixed well and represented as double H (HH).
Holes (in any state) appear on every lane in diagonal pattern, starting at the top right and moving down-across. A new line of holes should start in every 4th lane and every 8 characters in the top lane. See the examples for clarification.
The order of holes is irrelevant.
If 7n holes can't fit in road of given length, you may use #6 to choose which of the holes will not be visible.

In this example we have 14 holes, 4 of which are fixed poorly, and 2 which are fixed well:
------------------
OO      HH      OO
- - - - - - - - -
  ##      OO
- - - - - - - - -
    ##      OO
==================
      OO      OO
- - - - - - - - -
OO      ##      HH
- - - - - - - - -
  ##      OO
------------------

In this example we hava 9 holes, which is not multiple of 7. So your pool of holes to use is size 14 with 8 (OO), 4(##), 2(HH). You may use any holes from it to fill road.
------------------
OO  OO  OO  OO  OO
==================
  OO  OO  OO  ##
------------------

Another corner example. Road can have only 3 holes. So pool is 7: 4(OO), 2(##), 1(HH). Again, any can be used:
------
##
- - -
  ##
======
    HH
- - -

------

Other rules

You may change the appearance of holes to two of any other character, except -, = and whitespace. Just mention it in your answer.
It's code-golf, so make your code as compact as possible.

I think you probably want to do something like this: 1) calculate how many holes will fit on the road in that pattern. 2) make roughly half of these fixed holes. 3) make roughly half of the fixed holes fixed well.

I've added couple more examples to clarify approximate ratio

Is there some reason for using the 4:2:1 ratio instead of 4:2:2? The latter can be simplified to 2:1:1 and is simpler by all measures.

@ETHproductions No big reason, powers of 2 seems more appealing to me

starting at the top right in the description, but at the top left in the examples.

JavaScript (ES6), 158 bytes

f=
(w,l)=>[...Array(l*4+1)].map((_,i)=>[...Array(w)].map((_,j)=>i%2?(i>>1)-j&3?`  `:s[n%7]+s[n++%7]:i/2%l?`- `:i-l-l?`--`:`==`).join``,n=0,s=`O#OHO#O`).join`\n`

<input id=w type=number min=1 value=1><input id=l type=number min=1 value=1>
--
OO
==

--

Hooray for the winner!

Python 2, 229 213 204 200 188 bytes
lambda n,l:"\n".join(["-"*l]+[i%2and"".join(j-i/2&1+2*(n>1)and"  "or x.append(1)or"H0000##"[len(x)%7]*2for j in range(l/2))or((i-n*2and"- "or"=")*l)[:l]for i in range(1,n*4)]+["-"*l])
x=[]

Try it online!

My longest codegolf answer so far

Can't check right now, but wouldn't it be shorter to add a line at the beginning 'r=range'? and replace all range with r?

@Matias it would be exactly the same length

PHP, 160 186 178 173 170 168 163 bytes
for(;$y<=2*$h=2*$argv[2];$y+=print"
")for($x=0;$x++<$w=$argv[1];)echo$y%2?($x+$y+$h*$y)%($h+2)>1|$x>($w&~1)?" ":UBUGUBU[$n++%14/2]:" -="[$y%(2*$h)?$y-$h?$x&1:2:1];

takes input from command line; Run with -nr. The holes are Good, Bad and Ugly.
breakdown
for(;$y<=2*$h=2*$argv[2];$y+=print"\n") # loop throug lines and lanes, post-print newline
    for($x=0;$x++<$w=$argv[1];)echo         # loop from left to right and print ...
        $y%2
        ?                                       # lanes:
            ($x+$y+$h*$y)%($h+2)>1                  # if not the position for a hole
            |$x>($w&~1)                             # or too close to the end
            ?" "                                    # then space
            :UBUGUBU[$n++%14/2]                     # else hole
    :" -="[                                     # or lines:
        $y%(2*$h)                               # if neither top nor bottom line
            ?   $y-$h                               # if not middle line
                ?   $x&1                                # then "- "
                :   2                                   # else "=="
            :   1                                   # else "--"
    ]
    ;

($x-$y)+$y*($h+2) --> ($x+$y+$h*$y)
$w<$x+1&&$w&1 --> $x>$w-($w&1) --> $x>($w&~1)
($y%(2*$h)?$y-$h?" -"[$x&1]:"=":"-") -->
($y%(2*$h)?" -="[$y-$h?$x&1:2]:"-") (thanks @Christoph) -->
" -="[$y%(2*$h)?$y-$h?$x&1:2:1]

$y-$h?" -"[$x&1]:"=" to " -="[$y-$h?$x&1:2] for 1 byte.

Uhm you might want to check that: $y<=2*$h=2*$argv[2] to $y<=2*$h (+2, first iteration starts even if h == 0), for($x=0;$x++<$w=$argv[1];) to for($x=0;$x++<$w=$argv[1];$h=2*$argv[2]) (+0, basically just moved), ($x+$y+$h*$y)%($h+2)>1 to ($x+$y*++$h)%++$h>1 (-3). Adding up to -1 bytes but I haven't tested it.

@Christoph division by zero at %(2*$h)

Batch, 380 bytes
@echo off
set h=O#OHO#O
set r=
for /l %%i in (1,1,%1)do call set r=--%%r%%
set/an=%2*2-1
for /l %%j in (0,1,%n%)do call:c %1 %2 %%j
echo %r%
exit/b
:c
if %3==0 (echo %r%)else if %3==%2 (echo %r:-==%)else echo %r:--=- %
set s=
for /l %%i in (1,1,%1)do set/an=%3-%%i^&3&call:l
echo(%s%
exit/b
:l
if %n%==3 (set s=%s%%h:~,1%%h:~,1%&set h=%h:~1%%h:~,1%)else set s=%s%