Queen's Challenge - Part 5 of 6

 Part 5 – Backtrack Solver

While a smarter brute force method had a drastic effect on the performance of our solver, we were still trying out a huge number of combinations that were clearly not going to work. If only there was some way to eliminate the bulk of these clearly invalid moves. There is an approach called backtrack solving, which attempts to prune as many searches as possible. This is often depicted as a tree, so lets represent our first few rows as a tree.

As you can see, for each of the moves in the first row of the board, each piece of the second row has 8 moves it can make. For each combination of the first and second piece, there is an additional 8 moves for that combination, and so on. If, however, the first row and the second row are in conflict, then all the moves underneath the second row position are also in conflict so the entire branch underneath that move can be eliminated. This leads to a very simple process. For whatever row we are working on, lets call it depth as that is the generic term for a tree search, we try the first available position. If that position is not in conflict with any other queens, we go to the next row otherwise we go to the next position. If for a given row there is no valid position, we backtrack by going to the previous row and moving it to the next position. Repeat until all pieces are placed on the board or there are no more possible moves to try (no solution to the problem).

Implementation of a backtrack solver is not that much more difficult than brute-force methods but does require some slight modifications to how the solver works. Instead of placing all the pieces on the board, we only place the locked piece and a queen for each of the rows we have processed. We will use the term depth to represent how many of our pieces we have placed. As I am a programmer, the count will start at 0.

class BacktrackSolver extends BaseSolver {
    constructor(game) {
        super(game);
        this.depth = 0;
    }

 

We can change how pieces are placed on the board by overriding the placeStepOnBoard method and making all the pieces beyond our current depth invisible. Some minor changes to reflect this change were made to the isBoardSolved method but I won’t go over the details here.

    placeStepOnBoard() {
        super.placeStepOnBoard();
        for (let i = this.depth+1; i < 7; ++i)
            this.game.queens[i+1].setVisible(false);
    }

 

The reset method is very simple as we just need to set the depth to 0 and start our first queen off on either the first row or second row if the first row is occupied by the locked queen.

reset() {
    this.locked = this.game.queens[0].y * 8 + this.game.queens[0].x;
    let lockedRow = this.game.queens[0].y;
    if (lockedRow === 0)
        this.moveable[0] = 8;
    else
        this.moveable[0] = 0;
    this.depth = 0;
    this.placeStepOnBoard();
}

 

Because we need to check if a queen is in conflict with another queen, we will take advantage of the game logic we already have within the game instead of re-writing the logic. This can be a bit confusing as the locked queen is queens[0] while our queens are 1 through seven but you only need to add 1 to the current depth to find the queen we are working with. We first check to see if the queen we are looking at is in a valid position assuming it is not valid if we are backtracking. If the board is in a valid state then we start the next depth by placing the next queen in the starting column of it’s row, skipping over the locked row when necessary and we have finished our move. If the board is not in a valid position, then we stay at the same depth moving our queen to the next column of the row. If the queen is able to be moved, we are done. On the other hand, if the queen is at the end of the row, we need to backtrack so we reduce our depth and repeat the above.

    nextMove() {
        let moved = false;
        let backtrack = false;
        while ( ! moved) {
            let queen = this.game.queens[this.depth+1];
            queen.setVisible(false);
            if ((!backtrack) && (this.game.canEnterTile(queen.x, queen.y))) {
                // spawn next depth
                ++this.depth;
                let lockedRow = this.game.queens[0].y;
                this.moveable[this.depth] = (queen.y+1) * 8;
                if ((queen.y+1) === lockedRow)
                    this.moveable[this.depth] += 8;
                moved = true;
            } else {
                if (queen.x < 7) {
                    this.moveable[this.depth] += 1;
                    moved = true;
                } else {
                    backtrack = true;
                    --this.depth;
                }
            }
        }
    }
}

 

