Tic Tac Toe in TypeScript

By Sep 14, 2017

Description:

Here, we program a TIC TAC TOE game in Typescript, using the method of Negamax. This method makes it possible to determine one of the most favorable blows and so to decide on the blow to play.

Preferencesoft

In this article, we implement a Tic Tac Toe program in Typescript using the minimax algorithm. In addition, we explain the principle of the algorithm of the minimax and its variant form Negamax adapted to zero sum games.

Tic Tac Toe Game

Let's quickly remember the rules of the game. Tic Tac Toe is a game for 2 players that plays alternatively in front of a grid of 3x3 boxes. At the beginning of the game the 9 boxes are empty and the player who starts is designated at random and he must choose a symbol: a cross or a round. The other player has no choice and hangs the remaining symbol.

Both participants will play with the same symbol until the end of the game. The 2 players must check a box on the board in turn to try to get 3 identical symbols aligned.

One of the players wins the game when he managed to align 3 of his symbols horizontally, or vertically or on one of the 2 diagonals.

This game does not cause a lot of problems to humans who determine quickly strategies to win or arrive at the draw.

On the other hand, if one wants a player to be a computer, it is not so obvious to find an algorithm of determination of the best blow for such a simple game. Brute force can be used to examine up to 9x8x7x6x5x4x3x2=362880 possible blows. But we should determine the moves that will bring the greatest number of winning issues.

The minimax algorithm chooses recursively moves that maximize earnings of each player.

There are methods with neural networks but we will not consider them in this article.

Other methods are based on the recognition of certain configurations after reducing the problem through symmetry.

Minimax algorithm

Suppose there are two players, Max and Min. If one of the two players win, value + 1 is assigned, if he loses -1 is assigned and 0 in case of draw match.

Max wants to determine for every possible blow, the greatest gain value. But for this it needs to leave in each case Min play. In its interest Min goes in turn to determine for each of the remaining blow its largest gain value, which in fact corresponds to the smallest possible gain value for Max. It will in turn leave Max play in each of the cases to try to minimize the gain of Max. And so on ...

We go down to the terminal blows:

  • we return the value 0 in draw match cases,
  • we return the value 1 in victory cases of one of the two players,
  • we return the value -1 in the cases of defeat of one of the two players.

The Negamax algorithm is a variant of minimax for zero-sum two-player games, allowing to simplify its implementation by using the property: .

As the winnings of the player Max correspond to the losses of the player Min, therefore it is possible to calculate the min of these values by calculating the max of the opposite values.

Tic Tac Toe in Typescript

The game grid is represented in the HTML page by a 3-row and 3-column table:

cell11 cell12 cell13
cell21 cell22 cell23
cell31 cell32 cell33

These rows and columns are numbered from 1 to 3.

To represent the different moves of a game, we use a one-dimensional array of 9 boxes.

To a cell in the grid of line number x (1 ≤ x ≤ 3) and column number y (1 ≤ y ≤ 3) corresponds to a box in the board array at position 3(x-1) + (y-1).

So we get the following correspondence with the cells:

cell11 cell12 cell13 cell21 cell22 cell23 cell31 cell32 cell33

This array board initially contains 0, when all the boxes are empty and then contains the value 1 when the user plays and the value -1 when the computer plays.

We also represent the HTML objects of the grid by a one-row array of HTMLElement

This last array provides access to the cells on the HTML page and changes their properties

tictactoe.htm
<!DOCTYPE html>
<head runat="server">
    <title>Tic Tac Toe</title>
    <script src="tictactoe.js"></script>
<style>
   h1 {
    text-align: center;
    font-family: 'Indie Flower', cursive;
    font-size: 55px;
    color:lightgoldenrodyellow;
}
      div {
  text-align: center;
  margin: 0px auto;
  text-align: center;
  margin: auto;
}
body {
    background-color: #09de1e;
}

.cell {
  width:85px;
  height:85px;
  border: 5px solid #0026ff;
  background: #FFFFFF;
  font-size: 46pt;
  font-family: arial;
  font-weight: bold;
  text-align: center;
  margin: auto;

}

.cell:hover {
  background: #C2DBFC;
  text-align: center;
}
</style>
</head>
<body>
        <h1>Tic Tac Toe</h1>
        <div>
            <table>
                <tr>
                    <td id="cell11" class="cell">&nbsp;</td>
                    <td id="cell12" class="cell">&nbsp;</td>
                    <td id="cell13" class="cell">&nbsp;</td>
                </tr>
                <tr>
                    <td id="cell21" class="cell">&nbsp;</td>
                    <td id="cell22" class="cell">&nbsp;</td>
                    <td id="cell23" class="cell">&nbsp;</td>
                </tr>
                <tr>
                    <td id="cell31" class="cell">&nbsp;</td>
                    <td id="cell32" class="cell">&nbsp;</td>
                    <td id="cell33" class="cell">&nbsp;</td>
                </tr>
            </table>
        </div>
        <br /><br />
        <input id="reset" type="button" value="RESET" />
        <br /><br />
</body>
</html>

tictactoe.ts
class TTT {
    board: number[] = [0, 0, 0, 0, 0, 0, 0, 0, 0];
    table: HTMLElement[];

    computerSymbol: number = -1;
    //1 or -1
    //1="X" and -1="O"
    //computer = O
    gameRunning: boolean = true;

