## #StackBounty: #c #game #ai Solving Chain Reaction on Small Boards: Verifying Correctness

### Bounty: 200

I’m writing a program that finds the minimax value of Chain Reaction on various small boards (à la Solving Go on Small Boards). Here’s a brief description of the game of Chain Reaction:

Chain Reaction is a two player combinatorial game played on an n×m game board (where n,m &geq; 2) in which players Red and Green take turns to place a single atom of their color in an empty square or in a square that they control. Placing more than one atom in the same square creates a molecule.

The more atoms in a molecule, the more unstable it becomes. When a molecule becomes too unstable it splits and its atoms move to orthogonally adjacent squares, changing the color of the atoms in those squares to match their color. This can cause a chain reaction of splitting molecules.

Molecules in the four corner squares require two atoms to split. Molecules on the edge of the board require three atoms to split. Molecules in the center of the board require four atoms to split. Atoms of a splitting molecule each move in a different direction. The game ends immediately after one player captures all of the atoms belonging to the other player.

I found the minimax value of Chain Reaction on the 2×2, 2×3, 2×4, 2×5, 2×6, 3×3 and 3×4 boards. However, I haven’t verified their correctness. Here are the values I obtained:

+---+---+---+---+---+---+
|nm| 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
| 2 |-2 |+4 |-6 |+8 |+10|
| 3 |   |+7 |+10|   |   |
+---+---+---+---+---+---+


A positive value represents a win for Red. A negative value represents a loss for Red. The absolute value represents the number of moves to the terminal state under optimal play. A move consists of a turn by each player. Therefore, a value of -2 means that Red loses in two moves (i.e. Red loses in 4 turns). On the other hand, a value of +4 means that Red wins in four moves (i.e. Red wins in 7 turns). This is assuming Red plays first starting on an empty board.

Anyway, here’s the C program that I wrote to obtain these values:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int x, y, z, m, v, h;
} transposition;

transposition table[2][0x1000000] = {0};

int v, w;

int negamax(int x, int y, int z, int m, int alpha, int beta) {
static int result = -8000, color = 1, height;

if (m) { // a move is to be played
// begin: add the atom to the board
int x2 = y & z, y2 = w ^ y ^ z ^ w & x2, z2 = ~z & (x | y), m2 = ~m;

x  = x2 & m | m2 & x;
y2 = y2 & m | m2 & y;
z2 = z2 & m | m2 & z;
m &= z & (w | y);

y = y2, z = z2;
// end: add the atom to the board

while (m) { // a chain reaction is caused
// move the atoms to the North, East, west and South squares
int news[4] = { m >> v, m << 1, m >> 1, m << v };

m = 0; // splitting molecules for next iteration

for (int i = 0; i < 4; i++) { // for each direction, add atoms
int n = news[i];

x2 = y & z, y2 = w ^ y ^ z ^ w & x2, z = ~z & (x | y), m2 = ~n;

x  = x2 & n | m2 & x;
y2 = y2 & n | m2 & y;
z2 = z2 & n | m2 & z;
m |= n & z & (w | y); // collect splitting molecules

y = y2, z = z2;
}

if ((x & (y | z)) == 0) { // the chain reaction wiped out the player
height = 0;
return result;
}
}

x ^= y | z; // swap players (i.e. Red becomes Green and vice versa)
}

// begin: calculate hash index and lookup transposition tables
int index = w;
index ^= x + 0x9E3779B9 + (index << 6) + (index >> 2);
index ^= y + 0x9E3779B9 + (index << 6) + (index >> 2);
index ^= z + 0x9E3779B9 + (index << 6) + (index >> 2);
index &= 0xFFFFFF;

for (int i = 0; i < 2; i++) {
transposition t = table[i][index];

if (t.x == x && t.y == y && t.z == z) {
height = t.h;

switch (t.v & 3) {
case 0: return t.v;
case 1: if (t.v > alpha) alpha = t.v; break;
case 2: if (t.v < beta)  beta  = t.v; break;
}

if (alpha >= beta) return t.v;

break;
}
} // end: calculate hash index and lookup transposition tables

int moves = y | z, cut = beta + 1 & ~3, value = -9000, h = 0, move;

result += 2 * (1 + color); // update return value for next ply
color =- color; // switch players

for (moves = (w | x | moves) & ~(x & moves); moves; moves &= moves - 1) {
m = moves & -moves; // the move is played when we call negamax

int val = -negamax(x, y, z, m, -beta, -alpha);

if (val > value) { value = val; move = m; }
if (val > alpha) alpha = val;
if (++height > h) h = height;
if (alpha >= beta) { value = (value + 1 & ~3) + 1; break; }
}

color =- color; // switch back players
result -= 2 * (1 + color); // restore return value for current ply

// begin: save return value in transposition table
transposition t = table[0][index];

int i = h < t.h;

if (!i) table[1][index] = t;

t.x = x;
t.y = y;
t.z = z;
t.m = move;
t.v = value;
t.h = height = h;

table[i][index] = t;
// end: save return value in transposition table

return value;
}