Running the solver will usually result in a solution in under a minute, which is really good when you consider that we are only doing 10 steps per second. So, mathematically speaking, how long should this take? Best case would be 7 steps. The theoretical worst case is 8^7 for 2,097,152 which happens to be the same as the brute-force lines method. For this particular problem, we know that we will be pruning a lot of branches so our results will be significantly better than worst case, but calculating this is not a trivial matter so will leave the calculations to the more mathematically inclined.

Can we improve things further? Watching the results, you will notice that many of the boards checked are positions that are obviously bad based on the above pieces. If only there was a way of just checking potentially valid tiles. We will call this forward checking and look at it next time.

Queen's Challenge - Part 4 of 6

 Part 4 – One Queen Per Row

Last time we saw a big problem with the brute force approach which we saw that queens were often placed on the same horizontal line as other queens which we know is not possible. This is a problem that can easily be rectified by imposing a constraint on where we are allowed to place the queens.  Ultimately, we are still going to be brute forcing the solution but by removing the most obvious issues with brute force.

The term constraint is simply mathematical speak about a rule restricting the values a variable can hold based on the value in other variables. Having more than one queen in a given row is clearly not valid so we can eliminate all boards where there are multiple queens on a single line. Applying the constraint that each queen must be on a unique row drastically will improve the performance of our search for a solution.

Creating our row-based brute force solver is simple enough as we can just extend the BaseSolver to get much of the logic. The only things we then need to implement is the reset and the next move methods and they are very similar to the brute force solver.

class RowBruteSolver extends BaseSolver {
    constructor(game) {
        super(game);
    }

    reset() {
        this.locked = this.game.queens[0].y * 8 + this.game.queens[0].x;
        let lockedRow = this.game.queens[0].y
        let spot = 0;
        for (let i = 0; i < 7; ++i) {
            if (i === lockedRow)
                spot += 8;
            this.moveable[i] = spot;
            spot += 8;
        }
    }

 

As with the brute force solver, we set the locked tile to be the tile number of the tile based on the row and column of the locked tile in the game. We need to know which row this tile is on, which is just the y coordinate of the locked queen. As each row of tiles has 8 tiles on it, we know that the tile number will be 8*the row but we know we need to skip the row that row that the locked queen is on. To do this we use a spot variable that starts at 0 and if the current row is the same row as the locked row increases the spot by 8 to move the starting spot to the first (0) column of the next row. The queen is set and we update the spot for the next queen by adding 8 to it.

 

    nextMove() {
        let pieceToMove = 0;
        for (let i = 6; i >= 0; --i) {
            let nextPos = this.moveable[i] + 1;
            if ((nextPos % 8) > 0) {
                pieceToMove = i;
                this.moveable[i] = nextPos;
                break;
            }
        }
        for (let i = pieceToMove+1; i < 7; ++i) {
            this.moveable[i] = Math.floor(this.moveable[i] / 8)*8;
        }
    }
}

 

The nextMove method tries to move the last row’s queen to the next column and if that move results in the queen going off the board , moves up the list row by row until it finds a queen that it can move to the right without going off the board. Once that has been done, we simply set the queens below it to the first tile of that column.

Watching the results of this solver clearly shows an improvement from the first solver. If you are patient and can wait a few hours, you can even see a solution to the game. Watching for a minute or so will quickly show us the next issue that we need to solve. We still are placing queens in locations were they are in conflict with each other and then processing all the queens below the conflicting queens even though we know that none of those potential layouts will result in a valid solution. Still this is a big improvement over the brute force approach.

From a worst-case perspective, we know that there are 7 queens with each queen having 8 possible locations so that would be 8^7 possible boards that need to be examined. While 2,097,152 boards is certainly better than 994,596,970,221 it is still quite a bit of work. We can do even better by finding a way to remove all those unnecessary searches. But how can we do this? A simple change to our solver will allow us to eliminate entire branches of moves so we don’t waste time testing moves that can’t possibly work as we will discover in the next part.

Queen’s Challenge - part 3 of 6

 Part 3 – Brute Force

