Tuesday, May 17, 2016

Tic-Tac-Toe in Angular 2 and TypeScript

I’ve built a lot of small apps and games over the years, often to either learn a new framework or platform, or to help teach it. It’s always fun to dig up old code and migrate it to new technologies. For example, I took the Silverlight C# code to generate a plasma effect from my Old School app and ported it to JavaScript with optimizations. I also recently built a bifurcation diagram with ReactJs (RxJS) and div tags.

The other day I reviewed some older projects and came across an article I wrote as an introduction to Silverlight. I used a tic-tac-toe game and built the logic to enable a computer opponent.

tictactoe

I realized this would be a perfect project for Angular 2 so I proceeded to make the port. You can play it here to test it out. I did not build it responsive (shame on me, being lazy) so I may refactor it in the future to make it easier to play on phones. Tablets and computers should be fine.

Scaffolding

To create my project I used a combination of cross-platform tools including Visual Studio Code and Node.js. I also used the Angular-CLI for just about everything. The first step is get to a Node.js command prompt, then install the Angular CLI and initialize the project:

npm i angular-cli –g
ng new tic-tac-toe-ng2
cd tic-tac-toe-ng2
ng serve

By now I had a working project that I could navigate to, run unit tests against:

ng test

…and even run an end-to-end set of tests:

ng e2e

Great! Now to start porting the code!

Quotes

The original game had some wonky quotes that would show up in each tile that isn’t clicked yet. It would also give you a different, random quote if you tried to tap on a cell while it was the computer’s turn. We’ll get to the computer strategy in a bit (I built in a random delay for the computer to “think”).

A reusable unit of JavaScript code in Angular 2 is referred to as a “service” and we scaffold it like this:

ng g service quotes

This will generate the service and the specification (tests) for the service. One great feature of Angular is that it addresses testing right out of the box.

I really didn’t have many specifications, other than making sure I get an actual string from the service and that multiple calls randomly return all available quotes .

(Note: For the test, I iterate a large number of times to check the quotes, but technically it’s not a “good” test because you could randomly miss a quote and the test will fail even though the service is doing what it is supposed to).

The service itself just randomly sorts an array each time a quote is requested and returns the first element.

I repeated that pattern for the “bad quotes” (i.e. when you click out of turn) and then turned my attention to individual cells on the tic-tac-toe board.

Cell and Game States

Thinking about the game, I determined there would be exactly three states for a cell to be in:

export enum State {
    None = 0,
    X = 1,
    O = 2
}

Either “not played” or marked with an ‘X’ or an ‘O’. I created an interface for the data of a cell to represent where it is on the grid, the current state, and whether it is part of a winning row.

export interface ICell {
    row: number;
    col: number;
    state: State;
    winningCell: boolean;
}

Finally, the game flow will either allow a turn, or end in a win or a draw.

export enum GameState {
    XTurn = 0,
    OTurn = 1,
    Won = 2,
    Draw = 3
}

With these in place, I then built the component for an individual cell.

The Cell

To scaffold a component I used the following syntax:

ng g component cell

This created a sub-directory with the related files (CSS, HTML, code-behind and test). In the CSS you can see the styles to define the size (sorry, this one isn’t responsive for now, but that can be readily fixed), margins, etc.

Components have their own specifications. For example, one parameter that is input to the cell is the row and column. In the test, we create a test component that wraps the tested component, then verify the data-binding is working correctly (note the bindings in the template should match what is picked up by the component):

The “builder” is defined earlier in the source and spins up the instance of the test controller to host the component. This is all generated for you by the command line interface.

The cell itself takes several inputs, specifically the row, column, state, and whether it is a winning cell.

It also exposes an event when it is tapped. The template uses these to display either a random quote, an ‘X’, an ‘O’, and also color the background if the cell is part of a winning row.

The logic triggered when it is tapped checks to make sure it hasn’t already been set and whether it is a valid turn (the valid turn property is bound, so it can be set for testing or bound to other logic for the running application). If it is not the user’s turn, a random quote is set on the square to react to the tap. 

Another interesting behavior to note is the way the cell reacts to changes.