int main(int argc, char * argv[]) {
if (argc != 3) {
printf("Usage: %s nrows mcolsn", argv[0]);
printf("    nrows: number of rows (in the interval [2, 5])n");
printf("    mcols: number of cols (in the interval [n, 33/n-1])n");
return EXIT_SUCCESS;
}

int n = atoi(argv[1]);

if (n < 2 || n > 5) {
printf("Error: nrows must be in the interval [2, 5]n");
return EXIT_FAILURE;
}

int m = atoi(argv[2]);

if (m < n || m > 33 / n - 1) {
printf("Error: mcols must be in the interval [n, 33/n-1]");
return EXIT_FAILURE;
}

// begin: calculate initial empty bitboard values
v = m + 1, w = (1 << m) - 1;

{
int a = (1 << m - 1) + 1, b = w - a;
int i = n - 1, j = v, k = i * j;

w |= w << k;
x = a | a << k;

for (int k = 1; k < i; k++, j += v) {
w |= a << j;
x |= b << j;
}
}
// end: calculate initial empty bitboard values

int value = negamax(x, 0, 0, 0, -8000, 8000) / 4;

printf("#%dn", (value < 0 ? -2000 : 2000) - value);

return EXIT_SUCCESS;
}


Things you should know about my implementation:

• I used negamax with alpha beta pruning and transposition tables.
• I used the two-deep replacement scheme for transposition tables (with 2×224 entries).
• I used bitboards to represent the game state. The variables w, x, y and z hold the four bitboards that represent the game state. The variable w never changes and hence it’s a global variable. The variable m holds the bitboard for the current move. An explanation of how these bitboards work is found here.
• The values are represented by integers such that:
• +2000 represents a win in 0 moves.
• +1999 represents a win in 1 move.
• +1998 represents a win in 2 moves.
• -1998 represents a loss in 2 moves.
• -1999 represents a loss in 1 move.
• -2000 represents a loss in 0 moves.
• I’m using integrated bounds and values. Hence, the values are multiplied by 4. For lower bounds, the values are incremented. For upper bounds, the values are decremented.

I’d really appreciate it if you’d verify the correctness of my program and the values that it generates. Critiques and suggestions to improve my code are also welcome.

Get this bounty!!!

## Distributed Evolutionary Algorithms in Python

DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. It seeks to make algorithms explicit and data structures transparent. It works in perfect harmony with parallelization mechanism such as multiprocessing and SCOOP.

DEAP includes the following features:

• Genetic algorithm using any imaginable representation
• List, Array, Set, Dictionary, Tree, Numpy Array, etc.
• Genetic programing using prefix trees
• Loosely typed, Strongly typed
• Automatically defined functions
• Evolution strategies (including CMA-ES)
• Multi-objective optimisation (NSGA-II, SPEA2, MO-CMA-ES)
• Co-evolution (cooperative and competitive) of multiple populations
• Parallelization of the evaluations (and more)
• Hall of Fame of the best individuals that lived in the population
• Checkpoints that take snapshots of a system regularly
• Benchmarks module containing most common test functions
• Genealogy of an evolution (that is compatible with NetworkX)
• Examples of alternative algorithms : Particle Swarm Optimization, Differential Evolution, Estimation of Distribution Algorithm

See the DEAP User’s Guide for DEAP documentation.

## Installation

We encourage you to use easy_install or pip to install DEAP on your system. Other installation procedure like apt-get, yum, etc. usually provide an outdated version.

pip install deap

pip install git+https://github.com/DEAP/deap@master

If you wish to build from sources, download or clone the repository and type

python setup.py install

Source

## #StackBounty: #swift #ai #neural-network Neural Network in Swift

### Bounty: 100

This is my first Neural Network, specifically a multilayer feed forward neural network that uses back-propagation for training, and I plan on using it for a multitude of projects. I started with the XOR function and now I’m moving to OCR. This network, as far as I know, can also be used for deep learning. I chose Swift because it’s the language I’m most comfortable with. However, I may convert it to C++ for learning purposes.