Brute force approaches to solving problems are often the first approaches tried when attempting to solve a problem. Computers are fast, so why not just try all the possible solutions until we find one that works? As we will see shortly, while brute force solutions work, they are very inefficient making them infeasible for many problems.

A brute force solution for the Queen’s Challenge game would be to simply try all possible combinations until you find one that works. If I didn’t have my animation framework this would be trivially easy to implement, but by showing each step as I am, the work is a bit more complicated. Without the animation, the brute force method would look something like this:

Q0 = assigned_location
For q1 in range (1..58):

For q2 in range(q1..59):

…

For q7 in range(q6..64):

If (valid layout) break

Doing updates using steps is a bit trickier as we don’t have nested loops so will need to manually track the loop.  If you recall, a for loop is essentially just a macro for making a while loop with a counter. This concept can be easily extended to supporting nested loops by simply holding an array of loop indexes and updating them appropriately. This means that to implement our animated version of brute force solving we first need to set up an array of indexes, which we already are doing to hold the positions of the queens.  The reset method would then look something like this:

    reset() {
        this.locked = this.game.queens[0].y * 8 + this.game.queens[0].x;
        let spot = 0;
        for (let i = 0; i < 7; ++i) {
            if (this.locked !== spot)
                this.moveable[i] = spot;
            else {
                ++spot;
                this.moveable[i] = spot;
            }
            ++spot;
        }
    }

With the loops properly set up to skip over the locked spot if it is in one of the other seven queen’s starting position, we now can focus on the looping. This can be a bit confusing as while there are 8 queens, one is locked so we only have 7 counters (0 through 6). We need to loop backwards through these to find the lowest counter that needs to be updated. Remember that for a loop to go to the next element, the loop inside of it must have reached it’s end condition and for that loop to reach the end condition the loop inside of it must have reached it’s end condition and so on until the inner-most loop has reached it’s end condition. If a counter is incremented, but has not reached it’s end condition then we can break out of the updating loop as we know none of the loops above it need to be changed yet.

    nextMove() {
        let pieceToMove = 0;
        for (let i = 6; i >= 0; --i) {
            let nextPos = this.moveable[i] + 1;
            if (nextPos === this.locked)
                ++nextPos;
            if (nextPos < (57+i)) {
                pieceToMove = i;
                this.moveable[i] = nextPos;
                break;
            }
        }

Once we have updated the outer-most loop that have reached their end conditions, all the loops above it would be restarted so we simply loop from the outermost updated loop to the end of the list of loops to set them to their next starting state which would be one greater than the previous counter unless the locked queen happens to be on that tile.

        for (let i = pieceToMove+1; i < 7; ++i) {
            let nextPos = this.moveable[i-1] + 1;
            if (nextPos === this.locked)
                ++nextPos;
            this.moveable[i] = nextPos;
        }
    }

We now have our brute force implementation completed. This can be ran and we can watch the computer solve the game. This might take a while. After watching for a few minutes, we can readily see there is an obvious problem with our initial brute force approach. Most of the time, we are in an obviously invalid state as multiple tiles are on the same row! A quick fix could speed this up but how long will the brute force approach take?

To go through the complete loop, which is not necessary as a solution would be found way before then, we would need each of the loops to complete with the inner loops having to run multiple times. There are 7 variables looping through 57 possible positions on the board so a rough approximation would be 57^7 for 1,954,897,493,193 though because loops are going through progressively smaller counts, we would only have 994,596,970,221 iterations. On today’s hardware, we could probably process this number of moves quickly if we weren’t animating them but that is still a huge number of board positions that need to be processed. If we increase the board size, this grows ridiculously quickly. 

So the next step on improving the solver is simply enforcing a constraint on where the queens can be placed. This will be our next step and will dramatically reduce the number of moves. The source code is available on github https://github.com/BillySpelchan/BlazingPorts but may contain spoilers of future versions as I am going to be updating the repo as I work on the remaining parts of this series whenever I find a bit of spare time.