    constructor(t: HTMLElement[]) {
        this.table = t;
        this.board = [0, 0, 0, 0, 0, 0, 0, 0, 0];
    }

    Reset() {
        this.board = [0, 0, 0, 0, 0, 0, 0, 0, 0];
        this.gameRunning = true;
        for (let i = 0; i < 9; i++) {
            this.table[i].style.color = "white";
            this.table[i].innerHTML = "&nbsp;";
        }
    }

    IsFull(): boolean {
        for (let i = 0; i < 9; i++) {
            if (this.board[i] == 0)
                return false;
            }
        return true;
    }

    ClickCell(x: number, y: number) {
        //3*(x-1)+(y-1)
        let p: number = 3 * (x - 1) + (y - 1);
        if (!this.gameRunning) {
            alert("Game over");
        } else {
            if (this.board[p] == this.computerSymbol) {
                alert("The computer protecting this box!");
            }
            else {
                if (this.board[p] == -this.computerSymbol) {
                    alert("already played");
                }
                else {
                    this.table[p].style.color = "#25bfc4";
                    this.table[p].innerHTML = "X";
                    this.board[p] = 1;
                    if (this.win(this.board) == 1) {
                        this.gameRunning = false;
                        alert("You have won!");
                    } else {
                        if (this.IsFull()) {
                            this.gameRunning = false;
                            alert("Draw match");
                        } else {
                            let v = this.minmax(-1, true);
                            this.board[v] = -1;
                            this.table[v].style.color = "#fac95f";
                            this.table[v].innerHTML = "O";
                            if (this.win(this.board) == -1) {
                                this.gameRunning = false;
                                alert("You have lost!");
                            } else {
                                if (this.IsFull()) {
                                    this.gameRunning = false;
                                    alert("Draw match");
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    win(board: number[]): number {
        var b = board[1];
        if (board[0] == b && b == board[2] && b != 0) return b;
        b = board[4];
        if (board[3] == b && b == board[5] && b != 0) return b;
        b = board[7];
        if (board[6] == b && b == board[8] && b != 0) return b;
        b = board[3];
        if (board[0] == b && b == board[6] && b != 0) return b;
        b = board[4];
        if (board[1] == b && b == board[7] && b != 0) return b;
        b = board[5];
        if (board[2] == b && b == board[8] && b != 0) return b;
        b = board[4];
        if (board[0] == b && b == board[8] && b != 0) return b;
        if (board[2] == b && b == board[6] && b != 0) return b;
        return 0;
    }

    minmax(currentPlayer: number, root: boolean): number {
        let winner = this.win(this.board);
        if (winner != 0)
            if (currentPlayer == -1)
                return winner;
            else
                return -winner;
        //possible moves
        let possibleMoves: number[] = [];
        for (let i = 0; i < 9; i++) {
            if (this.board[i] == 0)
                possibleMoves.push(i);
        }
        let n: number = possibleMoves.length;
        if (n == 0)
            return 0;
        let which: number = -1;
        let v: number = 100;
        for (let j = 0; j < n; j++) {
            let move = possibleMoves[j];
            //play
            this.board[move] = currentPlayer;
            var m = -this.minmax(-currentPlayer, false);
            this.board[move] = 0;
            if (m < v) {
                v = m;
                which = move;
            }
        }
        if (root) {
            return (which)
        }
        else
            return (v)
    }
}


window.onload = () => {
    let cell11: HTMLElement = <HTMLElement>document.getElementById("cell11");
    let cell12: HTMLElement = <HTMLElement>document.getElementById("cell12");
    let cell13: HTMLElement = <HTMLElement>document.getElementById("cell13");
    let cell21: HTMLElement = <HTMLElement>document.getElementById("cell21");
    let cell22: HTMLElement = <HTMLElement>document.getElementById("cell22");
    let cell23: HTMLElement = <HTMLElement>document.getElementById("cell23");
    let cell31: HTMLElement = <HTMLElement>document.getElementById("cell31");
    let cell32: HTMLElement = <HTMLElement>document.getElementById("cell32");
    let cell33: HTMLElement = <HTMLElement>document.getElementById("cell33");
    let reset: HTMLButtonElement = <HTMLButtonElement>document.getElementById("reset");

    let ttt: TTT = new TTT([cell11, cell12, cell13, cell21, cell22, cell23, cell31, cell32, cell33]);
    cell11.onclick = (e) => { ttt.ClickCell(1, 1); }
    cell12.onclick = (e) => { ttt.ClickCell(1, 2); }
    cell13.onclick = (e) => { ttt.ClickCell(1, 3); }
    cell21.onclick = (e) => { ttt.ClickCell(2, 1); }
    cell22.onclick = (e) => { ttt.ClickCell(2, 2); }
    cell23.onclick = (e) => { ttt.ClickCell(2, 3); }
    cell31.onclick = (e) => { ttt.ClickCell(3, 1); }
    cell32.onclick = (e) => { ttt.ClickCell(3, 2); }
    cell33.onclick = (e) => { ttt.ClickCell(3, 3); }
    reset.onclick = (e) => { ttt.Reset(); }
}

Run Tic-Tac-Toe

new Version of Tic-Tac-Toe


TypeScript

Categories

Share

Follow


KodFor Privacy Policy