Does anyone have any suggestions on how I could make this code more bullet proof, improve the quality, improve performance, more robust/versatile, etc.?

Also, is this a good style to use? Meaning is it common to use all class functions? I feel like this would reduce, if not eliminate, any side effects and makes the code more thread safe? I can easily whip up some instance methods that call the class methods, then in turn store the weights, activations, derivatives, etc..

It seems like it’s pretty fast compared to other neural networks that I’ve downloaded and compared it to (only 2 in all honesty). However, as this is my first ANN, I’m not sure what “fast” is defined as. When attempting to train and test it with the MNIST dataset on a late 2015 iMac 4GHz Intel Core i7 Processor with 8GB DDR3 the results are as follows:

## Topology

Number Of Layers: 3
Number of Input Neurons: 784
Number of Hidden Neurons: 20
Number of Output Neurons: 10

## Training

Epochs: 100
Final Cost: 0.00529893
Cost Function: Mean Squared
Activation Function: Sigmoid
Number Of Training Examples: 60,000
Elapsed Time: 24 minutes and 6 seconds

## Testing

Number of Testing Examples: 10,000
Number of Correct Predictions: 9,297
Ratio: 92.97%

Quick side note: I’m new to optimization as well but, it’s definitely something I would like to be better at!

I would greatly appreciate any suggestions! Please be as harsh as you deem necessary! Also, if any more information is needed feel free to let me know.

EDIT 1:

I doubt this is applicable here but, I would like to implement some type of “live” testing where the user could draw a number on the screen, feed it forward, and get a predication.

Do I need to normalize the image the same way as the MNIST data? (e.g. normalize to fit in a 20×20 image while preserving the aspect ratio, center in a 28×28 image, and compute the center of mass. Then, translate the image so as to position this point at the center of the 28×28 field.) The only problem with that is I don’t know the anti-aliasing technique used by the normalization algorithm to get the grey scale levels (hopefully I could just email Yann LeCun and find out though).

Here’s the GitHub incase anyone finds that easier to read: JPSNeuralNetwork

JPSNeuralNetwork.swift

//
//  JPSNeuralNetwork.swift
//
//  Created by Jonathan Sullivan on 4/4/17.
//

import Foundation
import Accelerate

public protocol JPSNeuralNetworkDelegate
{
func network(costDidChange cost: Float)
func network(progressDidChange progress: Float)
func network(overallProgressDidChange progress: Float)
}