Queen’s Challenge - part 2 of 6

Animated Solver Framework 

Solving a game tends to be where things get challenging as often any brute-force method is going to require an exceedingly large number of trials to find a solution. That is pretty much the case with the Queen’s Challenge puzzle. More advanced approaches need to be used. For this series, we want to compare different approaches which is easiest if the user can see how the solver is solving the problem so we are going to need an animated solver framework which we will be roughing out today. Next, we will implement a brute force solver. Part 4 covers a smarter version of the solver. This will be followed by quite common approach of a backtracking solver. The final part will cover a more complicated approach using constraints.

We know that there are going to be 4 different solvers so we will want to create a base solver class so the game can simply call methods in this class to get the next step in solving. To simplify the solver, we are going to represent positions on the board as a single number so 0 through 7 would be the top row, 8 through 15 the next row and all the way to the last row. Complicating matters is that we do have one locked queen and seven queens that we can place. This can be set up as a locked variable and an array of moveable queens.

class BaseSolver {

    constructor(game) {

        this.game = game;

        this.locked = game.queens[0].y * 8 + game.queens[0].x;

        this.moveable = [0,1,2,3,4,5,6,7];

    }

While we are not doing anything with it now, the solver is going to need to be able to reset itself and set up the initial position of the queens based on the current position of the locked queen. While this is a bit of a kludge, we will assume that the game’s Queen[0] will be the locked Queen.

    reset() {

// TODO

    }

At this point we came into a bit of a dilemma as I am thinking that placing the queens on the board could be handled by the game when running the solver. Ultimately, since I may want to show additional information about the state of the solver (I don’t know as I am writing this as I am working on the code so this is as close to live coding as my blog can be) I figure the placing of the pieces on the game board will be the responsibility of the solver. 

    placeStepOnBoard() {

        for (let i = 0; i < 7; ++i) {

            let qx = this.moveable[i] % 8;

            let qy = Math.floor(this.moveable[i] / 8);

            this.game.queens[i+1].changePosition(qx,qy);

            this.game.queens[i+1].setVisible(true);

        }

    }

The heart of the solver will be making the next move. This will be where the solver looks at the current state of the solution and advances to the next one. This approach is a bit more complicated than having a solver just to try and solve the problem as with a traditional solution you could simply have nested loops, but this will have to infer the loop state from the positions. By having a separate step function for our solver, however, lets us do the solution in discrete steps which can then be rendered so the user will be able to see the solver working, which is the whole point of this exercise.

    nextMove() {

//TODO

    }

Finally, the user may be impatient with the solver and start a new game or switch to a new solver in which case we will want to stop the solver. This allows the solver to remove any visual aids from the board if we actually have any.

    stopSolver() {

//TODO

    }

}

To implement the solver, we are going to need buttons for starting a solver. These are simple enough to add as it is simply GUI code placed in the game’s constructor. While here we will also set the current solver to null to indicate that there is no solver being used.

        this.solver = null;

        this.solveBruteButton= new SLLTextButton("brute",

            new SLLRectangle(530,200,100,30),

            "Brute force", 3);

        this.solveBruteButton.setClickHandler(this);

        this.addChild(this.solveBruteButton);

The code for handling starting the solver is placed in our buttonClicked method and simply calls a startSolver method that we are going to need to write. This simply shuts down an existing solver before setting the solver to the new solver and calling that solver’s reset method. We are using timeouts for animation instead of animationFrames as 60 fps is way too fast for watching the solver so a lower speed is desired.

   startSolver(solver) {

if (this.solver != null)

this.sover.stopSolver();

        this.solver = solver;

        solver.reset();

        setTimeout(this.nextSolverStep.bind(this), 10);

    }

We need to run the animation until the board is solved (or interrupted, but we will fix that later). This is very simple matter of going through all the queens and seeing if any of them are in conflict with an earlier placed queen.

    isBoardSolved() {

        let solved = true;

        for (let q = 1; q < 8; ++q) {

            let queen = this.queens[q];

            for (let i = 0; i < q; ++i)

               if (this.queens[i].isCoordinateBlocked(queen.x, queen.y))

                   solved = false;

        }

        return solved;

    }