Components can implement the OnChanges interface that will fire when the model mutates. This is useful for responding to change without setting up individual watches (as was the case in Angular 1.x). Instead of using a timer to update quotes as I did in the old Silverlight app, I decided that I could just update the quotes randomly when changes occur.

The Matrix

“The Matrix is everywhere. It is all around us. Even now, in this very room … it is the world that has been pulled over your eyes to blind you from the truth.” – Morpheus

OK, the tic-tac-toe matrix isn’t quite as interesting. The matrix service is what manages the game state. The state machine for the game allows alternating between turns and ends at a draw or win. It is illustrated like this:

tictacstate

This is captured through the specifications for the matrix service. The service itself builds up a list of “winning rows” to make it easy to determine if a given row is a draw, a winning row, or still has open slots.

Each time the state changes, the logic first checks to see if the game was won and whether the computer or the user won it:

Next, it checks to see if any slots are available. This is the “dumb logic” for a draw. I could have eliminated this code as it was the first pass at the algorithm, but I decided a two phase would be fine to illustrate as the second pass does a more intelligent look “row-by-row”. If it’s not a draw, it switches to the next turn.

The main component binds to the matrix service and uses this to drive the state of the individual cells.

Strategies

To drive the computer’s moves, I created two strategies. The first strategy is a simple one and simply picks a random empty cell for the computer move. Notice it is a simple function that is exported.

For the hard strategy, I devised a simple algorithm. Each row is assigned a point value based on the state of the row. The point values are listed here:

  • Row is a draw (one from each) – 0 points
  • Row is empty – 1 point
  • Row has one of theirs – 10 points
  • Row has one of mine – 50 points
  • Row has two of theirs – 100 points
  • Row has two of mine – 1000 points

This is an aggressive (not defensive) strategy because there are more points assigned to building up a winning row than blocking the opponent’s. Each empty cell is assigned a weight based on the sum of all intersecting rows, and then the highest weighted cell wins. Here is a visualization where the computer is “O”:

tictacstrategy

The top grid shows the row values (first and last columns on the top represent the diagonals) and the bottom grid shows the computed values for the cell. Note the highest score is the cell that will win the game.

The logic is encapsulated in the hard strategy function. The pseudo-code follows:

  1. Create a matrix of cell ranks
  2. Iterate each row. If the cell is occupied, set it’s weight to a negative value.
  3. Sum the count of X and O values for the row.
  4. Update the cell’s weight based on the logic described earlier.
  5. Sort by weight.
  6. Create a short array of the cells with the highest weight (in case multiple cells “tie”)
  7. Pick a cell and populate it.

That’s it – a simple strategy that works well.

Putting it All Together

The main component orchestrates everything. A flag is synchronized with the strategy service to run the selected algorithm, and the matrix is consulted for the first turn. (Note the MatrixService is bootstrapped with the main component so the same copy is available throughout).

On initialization, it is determined whether the component is running with a “slow computer.” This is the default and uses a timeout to emulate time for the computer to decide it’s next move. It makes for more realistic gameplay. When set to false, the statements execute immediately to make it easier for testing.

The remaining methods simply check for the game state and pass it through to properties on the component for data-binding, and advance the state. The user is responsible for tapping a cell to trigger their move. This is handled by the stateChange method:

The template the generates the cells iterates through the grid and binds the cell attributes to each CellComponent:

The updateStats method queries the matrix to determine the game state. If it is the computer's turn, the computerMove method is called. This simply calls the strategy service to make the next move and passes control back to the user. That's pretty much it!

Bonus Opportunity: if you like challenges, the AI in this is not perfect. You can take on a two-part challenge. First, the computer is absolutely beatable when you have the first turn. If you solve it, comment here and let us know the solution! My only hint is that it does not start with placing an X in the middle. Second, once you've done that, is there a better algorithm that can beat the winning strategy?

You can view the entire project (along with projects to install and run it locally) at the tic-tac-toe-ng2 repository. I hope this helps illustrate building applications with Angular 2 and TypeScript using the Angular Command Line interface.

Please share your thoughts and comments below, and if you get bored, play some tic-tac-toe!

Until next time,

No comments:

Post a Comment