public class JPSNeuralNetwork
{
private typealias FeedForwardResult = (inputs: Matrix, activations: Matrix, activationRates: Matrix)

private class func cost(costFunction: JPSNeuralNetworkCostFunction, activations: Matrix, targetOutputs: Matrix) -> Scalar
{
var cost: Scalar = 0

for (activation, targetOutput) in zip(activations, targetOutputs) {
cost += costFunction.cost(forOutputs: activation, targetOutputs: targetOutput)
}

cost /= Scalar(targetOutputs.count)

return cost
}

private class func weights(forTopology topology: [Int]) -> Matrix
{
var weights = Matrix()

var previousNumberOfInputs = topology[0]

for neuronCount in topology[1..<topology.count]
{
// Plus one for the bias weight.

let neuronWeights = JPSNeuralNetworkLayer.randomWeights(neuronCount: neuronCount, inputCount: previousNumberOfInputs + 1)
weights.append(neuronWeights)

previousNumberOfInputs = neuronCount
}

return weights
}

public class func feedForward(topology: [Int], activationFunction: JPSNeuralNetworkActivationFunction, inputs: Vector, weights: Matrix) -> Vector {
return JPSNeuralNetwork.feedForward(topology: topology, activationFunction: activationFunction, inputs: inputs, weights: weights).activations.last!
}

private class func feedForward(topology: [Int], activationFunction: JPSNeuralNetworkActivationFunction, inputs: Vector, weights: Matrix) -> FeedForwardResult
{
var previousActivations = inputs

var networkInputs = Matrix()
var networkActivations = Matrix()
var networkActivationRates = Matrix()

// Ignore the input layer as it's just a place holder.

for (neuronCount, layerWeights) in zip(topology[1..<topology.count], weights)
{
// Append one for the bias input.

var layerInputs = previousActivations
layerInputs.append(1)
networkInputs.append(layerInputs)

let feedForward = JPSNeuralNetworkLayer.feedForward(neuronCount: neuronCount, activationFunction: activationFunction, inputs: layerInputs, weights: layerWeights)

previousActivations = feedForward.activations

networkActivations.append(previousActivations)
networkActivationRates.append(feedForward.activationRates)
}

return (networkInputs, networkActivations, networkActivationRates)
}

private class func outputGradientFor(costFunction: JPSNeuralNetworkCostFunction, activations: Vector, activationRates: Vector, targetOutputs: Vector) -> Vector
{

for (activationRate, (activation, targetOutput)) in zip(activationRates, zip(activations, targetOutputs))
{
let costRate = costFunction.derivative(OfOutput: activation, targetOutput: targetOutput)
let error = (costRate * activationRate)
}

}

private class func gradientFor(costFunction: JPSNeuralNetworkCostFunction, activations: Matrix, activationRates: Matrix, weights: Matrix, targetOutputs: Vector) -> Matrix
{
let reversedWeights = weights.reversed()
var reversedActivations = (activations.reversed() as Matrix)
var reversedActivationRates = (activationRates.reversed() as Matrix)

let outputLayerActivations = reversedActivations.removeFirst()
let outputLayerActivationRates = reversedActivationRates.removeFirst()

for (layerActivationRates, (layerActivations, layerWeights)) in zip(reversedActivationRates, zip(reversedActivations, reversedWeights))
{

}

}

private class func updateWeights(learningRate: Float, inputs: Matrix, weights: Matrix, gradient: Matrix) -> Matrix
{
var newWeights = Matrix()

{
newWeights.append(newLayerWeights)
}

return newWeights
}

private class func backpropagate(learningRate: Float, costFunction: JPSNeuralNetworkCostFunction, inputs: Matrix, weights: Matrix, activations: Matrix, activationRates: Matrix, targetOutput: Vector) -> Matrix
{
let gradient = JPSNeuralNetwork.gradientFor(costFunction: costFunction, activations: activations, activationRates: activationRates, weights: weights, targetOutputs: targetOutput)

}

public class func train(delegate: JPSNeuralNetworkDelegate?, topology: [Int], epochs: Int, learningRate: Float, activationFunction: JPSNeuralNetworkActivationFunction, costFunction: JPSNeuralNetworkCostFunction, trainingInputs: Matrix, targetOutputs: Matrix) -> Matrix
{
var weights = JPSNeuralNetwork.weights(forTopology: topology)

for epoch in 0..<epochs
{
var activations = Matrix()

for (index, (inputs, targetOutput)) in zip(trainingInputs, targetOutputs).enumerated()
{
let progress = (Float(index + 1) / Float(targetOutputs.count))
delegate?.network(progressDidChange: progress)

let overallProgress = ((Float(epoch) + progress) / Float(epochs))
delegate?.network(overallProgressDidChange: overallProgress)

let feedForward: FeedForwardResult = JPSNeuralNetwork.feedForward(topology: topology, activationFunction: activationFunction, inputs: inputs, weights: weights)
activations.append(feedForward.activations.last!)

weights = JPSNeuralNetwork.backpropagate(learningRate: learningRate, costFunction: costFunction, inputs: feedForward.inputs, weights: weights, activations: feedForward.activations, activationRates: feedForward.activationRates, targetOutput: targetOutput)
}

let cost = JPSNeuralNetwork.cost(costFunction: costFunction, activations: activations, targetOutputs: targetOutputs)
delegate?.network(costDidChange: cost)
}

return weights
}
}


JPSNeuralNetworkLayer.swift

//
//  JPSNeuralNetworkLayer.swift
//
//  Created by Jonathan Sullivan on 4/4/17.
//

import Foundation
import Accelerate