Finally, we have our main animation loop where we draw the board and then check to see if the board is solved. If not, we get the next move and set a timer for the next redraw. 

    nextSolverStep() {

        this.solver.placeStepOnBoard();

        if ( ! this.isBoardSolved()) {

            this.solver.nextMove();

            setTimeout(this.nextSolverStep.bind(this), 250);

        }

        draw();

    }

While this framework is simple enough, we now need to get a solver working properly so that we can see a solution as it is happening. Next post I will look at the most basic – and least useful – of the solvers. Namely using brute force. While it will not be a useful method for solving, it is a good starting point and should let us discover if there are any issues with our framework. I am writing this as I write the code so let’s hope things go smooth and that the article is short enough that I can do some additional cleanup work! 

Queen's Challenge - part 1 the base game

 It's a new year so lets do something different, sort of. I am going to try something a bit different over the next several months. This month I will be going over the creation of the game, which is normal enough. One feature I want to add to the game is a solver. I figured it would be both interesting and informative to go over the techniques for solving the game ranging from brute force to smart brute force to backtrack solving to constraints. Each method would build off the other and would be added to the game.

Whar game am I talking about? Queens challenge is a chess puzzle, though no knowledge of chess is necessary to play. The goal of the game is to arrange 8 Queens on an 8x8 Chess board in such a way that none of them can capture another Queen. Originally this was a Flash game, but I have rewrote the game in JavaScript. The game is on my spelchan.com site with the source code on my repository (link here). 

The game uses my SLL library but could have easily been written from scratch. The game consists of two classes. The Queen class extends SLLImageLayer making it effectively a sprite. The purpose of this class is to hold position information for the Queen. A simple method for determining if a provided board location is in conflict with the Queen is provided. 

class Queen extends SLLImageLayer{
    constructor(x,y,locked) {
        super("queen", QC.playerQueen, QC.QueenClip);
        this.changePosition(x,y);
        this.setLocked(locked);
    }

    changePosition(x,y) {
        this.x = x;
        this.y = y;
        this.moveTo(QC.boardOffsetX+this.x*QC.tileSize,
            QC.boardOffsetY+this.y*QC.tileSize);
    }

    setLocked(b) {
        this.locked = b;
        if (b)
            this.setImage(QC.lockedQueen);
        else
            this.setImage(QC.playerQueen);
    }

    isCoordinateBlocked(x,y) {
        if (this._visible === false)
            return false;
        if ((x === this.x) || (y===this.y))
            return true;
        return (Math.abs(this.x - x) === Math.abs(this.y-y));
    }
}

This is a very easy method as one simply has to check against the list of existing Queen’s to see if any of them are directly horizontal, vertical, or diagonal from the Queen that is being processed. If this happens to be the case, then the queens are in conflict. 

The game then consists of randomly placing the first Queen on the board. We can then let the players add other Queens by clicking on the desired tile on the Chess board. To make things simpler, we create a highlight rectangle that will follow the mouse and will check to see if the tile the player is over is valid. Once eight pieces are on the board, the player has won.

Not very much too the game, but solving the game is a bit tricker. Next month I will adjust the code so that we can use a solver to solve the game. This will be done in a visual way so that it will be possible to see the moves that the computer is trying so that the different methods of solving the game are better emphasised.

Marvel's Avengers

 I was going to start a series on Making Queen's Challenge followed by a series of articles on the techniques for solving that problem but that will wait until next year. It has been a long time since I wrote a game review so decided after a long invigilation session to relax by writing a review for Marvel's Avengers. I also posted this on Steam.

