#StackBounty: #game #health #accessibility #fitness #wii Wii games for a child with motor impairment

Bounty: 50

I have a 4-year old child with motor impairment, and recently came across several papers regarding how playing Wii games can yield improvements in dexterity, limb coordination, balance and motor proficiency, such as [1] [2].

What I’m looking for is recommendations for games that would be suitable. Requirements:

  1. Ideally, to begin with at least, the games should be playable using only movement of the controller (without the buttons)
  2. I’m also interested in games that use only the ‘nunjuks’
  3. Games must not be too fast paced

As an example, the Wii Sports: Tennis game fits the first requirement, but it is too fast paced.


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;

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

#StackBounty: #java #algorithm #game #collision Handling collision on a turn-based 2D game

Bounty: 100

I have implemented a collision check algorithm that I have created for my game, and the algorithm uses recursion.

Now it all works fine, and I thought to myself, what if there was a way to solve this algorithm, without using recursion, and more something with promise callbacks, or something, but unfortunately after researching, I could not find any way that I can think of at this time, so I thought I should ask there.

Now by turn-based I mean that the game is basically a big board of rectangles where each rectangle is a tile position, and there are ships, each ship can be on a tile unless its a rock, or another ship on there.

Now the collision is handled server-sided, so the coordinates are always integers, so it’s not some graphical collision check, don’t get me wrong.

There’s an Example of collision, you can see that the ship selected the moves Right, Left, Right, and the left move collided, because the other ship does not move at that turn of the move.

So how does my algorithm work

    // Loop through all turns
    for (int turn = 0; turn < 4; turn++) {
        // Loop through phases in the turn (split turn into phases, e.g turn left is 2 phases, turn forward is one phase).
        // So if stopped in phase 1, and its a turn left, it will basically stay in same position, if in phase 2, it will only
        // move one step instead of 2 full steps.
        for (int phase = 0; phase < 2; phase++) {

             // Go through all players and check if their move causes a collision
             for (Player p : players) {

                 // If a player is already collided in this step, we don't want him to move
                 // anywhere, so we skip this iteration
                 if (p.getCollisionStorage().isCollided(turn)) {
                     continue;
                 }

                 // Checks collision for the player, according to his current step #phase index and turn
                 collision.checkCollision(p, turn, phase, true);
           }
        }
     }

So basically checkCollision(Player p, int turn, int phase, boolean setPos) is where the collision is handled, and is a big method. This method basically goes through the collision rules and saves into players’ collision storage if it collided or not.

But here comes the recursion part: When a tile is already claimed, in the method, we check if the claimed player has a move placed on that turn, if yes, we will run the checkCollision method on that player that claimed it, if the player collided during his move, the method will return true, and then we know that this claimed player did not move, so the player we check for will collide with him. And now imagine a line of ships, and ship A wants to move forward, so we check ship B, ship B checks ship C and on and on and makes sure that every checkCollision returned false, so ship A can move and rest can move as-well.

Now I am curious, if there is a better way on implementing this besides using a recursion?

/**
 * Checks if a player has a collision according to his move, in the given turn and move-phase
 * @param p             The player to check
 * @param turn          The turn
 * @param phase         The move-phase step
 * @param setPosition   If to set the next position or not on non-collided result
 * @return  <code>TRUE</code> If the player was collided, <code>FALSE</code> if not.
 */
