#StackBounty: #javascript #ai #game-mechanics #path-finding Game AI move towards player while avoiding an obstacle

Bounty: 50

I’m trying to move enemy towards player, while enemy also tries to avoid an obstacle if it’s in its path. Here’s a simple illustration of what I want to do:

enter image description here

What I’ve tried:

  • Making circular collision around the obstacle. It works but that
    makes the enemy impossible to hit.

  • I think going with an A* pathfinding algorithm might be a bit overkill
    especially since it’s designed for multiple obstacles, where in my
    case there is only the mouse and wall collision concerned.

  • Moving the enemy towards the player, while also moving away from the
    obstacle at a slower speed. This works better because you can
    actually hit the enemy, but also slows down enemy if obstacle if it’s
    in its path.

My questions:

  1. Is there a better way to go about doing this?
  2. Anything you would’ve done differently with my code to either improve or optimize?

Here’s the code I have currently in my game logic and a fully-working example on jsFiddle.

// Calculate vector between player and target
var toPlayerX = playerPosX - enemyPosX;
var toPlayerY = playerPosY - enemyPosY;

// Calculate vector between mouse and target
var toMouseX = mousePosX - enemyPosX;
var toMouseY = mousePosY - enemyPosY;

// Calculate distance between player and enemy, mouse and enemy
var toPlayerLength = Math.sqrt(toPlayerX * toPlayerX + toPlayerY * toPlayerY);
var toMouseLength = Math.sqrt(toMouseX * toMouseX + toMouseY * toMouseY);

// Normalize vector player
toPlayerX = toPlayerX / toPlayerLength;
toPlayerY = toPlayerY / toPlayerLength;

// Normalize vector mouse
toMouseX = toMouseX / toMouseLength;
toMouseY = toMouseY / toMouseLength;

// Move enemy torwards player
enemyPosX += toPlayerX * speed;
enemyPosY += toPlayerY * speed;

// Move enemy away from obstacle (a bit slower than towards player)
enemyPosX -= toMouseX * (speed * 0.4);
enemyPosY -= toMouseY * (speed * 0.4);

Get this bounty!!!

#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 ≥ 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;

    } // 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.


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

The latest version can be installed with

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



#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:


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


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


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.


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
//  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)

            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

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

            previousActivations = feedForward.activations


        return (networkInputs, networkActivations, networkActivationRates)

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

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

        return gradient

    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()
        var previousGradient = JPSNeuralNetwork.outputGradientFor(costFunction: costFunction, activations: outputLayerActivations, activationRates: outputLayerActivationRates, targetOutputs: targetOutputs)

        var gradient = Matrix()

        for (layerActivationRates, (layerActivations, layerWeights)) in zip(reversedActivationRates, zip(reversedActivations, reversedWeights))
            previousGradient = JPSNeuralNetworkLayer.gradientFor(activations: layerActivations, activationRates: layerActivationRates, weights: layerWeights, gradient: previousGradient)


        return gradient.reversed()

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

        for ((layerInputs, layerWeights), layerGradient) in zip(zip(inputs, weights), gradient)
            let newLayerWeights = JPSNeuralNetworkLayer.updateWeights(learningRate: learningRate, inputs: layerInputs, weights: layerWeights, gradient: layerGradient)

        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)

        return JPSNeuralNetwork.updateWeights(learningRate: learningRate, inputs: inputs, weights: weights, gradient: gradient)

    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)

                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
//  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

     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,

        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)

        vDSP_mmul(gradient, 1,
                  weights, 1,
                  &layerGradient, 1,
                  1, vDSP_Length(activations.count),

        vDSP_vmul(layerGradient, 1,
                  activationRates, 1,
                  &layerGradient, 1,

        return layerGradient

     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
        var scaledGradient = Vector(repeating: 0, count: gradient.count)

        vDSP_vsmul(gradient, 1,
                   &scaledGradient, 1,

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

        vDSP_mmul(scaledGradient, 1,
                  inputs, 1,
                  &scaledInputs, 1,
                  vDSP_Length(scaledGradient.count), vDSP_Length(inputs.count),

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

        vDSP_vadd(weights, 1,
                  scaledInputs, 1,
                  &layerWeights, 1,

        return layerWeights


//  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:

            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:

            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:

            return (activation * (1 - activation))

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

        case .sigmoid:

            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)

        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.

enter image description here

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.)

enter image description here

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.

enter image description here

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.

Here’s another way to think about this that approaches the topic through the formulas instead of visually:

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:



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

Sample Output


Complete the function next_move that takes in 3 parameters: posr and posc denote the co-ordinates of the bot’s current position, and board denotes the board state, and print the bot’s next move.

The goal is to clean all the dirty cells in as few moves as possible. Your score is (200 – #bot moves)/25. All bots in this challenge will be given the same input. CLEAN is also considered a move.

Education Links


Solution tester posted alongside the program for users to test their input as well.