I received Marvel Avenger’s for “free” with the purchase of my laptop so I can easily say that I got my money’s worth out of the game. While I occasionally will play the occasional shooter, I am not really a fan of action oriented games which is why I quickly gave up on  Final Fantasy XV and will likely never bother with the remake of Final Fantasy VII. Perhaps it is my infamiliarity with looter shooters that kept me playing this game despite mediocre reviews. There is a lot wrong with this game, but even though the cons outweigh the pros, I am giving this game a very marginal thumbs up but only because despite all the flaws I am still playing this game and somewhat enjoying it. Perhaps if I played the better loot shooters first or if I didn’t prefer solo gaming my opinion would differ. 

Pros

Marvel. While not as good as the Lego Marvel games, it still lets you be some of your favorite heroes.

Thor. My least favorite Avenger’s character is one of my favorite characters to play so they must be doing something right! 

Good mix of ranged and melee combat. The variety of attacks and booster powers makes combat, even when overwhelmed, fun to play.

Great graphics. 

Great campaign. While it is a bit too PC, the story was not what I was expecting so rather enjoyed the story line. 

Cons

RPG Elements are pointless as the game scales with your level. This also means that poor players can’t over-level in order to reduce the difficult of the game. That said, as the power level is based on your equipment, you may be able to cheat this flaw by putting on low-level equipment then switching in your good equipment once you have started the mission.

Easy isn’t. This could be my lack of reflexes, but more likely it is because the designers made this game for existing loot shooter players so expect a familiarity with that type of game. Hint to designers, if the player is already playing on the easiest level, DON’T PROMPT THEM TO TELL THEM YOU CAN CHANGE THE DIFFICULTY IF THE GAME IS TOO HARD! It would seem to me that most game companies don’t bother testing their games on people who are new to the genre. In the long term this is why genres die out because new players can’t play the games due to entry difficulty and older players get bored of them.

Timing puzzles. If it were up to me, all timing puzzles would be optional! This wasn’t overly bad until you get to the Kate DLC which requires you break a lock then shoot targets on either side of a cell within an exceedingly short time limit. It took me over half an hour to get by the 3 cells locked this way.

Poor navigation. Having a marker tell you that to get to your next objective requiring you to travel through a wall or mountain isn’t very helpful. Waypoints have existed in games for decades now so there is no reason you couldn’t  put a waypoint in the hard to see tunnel so you can find it and not waist time backtracking to find a path around the mountain.

Chimera sequences require you wander around the airship (or anthill) to complete some vaguely specified objective which wouldn’t be bad if the layout wasn’t so awful. Finding the harm room and interrogation room took way too long and were really pointless tasks as the harm room missions are accessed in the war room once you have found it. No clear directions also was frequent during missions. 

Chest nearby? This message came up frequently but most the time I couldn’t find them.

Ms Marvel as main character. Perhaps because I am not familiar with this character. Perhaps because I am old and male so can’t relate to being a fangirl. Escaping the park was by far the worst part of the campaign, which is sad because it is right near the beginning. Once you get other characters the game gets way better, even when you have to use her.

Multiplayer seems repetitive.  Thankfully you can play multiplayer solo by using bots. That said, the missions I went on were very similar to each other and to the campaign sequences. Yay I get to smash more reactors which spawn hoards of enemies!

Bots not good at multiplayer tasks. It might be more fun with other people rather than bots, but as I am poor at these games don’t want to inflict my bad gaming on other players. That said, when you have sequences that require human players spread out, the bots don’t quite seem to understand the objectives meaning when you have to control 3 points on the map things become annoying.

Mobs attacking are harder than boss fights! I get that combat is the point of this game, but this tends to be far too many enemies attacking you at the same time making most combat a test of reflexes rather than on strategy.

Black Widow Boss Fight was exception to above requiring me to exit the campaign and level up outside of the campaign before giving it another go and even then lost another dozen times before I was able to get through this awful fight. Granted, I was also unable to complete the Harm training so could be that I simply can’t use this character properly.

I am sure I missed a few points. 

TLDR: If you like Marvel heroes, this is fun but has a lot of flaws so wait until on sale.