public class JPSNeuralNetworkLayer
{
/**
Used to generate a random weights for all neurons.
*/
public class func randomWeights(neuronCount: Int, inputCount: Int) -> Vector
{
var layerWeights = Vector()

for _ in 0..<neuronCount
{
let neuronWeights = JPSNeuralNetworkNeuron.randomWeights(inputCount: inputCount)
layerWeights.append(contentsOf: neuronWeights)
}

return layerWeights
}

/**
Used to feed the inputs and weights forward and calculate the weighted input and activation.
This method also precalculates the activation rate for use later on and to reduce the number of
calculations.

weightedInput = sum(x[i] * w[i])
activation = sigma(weightedInput[j])
activationRate = sigma'(activation[j])
*/
public class func feedForward(neuronCount: Int, activationFunction: JPSNeuralNetworkActivationFunction, inputs: Vector, weights: Vector) -> (activations: Vector, activationRates: Vector)
{
var activations = Vector(repeating: 0, count: neuronCount)

vDSP_mmul(weights, 1,
inputs, 1,
&activations, 1,
vDSP_Length(neuronCount), 1,
vDSP_Length(inputs.count))

activations = activations.map({
return activationFunction.activation($0) }) let activationRates = activations.map({ return activationFunction.derivative($0)
})

return (activations, activationRates)
}

/**
Used to calculate the error gradient for each neuron.
*/
public class func gradientFor(activations: Vector, activationRates: Vector, weights: Vector, gradient: Vector) -> Vector
{
var layerGradient = Vector(repeating: 0, count: activations.count)

weights, 1,
1, vDSP_Length(activations.count),

activationRates, 1,

}

/**
Used to generate update each neurons weights on a per neuron error basis given the input.
*/
public class func updateWeights(learningRate: Float, inputs: Vector, weights: Vector, gradient: Vector) -> Vector
{
var nagativeLearningRate = -learningRate

&nagativeLearningRate,

var scaledInputs = Vector(repeating: 0, count: weights.count)

inputs, 1,
&scaledInputs, 1,
1)

var layerWeights = Vector(repeating: 0, count: weights.count)

scaledInputs, 1,
&layerWeights, 1,
vDSP_Length(weights.count))

return layerWeights
}
}


JPSNeuralNetworkNeuron.swift

//
//  JPSNeuralNetworkNeuron.swift
//
//  Created by Jonathan Sullivan on 4/4/17.
//

import Foundation

public typealias Scalar = Float
public typealias Vector = [Scalar]
public typealias Matrix = [Vector]

public enum JPSNeuralNetworkCostFunction: Int
{
case meanSquared = 0
case crossEntropy = 1

func derivative(OfOutput output: Scalar, targetOutput: Scalar) -> Scalar
{
switch self
{
case .crossEntropy:
return (output - targetOutput) / ((1 - output) * output)

case .meanSquared:
fallthrough

default:
return (output - targetOutput)
}
}

func cost(forOutputs outputs: Vector, targetOutputs: Vector) -> Scalar
{
switch self
{
case .crossEntropy:
return -zip(outputs, targetOutputs).reduce(0, { (sum, pair) -> Scalar in
let temp = pair.1 * log(pair.0)
return sum + temp + (1 - pair.1) * log(1 - pair.0)
})

case .meanSquared:
fallthrough

default:
return 0.5 * zip(outputs, targetOutputs).reduce(0, { (sum, pair) -> Scalar in
return pow(pair.1 - pair.0, 2)
})
}
}
}

public enum JPSNeuralNetworkActivationFunction: Int
{
case sigmoid = 0
case hyperbolicTangent = 1

func derivative(_ activation: Scalar) -> Scalar
{
switch self
{
case .hyperbolicTangent:
return (1 - pow(activation, 2))

case .sigmoid:
fallthrough

default:
return (activation * (1 - activation))
}
}

func activation(_ weightedInput: Scalar) -> Scalar
{
switch self
{
case .hyperbolicTangent:
return tanh(weightedInput)

case .sigmoid:
fallthrough

default:
return (1 / (1 + exp(-weightedInput)))
}
}
}

public class JPSNeuralNetworkNeuron
{
/**
Used to generate a single random weight.
*/
private class func randomWeight(inputCount: Int) -> Scalar
{
let range = (1 / sqrt(Scalar(inputCount)))
let rangeInt = UInt32(2000000 * range)
let randomDouble = Scalar(arc4random_uniform(rangeInt)) - Scalar(rangeInt / 2)
return (randomDouble / 1000000)
}

/**
Used to generate a vector of random weights.
*/
public class func randomWeights(inputCount: Int) -> Vector
{
var weights = Vector()

for _ in 0..<inputCount
{
let weight = JPSNeuralNetworkNeuron.randomWeight(inputCount: inputCount)
weights.append(weight)
}

return weights
}
}


Get this bounty!!!

## What is the difference between linear regression on y with x and x with y?

The Pearson correlation coefficient of x and y is the same, whether you compute pearson(x, y) or pearson(y, x). This suggests that doing a linear regression of y given x or x given y should be the same, but that’s the case.