public boolean checkCollision(Player p, int turn, int phase, boolean setPosition) {
    // The current selected move of the player
    MoveType move =  p.getMoves().getMove(turn);

    // If this player was bumped, and a move was not selected, we want to process the bump animation
    // But we have to check if the position to be bumped is available to be claimed
    if (move == MoveType.NONE && p.getCollisionStorage().isBumped()) {
        Position pos = p.getCollisionStorage().getBumpAnimation().getPositionForAnimation(p);
        Player claimed = players.getPlayerByPosition(pos.getX(), pos.getY());
        // Claiming checking for the new position for bump
        return claimed != null && (claimed.getMoves().getMove(turn) == MoveType.NONE || checkCollision(claimed, turn, phase, false));
    }

    // Use the current position as default, imply we have already set it
    Position position = p;

    // If not set by default.txt on previous loops, gets the next position on the map for the given phase on the given move
    if (!p.getCollisionStorage().isPositionChanged()) {
        position = move.getNextPositionWithPhase(p, p.getFace(), phase);
    }
    // If the player has moved since his last position
    if (!position.equals(p)) {
        // Check for bounds collision with the border
        if (checkBoundCollision(p, turn, phase) || checkRockCollision(p, turn, phase)) {
            return true;
        }
        // Check if the next position is claimed by another player, null result if not
        Player claimed = players.getPlayerByPosition(position.getX(), position.getY());

        // If the result is not null, the position is claimed
        if (claimed != null) {
            Position claimedNextPos = claimed;
            if (!claimed.getCollisionStorage().isPositionChanged()) {
                claimedNextPos = claimed.getMoves().getMove(turn).getNextPositionWithPhase(claimed, claimed.getFace(), phase);
            }

            // Check if the claimed position doesn't move away
            if (claimed.getMoves().getMove(turn) == MoveType.NONE || claimedNextPos.equals(claimed)) {
                if (move != MoveType.FORWARD || claimed.getVessel().getSize() >= p.getVessel().getSize()) {
                    collide(p, claimed, turn, phase);
                }

                if (move == MoveType.FORWARD && canBumpPlayer(p, claimed, turn, phase)) {
                    bumpPlayer(claimed, p, turn, phase);
                    p.set(position);
                    p.getCollisionStorage().setPositionChanged(true);
                }

                claimed.getVessel().appendDamage(p.getVessel().getRamDamage());

                return true;
            }
            else if (claimedNextPos.equals(p)) { // If they switched positions (e.g nose to nose, F, F move)
                collide(p, claimed, turn, phase);
                collide(claimed, p, turn, phase);
                return true;
            }
            else {
                // Make sure that the claimed position moves away successfully
                if (!checkCollision(claimed, turn, phase, false)) {
                    if (setPosition) {
                        // Moved successfully, claim position
                        p.set(position);
                        p.getCollisionStorage().setPositionChanged(true);
                    }
                }
                else {
                    // did not move successfully, collide
                    collide(p, claimed, turn, phase);
                    collide(claimed, p, turn, phase);
                    return true;
                }
            }
        } else {
            // List of players that collided with this player, while performing this move, in this phase
            List<Player> collisions = getPlayersTryingToClaim(p, position, turn, phase);

            if (collisions.size() > 0) { // Collision has happened
                collisions.add(p);

                Player largest = getLargestSize(collisions);

                if (countPlayersForSize(collisions, largest.getVessel().getSize()) > 1) {
                    // Stop players from movement
                    for (Player pl : collisions) {
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, pl, turn, phase);
                    }
                }
                else {
                    for (Player pl : collisions) {
                        if (pl == largest) {
                            continue;
                        }
                        pl.getCollisionStorage().setCollided(turn, phase);
                        collide(pl, largest, turn, phase);
                    }
                    if (!largest.getCollisionStorage().isPositionChanged()) {
                        largest.set(position);
                        largest.getCollisionStorage().setPositionChanged(true);
                    }
                }
                return true;
            } else {
                if (setPosition) {
                    p.set(position);
                    p.getCollisionStorage().setPositionChanged(true);
                }
            }
        }
    }

    return false;
}


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!

#StackBounty: #code-challenge #game #cellular-automata #game-of-life #tetris Build a working game of Tetris in Conway's Game of Life

Bounty: 100

Here is a theoretical question – one that doesn’t afford an easy answer in any case, not even the trivial one.

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automation using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automation. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.

  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.

  • Fastest execution — the fewest generations to advance one tick in the simulation wins.

  • Initial live cell count — smaller count wins.

  • First to post — earlier post wins.


Get this bounty!!!