The best way to think about this is to imagine a scatter plot of points with y on the vertical axis and x represented by the horizontal axis. Given this framework, you see a cloud of points, which may be vaguely circular, or may be elongated into an ellipse. What you are trying to do in regression is find what might be called the ‘line of best fit’. However, while this seems straightforward, we need to figure out what we mean by ‘best’, and that means we must define what it would be for a line to be good, or for one line to be better than another, etc. Specifically, we must stipulate a loss function. A loss function gives us a way to say how ‘bad’ something is, and thus, when we minimize that, we make our line as ‘good’ as possible, or find the ‘best’ line.

Traditionally, when we conduct a regression analysis, we find estimates of the slope and intercept so as to minimize the sum of squared errors. These are defined as follows:

In terms of our scatter plot, this means we are minimizing the sum of the vertical distances between the observed data points and the line.

On the other hand, it is perfectly reasonable to regress x onto y, but in that case, we would put x on the vertical axis, and so on. If we kept our plot as is (with x on the horizontal axis), regressing x onto y (again, using a slightly adapted version of the above equation with x and y switched) means that we would be minimizing the sum of the horizontal distances between the observed data points and the line. This sounds very similar, but is not quite the same thing. (The way to recognize this is to do it both ways, and then algebraically convert one set of parameter estimates into the terms of the other. Comparing the first model with the rearranged version of the second model, it becomes easy to see that they are not the same.)

Note that neither way would produce the same line we would intuitively draw if someone handed us a piece of graph paper with points plotted on it. In that case, we would draw a line straight through the center, but minimizing the vertical distance yields a line that is slightly flatter (i.e., with a shallower slope), whereas minimizing the horizontal distance yields a line that is slightly steeper.

A correlation is symmetrical x is as correlated with y as y is with x. The Pearson product-moment correlation can be understood within a regression context, however. The correlation coefficient, r, is the slope of the regression line when both variables have been standardized first. That is, you first subtracted off the mean from each observation, and then divided the differences by the standard deviation. The cloud of data points will now be centered on the origin, and the slope would be the same whether you regressed y onto x, or x onto y.

Now, why does this matter? Using our traditional loss function, we are saying that all of the error is in only one of the variables (viz., y). That is, we are saying that x is measured without error and constitutes the set of values we care about, but that y has sampling error. This is very different from saying the converse. This was important in an interesting historical episode: In the late 70’s and early 80’s in the US, the case was made that there was discrimination against women in the workplace, and this was backed up with regression analyses showing that women with equal backgrounds (e.g., qualifications, experience, etc.) were paid, on average, less than men. Critics (or just people who were extra thorough) reasoned that if this was true, women who were paid equally with men would have to be more highly qualified, but when this was checked, it was found that although the results were ‘significant’ when assessed the one way, they were not ‘significant’ when checked the other way, which threw everyone involved into a tizzy. See here for a famous paper that tried to clear the issue up.

The formula for the slope of a simple regression line is a consequence of the loss function that has been adopted. If you are using the standard Ordinary Least Squares loss function (noted above), you can derive the formula for the slope that you see in every intro textbook. This formula can be presented in various forms; one of which I call the ‘intuitive’ formula for the slope. Consider this form for both the situation where you are regressing y on x, and where you are regressing x on y:

Now, I hope it’s obvious that these would not be the same unless Var(xequals Var(y). If the variances are equal (e.g., because you standardized the variables first), then so are the standard deviations, and thus the variances would both also equal SD(x)SD(y). In this case, β^1 would equal Pearson’s r, which is the same either way by virtue of the principle of commutativity:

Source

## HackerRank: BotClean Partially Observable

Problem Statement

The game Bot Clean took place in a fully observable environment, i.e., the state of every cell was visible to the bot at all times. Let us consider a variation of it where the environment is partially observable. The bot has the same actuators and sensors. But the sensors visibility is confined to its 8 adjacent cells.

Input Format
The first line contains two space separated integers which indicate the current position of the bot. The board is indexed using Matrix Convention

5 lines follow, representing the grid. Each cell in the grid is represented by any of the following 4 characters:
‘b’ (ascii value 98) indicates the bot’s current position,
‘d’ (ascii value 100) indicates a dirty cell,
‘-‘ (ascii value 45) indicates a clean cell in the grid, and
‘o’ (ascii value 111) indicates the cell that is currently not visible.

Output Format
Output is the action that is taken by the bot in the current step. It can either be any of the movements in 4 directions or the action of cleaning the cell in which it is currently located. Hence the output formats are LEFT, RIGHT, UP, DOWN or CLEAN.

Sample Input

0 0
b-ooo
-dooo
ooooo
ooooo
ooooo


Sample Output

RIGHT