DEV Community: Luka

Implementing Routing in React, a Step by Step Approach

Luka — Sun, 09 Jul 2023 21:41:34 +0000

This article follows my thought process of building a routing system for React applications.

To be able to follow along one should have some exposure to building React applications and custom React hooks.

These are our goals:

Have a simple routing system where one can simply read the current route as a string, and also be able to navigate to some other given route.
Make it UX friendly and make it feel natural for usage in a React application.

The first goal alone is actually very simple to accomplish. There already exists a browser native solution: location.href.

console.log(location.href);      // prints out the current URL
location.href = ‘example.com’;   // navigates to `example.com`

The biggest problem with this is when we navigate to a new URL, the browser gets refreshed. It is as if we simply typed the URL in the address bar and pressed enter. Definitely not a good user experience. There is no need to refresh the app if we already have that app loaded and running.

There is a way to make it change only the URL and not refresh the browser. Like this:

history.pushState({}, '', ‘example.com’);

But then we will only change what is written in the address bar, and not really refresh our app to correspond to the URL change. Let’s park this issue for now, we will return to it later.

First, we will define the ideal way somebody would use the routing solution. In today’s React applications it feels natural to implement this with a custom hook. Imagine we have a hook useRouter, and we would like to use it like this:

let [route, setRoute] = useRouter();

console.log(route);     // prints out the current route
setRoute(‘/home’);      // navigates to `/home` on the same origin

Looks very much like the useState hook, doesn’t it? Let’s implement this hook. We will do it step by step.

// router.jsx

import { useState } from "react";

export function useRouter() {
  let [route, setRoute] = useState(location.pathname);
  return [
    route,
    (newRoute) => {
      history.pushState({}, "", newRoute);
      setRoute(newRoute);
    },
  ];
}

This is just our first try. It makes sense to try it now with a simple application that consists of two React components: the main one <App> and the inner one <Pancake>. <Pancake> should be rendered only if we are accessing route /pancake.

// App.jsx

import { useRouter } from "./router.js";
import Pancake from "./Pancake.jsx";

export default function App() {
  let [route, setRoute] = useRouter();

  return (
    <>
      current route: {route}
      <br />
      {route == "/pancake" && <Pancake />}
    </>
  );
}

// Pancake.jsx

import { useRouter } from "./router.js";

export default function Pancake() {
  let [route, setRoute] = useRouter();

  return (
    <>
      <button onClick={(_) => setRoute("/waffle")}>go to /waffle</button>
    </>
  );
}

If we try the app now and we type directly in the address bar the route /pancake we will see exactly what is expected: the button "go to /waffle" will be rendered. Now, if we click on the button, what happens is the route changes to /waffle as expected, but nothing changes on the page. No surprise here, as there is nothing in the state of the <App> component that has changed, so React doesn’t know that it needs to refresh its hierarchy. Even though we are using the same hook useRoute in both <App> and <Pancake>, there are actually just two separate instances of the individual states of those components. But we want them to use the same state. The way to do this in React is with React Context.

We will provide route and setRoute through the context. That means we can change our <App> and <Pancake> components to this:

// App.jsx

import { useContext } from "react";
import { routerContext } from "./router.jsx";
import Pancake from "./Pancake.jsx";

export default function App() {
  let [route, setRoute] = useContext(routerContext);

  return (
    <>
      current route: {route}
      <br />
      {route == "/pancake" && <Pancake />}
    </>
  );
}

// Pancake.jsx

import { useContext } from "react";
import { routerContext } from "./router.jsx";

export default function Pancake() {
  let [route, setRoute] = useContext(routerContext);

  return (
    <>
      <button onClick={(_) => setRoute("/waffle")}>go to /waffle</button>
    </>
  );
}

Obviously, we have to create and expose the routerContext in our router.jsx. Also we need to wrap our app in the <routerContext.Provider> component. First, let’s make a separate component, <Router>, that will contain this provider:

// router.jsx

import { useState, createContext } from "react";

function useRouter() {
  let [route, setRoute] = useState(location.pathname);
  return [
    route,
    (newRoute) => {
      history.pushState({}, "", newRoute);
      setRoute(newRoute);
    },
  ];
}

export const routerContext = createContext();

export default function Router(props) {
  let [route, setRoute] = useRouter();

  return (
    <>
      <routerContext.Provider value={[route, setRoute]}>
        {props.children}
      </routerContext.Provider>
    </>
  );
}

And now simply wrap <App> inside <Router>.

let root = ReactDOM.createRoot(document.getElementById("root"));
root.render(
  <Router>
    <App />
  </Router>
);

If we try the app now, everything works as expected. When we click on the button “go to /waffle”, both the URL in the address bar changes, and also the app refreshes its view but without refreshing the browser page. Great!

Now is the time to make some clean ups in the code. First, one can notice we are not using the useRouter hook outside the router.jsx, hence, there is no need for the export. Also, there is actually no need for this hook to exist anymore, as it is used only once and in the same file. Let us rewrite the file to clean this up.

// router.jsx

import { useState, createContext } from "react";

export const routerContext = createContext();

export default function Router(props) {
  let [route, setR] = useState(location.pathname);

  let setRoute = (newRoute) => {
    history.pushState({}, "", newRoute);
    setR(newRoute);
  };

  return (
    <>
      <routerContext.Provider value={[route, setRoute]}>
        {props.children}
      </routerContext.Provider>
    </>
  );
}

Neat! Now, as suggested in the beginning, we want to use the router throughout the app with the useRouter hook. But, with the current solution, we have to use it with useContext(routerContext). This is a little bit cumbersome. We are building the router solution that can be used as is. A developer who would use it doesn’t need to know that we are implementing all this magic with React Context. Also, we already wrapped the routerContext.Provider in the Router component, so this part is hidden. Let's reintroduce the useRouter hook idea and implement this hook again.

This time, the hook will look very differently than before. It only needs to hide the useContext(routerContext) part in itself, so it should be very simple. We will put that in the router.jsx. Also, we can remove exposing of the routerContext, as we will not need that outside the file anymore.

// router.jsx

import { useState, useContext, createContext } from "react";

const routerContext = createContext();

export function useRouter() {
  return useContext(routerContext);
}

export default function Router(props) {
  let [route, setR] = useState(location.pathname);

  let setRoute = (newRoute) => {
    history.pushState({}, "", newRoute);
    setR(newRoute);
  };

  return (
    <>
      <routerContext.Provider value={[route, setRoute]}>
        {props.children}
      </routerContext.Provider>
    </>
  );
}

// App.jsx

import { useRouter } from "./router.jsx";
import Pancake from "./Pancake.jsx";

export default function App() {
  let [route, setRoute] = useRouter();

  return (
    <>
      current route: {route}
      <br />
      {route == "/pancake" && <Pancake />}
    </>
  );
}

// Pancake.jsx

import { useRouter } from "./router.jsx";

export default function Pancake() {
  let [route, setRoute] = useRouter();

  return (
    <>
      <button onClick={(_) => setRoute("/waffle")}>go to /waffle</button>
    </>
  );
}

We are almost there. There is one more important thing to fix. What happens if somebody uses the back and forward browser buttons? It doesn’t work! The URL changes expectedly, but the page doesn’t refresh. To fix this, we need to add an event listener to this event that will make a navigation using our router. The event is called popstate and fires on the window object. Also, as we will add this event listener, we have to make sure to clean it up if the component dismounts. This is done by creating a return function inside the useEffect hook. Finally, our routing solution becomes this:

// router.jsx

import { useState, useEffect, useContext, createContext } from "react";

const routerContext = createContext();

export function useRouter() {
  return useContext(routerContext);
}

export default function Router(props) {
  let onPopState = (event) => {
    setRoute(location.pathname);
  };

  useEffect((_) => {
    addEventListener("popstate", onPopState);
    return (_) => {
      removeEventListener("popstate", onPopState);
    };
  }, []);

  let [route, setR] = useState(location.pathname);

  let setRoute = (newRoute) => {
    history.pushState({}, "", newRoute);
    setR(newRoute);
  };

  return (
    <>
      <routerContext.Provider value={[route, setRoute]}>
        {props.children}
      </routerContext.Provider>
    </>
  );
}

This is more or less the whole simple routing solution. It is very simple, and there is definitely space for improvements. We can mention few things that could be added if there is a need for it.

First, if somebody is to use a hyperlink with a standard <a> tag, it would obviously do navigation without our router. To overcome this, one would need to provide an onClick listener to the element that would prevent default browser navigation and use our router instead. For example, if we were to use the link instead of the button in our <Pancake>, it would look something like this:

// Pancake.jsx

import { useRouter } from "./router.jsx";

export default function Pancake() {
  let [route, setRoute] = useRouter();

  function onClick(evt) {
    evt.preventDefault();
    setRoute(new URL(evt.currentTarget.href).pathname);
  }

  return (
    <>
      <a href="/waffle" onClick={onClick}>
        go to /waffle
      </a>
    </>
  );
}

If there is a need to use something similar very often, it would be reasonable to create a separate component that wraps the <a> tag with this logic, and provide it as an additional component of our routing system.

Second, sometimes there is a need for a redirect that we don’t want to save in the navigation history. For example, we may want to render the same page whether the user goes to "/home" or to "/". And usually the page would simply navigate from the first route to the second. So, if this redirection was saved in the navigation history, then pressing the browser’s back button wouldn’t do much, it would just try to go to the previous page which would right away redirect back. In this case, we would prefer to call history.replaceState instead of our history.pushState. This option can simply be added as an additional parameter to our setRoute function.

Lastly, one small optimization can be implemented with our solution. Functions onPopState and setRoute don’t need to be redefined every time when a state updates in the <Router> component. If this is really a concern, one can always wrap those functions using the useCallback hook provided by React for this kind of optimizations.

While there are many other possible improvements, I will stop here, as my intention was to share my step-by-step thought process of a very simple routing implementation, instead of providing a full fledged routing system.

Building an Unbeatable Tic-Tac-Toe AI Player

Luka — Mon, 26 Jun 2023 21:27:44 +0000

While there are numerous online sources that cover this topic, I aim to offer an uncommon approach by developing an algorithm for the AI player that closely mimics human thinking.

Let's begin by introducing some notation that will be used throughout the article. The grid consists of 9 cells, each assigned a numbered position as follows:

The center cell is denoted as 4, the corner cells are 0, 2, 6, and 8, and the edge cells are 1, 3, 5, and 7. Although the starting symbol is irrelevant for the algorithm, for the sake of this article, we will assume that X always makes the first move.

In a game played perfectly by both players, it results in a draw. However, when players are not flawless, the one with the best chances of winning is the player capable of creating a fork. A fork occurs when a player reaches a board state where they can create three-in-a-row in two different ways on their next move, making it impossible for the opponent to defend. This is an example situation where X is about to win, regardless of O's move on their current turn.

Enumerating All Board States

This section is not essential for understanding the main subject of this article, which focuses on constructing the AI player. Its purpose is to provide insights into the scale of the problem.

Tic-tac-toe is a relatively simple game, and it is feasible to enumerate all possible board states. One approach is to store the states in a lookup table or a hash map, where each state is associated with the optimal move for the player. For instance, in the following scenario, the best move for X is to play at position 3, thereby blocking O from winning in the next move.

To represent this information in a hash map, we can use a key representing the board state, such as "..o.x.x.o", and the corresponding value representing the best position to play, in this case, 3.

Determining the best move for each board state can even be analyzed manually.

Now, let's explore the feasibility of this approach by calculating the total number of possible board states.

Suppose we have made $n$ moves so far, which implies that there are $⌊n+12⌋\left\lfloor \frac{n+1}{2} \right\rfloor$ X's and $⌊n2⌋\left\lfloor \frac{n}{2} \right\rfloor$ O's on the board. For the $n$ symbols, we can choose $n$ cells out of the total 9 in $(9n)\binom{9}{n}$ ways. Then, we can arrange $⌊n2⌋\left\lfloor \frac{n}{2} \right\rfloor$ O's into the selected cells, resulting in $(n⌊n2⌋)\binom{n}{\left\lfloor \frac{n}{2} \right\rfloor}$ possible arrangements. This gives us a total of

(9n)(n⌊n2⌋)\binom{9}{n}\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}

distinct board configurations with $n$ symbols.

For example, how many board states are there with 5 symbols? Choosing 5 cells out of 9, and then arranging 2 O's into those 5 cells, gives us

(95)(52)=1260\binom{9}{5}\binom{5}{2} = 1260

different board states.

Since there can be any number of symbols between 0 and 9, we have

∑n=09(9n)(n⌊n2⌋)=6046\sum_{n=0}^9\binom{9}{n}\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor} = 6046

different board configurations in total.

However, this is an upper bound, as not all of these states are valid. For instance, consider the following board state included in the above calculation:

This state is clearly invalid because there is no point in continuing the game after one of the players has already won, and it appears that both players have achieved a three-in-a-row.

Furthermore, we can reduce the number of states that need to be stored by excluding rotations and reflections. For example, the following 8 states are equivalent, and knowing the best move for one of them is sufficient to determine the best move for all of them.

Each state belongs to a group of at most 8 equivalent symmetrical states. By considering this into the analysis, the number of states requiring storage can be significantly reduced, nearly by a factor of 8.

Additionally, there is no need to save winning states or states with a full grid of 9 symbols. These are considered end states where the game cannot progress any further.

There are a few more optimization techniques that can further reduce the number of states. By incorporating all of these ideas, the total number of states can be reduced to approximately 600. This number of states makes it manageable even for manual analysis.

Finding the Optimal Strategy

A skilled human player typically follows this approach on each move:

- if there is a winning move, play it
- if there is a move that blocks the opponent's potential win, play it
- if there is a possibility to make a fork, do it
- if there is a possibility to do an attack, do it

This outline serves as the basis for our AI algorithm. However, it doesn't provide a solution for every board state, particularly at the beginning of the game. The plan is to apply this algorithm to every feasible board state and refine it where it falls short.

There is an xkcd comic that visually depicts the optimal play. The representation for player X can be seen here:

The representation for player O is similar but slightly more complex.

The image displays the best moves for all reachable board states. By carefully applying the above algorithm to each board state in the image, removing solvable states, and eliminating duplicates through equivalent rotations and reflections, we are left with only 13 unresolved board states:

It's worth noting that each of these unresolved board states contains a maximum of three symbols. The next step involves analyzing each of them to identify all viable moves. Here is the resulting chart:

The orange symbols indicate the best moves. It is apparent that there are multiple equally good moves for nearly all of these board states. By utilizing this chart and the above algorithm, one can determine the ideal course of action and play a perfect game until the end.

The final step is to enhance the algorithm with additional rules based on this chart, while striving to keep them as straightforward as possible. Let's incorporate these rules. The revised pseudocode is as follows:

- if there is a winning move, play it
- if there is a move that blocks the opponent's potential win, play it
- if number of symbols < 4:
    - if it’s player 1’s turn and edges are empty, take any corner   # red
    - if player 2 has the center:
        - if an edge is taken, take any corner adjacent to it        # purple
        - else take any edge                                         # yellow
    - take the center if available                                   # blue
    - take any corner                                                # green
- if there is a possibility to make a fork, do it
- if there is a possibility to do an attack, do it
- play anything

Note: The additional rules are annotated with colors at the end of lines, corresponding to the board states they address in the following chart. Some of the orange symbols representing the best moves are removed from the chart to align with the rules in the pseudocode.

This revised pseudocode now provides a complete definition for our AI player. It can also be followed by a human player.

Board Representation in Code

A wide range of programming languages can be used for implementation. I have implemented this logic in both Python and JavaScript, and in this article, I will present the Python version.

When implementing this algorithm, it's crucial to decide how to represent the board state. One common approach is to use a matrix (an array of arrays) or a string. However, I have chosen to represent it as a binary number to optimize performance through efficient bit manipulations. While this may not be necessary for such a simple game, it's still a fun exploration.

In this representation, X is player 1, O is player 2, and 0 denotes an empty cell. Each cell can have a value of 0, 1, or 2, requiring only 2 bits to represent. Taking the example board state:

We can assign values as follows:

By ordering these digits, we obtain the binary number that represents this board state: 01 01 00 00 10 01 00 10 00.

In Python, we can directly save this state using 0b numeric literals. To improve readability, Python allows the use of underscores to visually separate digits. Therefore, we can save the above board state as:

board = 0b_01_01_00_00_10_01_00_10_00

Now, let's explore some examples of using bitwise operations on this board state.

To extract the symbol at position p, we can use:

symbol = board>>2*p & 0b11

This operation shifts the board to the right by 2*p bits, placing the desired symbol in the rightmost position, and then extracts those two bits using bitwise AND with 0b11.

To create a new board state after a player makes a move at position 6, we can use:

new_board = board | player<<2*6

Here, the player value is shifted to the left by 2*6 bits and then combined with the board using bitwise OR.

Now, let's also explore counting the number of symbols on the board. This task involves slightly more complexity. Assuming a valid board state, our goal is to count the number of set bits. We can achieve this by implementing the following function:

def count_symbols(board):
    count = 0
    while board:
        board &= board-1
        count += 1
    return count

To understand the logic behind it, let's break down the first iteration of the loop using our previous example.

                board   = 01 01 00 00 10 01 00 10 00
                board-1 = 01 01 00 00 10 01 00 01 11
                ------------------------------------
board = board & board-1 = 01 01 00 00 10 01 00 00 00

By performing the bitwise AND operation between the board and board-1, we effectively remove the rightmost set bit. Continuing this process until we are left with an empty board will result in iterating count times, which corresponds to the number of set bits.

We will use the function count_symbols in our implementation below.

These examples provide insight into the implementation, showcasing the utilization of bitwise operations and the chosen binary representation of the board.

Implementation

Let's gradually construct the main function find_best_move.

def find_best_move(board, player):
    # find winning move
    # find blocking move

    # handle if less than 4 symbols:
    if count_symbols(board) < 4:
        # if it's player 1's turn and edges are empty, take any corner
        # if player 2 has the center:
            # if an edge is taken, take any corner adjacent to it
            # else take any edge
        # take the center if available
        # take any corner
        pass

    # find a fork
    # find an attack
    # play any move

This function accepts the current state of the board and the player who is currently making a move. Its objective is to return a new state of the board.

First, let's create a function that handles playing any move. This function will be placed directly at the bottom of our logic. We will design it to accept a list of permissible positions, which will prove useful later on.

def find_available(board, player, allowed):
    for p in allowed:
        if board & 0b11<<2*p == 0:
            return board | player<<2*p

The purpose of this function is to locate any vacant position from the provided allowed list of cells and return the updated board with the new symbol in place. To execute any move, we simply need to provide the list [0, 1, 2, 3, 4, 5, 6, 7, 8] as allowed positions. For instance, if we wish to play a move in any of the corners, we can provide the list of corner positions as [0, 2, 6, 8].

Now that we have the find_available function ready, let's proceed to implement the logic for when the symbol count is less than 4.

To check if the edges are empty, we use the following code:

if not board & 0b_00_11_00_11_00_11_00_11_00

To determine if player 2 has the center:

if board & 0b_00_00_00_00_10_00_00_00_00

To test whether an edge is already taken and to place the symbol adjacent to that edge, we can achieve this in just two lines of code. Check if any edge in positions 1 and 3 is occupied and play on the corner between them. Otherwise, check edges 5 and 7 and play in corner 8.

if board & 0b_00_00_00_00_00_11_00_11_00: return board | player
if board & 0b_00_11_00_11_00_00_00_00_00: return board | player<<16

Now we have all the components necessary to assemble the part for when there are fewer than 4 symbols on the board.

def find_best_move(board, player):
    # find winning move
    # find blocking move

    # handle if less than 4 symbols:
    if count_symbols(board) < 4:
        # if it's player 1's turn and edges are empty, take any corner:
        if player==1 and not board & 0b_00_11_00_11_00_11_00_11_00:
            return find_available(board, player, [0, 2, 6, 8])

        # if player 2 has the center:
        if board & 0b_00_00_00_00_10_00_00_00_00:
            # take any corner adjacent to a taken edge:
            if board & 0b_00_00_00_00_00_11_00_11_00: return board | player
            if board & 0b_00_11_00_11_00_00_00_00_00: return board | player<<16
            # take any edge:
            return find_available(board, player, [1, 3, 5, 7])

        # take the center if available, or take any corner:
        return find_available(board, player, [4, 0, 2, 6, 8])

    # find a fork
    # find an attack

    # play any move:
    return find_available(board, player, [0, 1, 2, 3, 4, 5, 6, 7, 8])

Let's continue with the logic for finding a winning move. To accomplish this, we will define masks that will be used for checking three-in-a-row combinations. There are 8 masks in total, representing the 8 different possibilities for achieving three-in-a-row.

win_masks = [
    0b_01_01_01_00_00_00_00_00_00,
    0b_00_00_00_01_01_01_00_00_00,
    0b_00_00_00_00_00_00_01_01_01,
    0b_01_00_00_01_00_00_01_00_00,
    0b_00_01_00_00_01_00_00_01_00,
    0b_00_00_01_00_00_01_00_00_01,
    0b_01_00_00_00_01_00_00_00_01,
    0b_00_00_01_00_01_00_01_00_00
]

Now, let's define a function that attempts to find a winning move. If a winning move exists, the function will return the new board state.

def find_winning_move(board, player):
    for mask in win_masks:
        mask *= player
        new_board = board | mask
        if is_valid_board(new_board) and are_successive_boards(board, new_board):
            return new_board

In this code snippet, we iterate through each winning mask. In the case of player 2, we need to adjust the masks by multiplying them by the value 2, effectively shifting the bit mask one place to the left. For each mask, we perform a bitwise OR operation with the board to obtain the new board state. If this new board is considered valid (i.e., no overlapping X's and O's) and if it has exactly one more symbol than the original board, we have found a winning move.

Now, let's discuss the two auxiliary functions: is_valid_board and are_successive_boards.

def is_valid_board(board):
    # check for broken cells (overlapping X and O):
    return not board & board>>1 & 0b_01_01_01_01_01_01_01_01_01

def are_successive_boards(b1, b2):
    b = b1 ^ b2
    return b>0 and not b & b-1   # is not 0 and is power of 2

To explain the check for overlapping cells, let's consider the example of a single cell. A cell can be in one of three valid states: 0b00, 0b01, and 0b10. To check for the only invalid state, 0b11, we can take the state and bitwise AND it with itself shifted one place to the right. If the rightmost bit becomes 1, it indicates that the state is invalid. The left bit is not relevant for this check, so we ensure it is unset by performing a bitwise AND with 0b01. By applying this operation to all cells simultaneously, we can check for overlapping X's and O's on the whole board.

The function are_successive_boards is used to determine if two boards are successive. We calculate their difference using bitwise XOR and check if the result contains only one symbol. This condition effectively means that the board is a number that is a power of 2. For this check to work correctly, both boards need to be valid.

Let’s continue with finding a blocking move. This involves identifying if there exists a winning move for the opponent. We can make use of the find_winning_move function by passing the opponent as a parameter. If a winning move is found, we can simply swap the opponent's winning symbol.

def find_blocking_move(board, player):
    b = find_winning_move(board, 3-player)  # find winning move for the opponent
    if b:
        c = board ^ b                       # get only the last symbol on the board
        c = c>>1 if player==1 else c<<1     # swap the symbol
        return board | c                    # put the symbol back

Now, let's create a function for finding an attack. Finding an attack means identifying a move that leads to a board state that creates an opportunity to make three-in-a-row in the next turn. To find such a move, we iterate over each available cell and, for each resulting board state, check if a winning move can be found for the same player.

def find_attack(board, player):
    for p in range(9):
        if board & 0b11<<2*p: continue  # this cell is taken
        b1 = board | player<<2*p
        if find_winning_move(b1, player):
            return b1

Lastly, we need to address the problem of finding a fork. The solution is slightly more complex than finding an attack. The main difference is that when searching for a winning move, we need to ensure that the move can be confirmed using two different masks. To accomplish this, we unpack the find_winning_move function and make a small adjustment: whenever we find a winning move with one mask, we continue searching for a winning move with different masks. If we find two masks that confirm the same winning move, we have discovered a fork.

def find_fork(board, player):
    fork_board = None

    for p in range(9):
        if board & 0b11<<2*p: continue  # this cell is taken
        b1 = board | player<<2*p

        for mask in win_masks:
            mask *= player
            b2 = b1 | mask
            if is_valid_board(b2) and are_successive_boards(b1, b2):
                # if already found another attack with b1, then this is a fork:
                if fork_board == b1: return b1
                fork_board = b1

To simplify the overall logic, we can combine the find_attack and find_fork functions into a single function called find_best_attack. This function attempts to find a fork first. If no fork is found, it returns the last attack that was discovered. The best_new_board variable stores the most recent attack found.

Let’s rename and modify the function accordingly.

def find_best_attack(board, player):  # find a fork if exists, else find any attack
    best_new_board = None

    for p in range(9):
        if board & 0b11<<2*p: continue  # this cell is taken
        b1 = board | player<<2*p

        for mask in win_masks:
            mask *= player
            b2 = b1 | mask
            if is_valid_board(b2) and are_successive_boards(b1, b2):
                # if already found another attack with b1, then this is a fork:
                if best_new_board == b1: return b1
                best_new_board = b1

    return best_new_board

With these components in place, we now have all the necessary pieces to complete the main function.

def find_best_move(board, player):
    # find winning move:
    if b := find_winning_move(board, player): return b

    # find blocking move:
    if b := find_blocking_move(board, player): return b

    # handle if less than 4 symbols:
    if count_symbols(board) < 4:
        # if it's player 1's turn and edges are empty, take any corner:
        if player==1 and not board & 0b_00_11_00_11_00_11_00_11_00:
            return find_available(board, player, [0, 2, 6, 8])

        # if player 2 has center:
        if board & 0b_00_00_00_00_10_00_00_00_00:
            # take any corner adjacent to a taken edge:
            if board & 0b_00_00_00_00_00_11_00_11_00: return board | player
            if board & 0b_00_11_00_11_00_00_00_00_00: return board | player<<16
            # take any edge:
            return find_available(board, player, [1, 3, 5, 7])

        # take the center if available, or take a corner:
        return find_available(board, player, [4, 0, 2, 6, 8])

    # find a fork, or else any attack:
    if b := find_best_attack(board, player): return b

    # play any move:
    return find_available(board, player, [0, 1, 2, 3, 4, 5, 6, 7, 8])

Sometimes, there are situations where we want the AI to play on any available corner, but the current code always selects the first available corner from the list of allowed positions. To introduce some randomness in the AI's moves when multiple moves are equally good, we can shuffle the list of allowed positions. This way, the AI won't always make the same move.

Implementing the shuffle functionality is fairly simple. We can utilize the random.shuffle() function that shuffles the list in-place.

import random

def shuffle(a):
    random.shuffle(a)
    return a

With the shuffling capability added, unnecessary comments removed, and final adjustments made to our main function, we have completed our AI tic-tac-toe solution.

def find_best_move(board, player):
    if b := find_winning_move(board, player): return b

    if b := find_blocking_move(board, player): return b

    if count_symbols(board) < 4:
        if player==1 and not board & 0xCCCC:           # edges empty
            return find_available(board, player, shuffle([0, 2, 6, 8]))
        if board & 0x200:                              # player 2 has center
            if board & 0x00CC: return board | player
            if board & 0xCC00: return board | player<<16
            return find_available(board, player, shuffle([1, 3, 5, 7]))
        return find_available(board, player, [4] + shuffle([0, 2, 6, 8]))

    if b := find_best_attack(board, player): return b

    return find_available(board, player, shuffle([0, 1, 2, 3, 4, 5, 6, 7, 8]))

Repository

The implementations of this algorithm in both Python and JavaScript, along with the script that helped create SVG images used in this article, can be found in this repository.

Creating a Rollup Plugin to Copy and Watch a File

Luka — Fri, 18 Sep 2020 07:33:01 +0000

A simple web application is what I needed to build. I was going for minimalistic approach: pure JavaScript and HTML, and only for modern browsers. Therefore, I didn't need any compiling/transpiling tools such as Babel. I did need, though, a tool that will bundle up my JavaScript files and a watcher to do that on every change. Rollup happened to be an excellent tool for my needs.

Rollup Configuration

Standard way to set up the build process with Rollup is to write a Rollup configuration file rollup.config.js. Below is a simple config file on which I will base my approach. It instructs Rollup to bundle all JavaScript starting from input main.js into the destination folder dist.

rollup.config.js

export default {
    input: 'main.js',
    output: {
        dir: 'dist',
        format: 'es'
    }
};

Now, one can run Rollup with:

rollup -c -w

Flag -c instructs Rollup to use the config file. Flag -w enables watch mode.

What About HTML?

I have my index.html. It is placed in the same folder as main.js and it contains this line:

<script src="main.js" type="module"></script>

As such, it simply needs to be copied into the build destination folder, and recopied on changes in the watch mode. But Rollup deals only with JavaScript by default, it doesn't know how to handle HTML files. For this, we need to use Rollup plugins.

There are plenty of Rollup plugins that might be helpful in these situations. Some of them create their own index.html file based on some parameters. Some are designed to only copy specific assets. I have tried a few of them and was disappointed with the choices. Many come with a bunch of dependencies and other stuff that I don't need, and all I need it to simply copy a file and recopy it on every change. So, I decided to write my own plugin.

Writing a Rollup Plugin

A Rollup plugin is an object, with property name, and one or more functions that are called build hooks. This is an example of the structure with two hooks, buildStart and generateBundle.

{
    name: 'my-rollup-plugin',
    async buildStart() => {
        // do some stuff
    },
    async generateBundle() => {
        // do some more stuff
    }
}

Hooks are functions which are called at various stages of the build. There are more than 20 build hooks currently defined in the Rollup documentation. We will be using two hooks, namely, buildStart and generateBundle. As their names suggest, the former is called at the beginning of the build process, and the latter at the end right before writing the bundle to disk.

Rollup plugin is usually, if not always, wrapped in a function that returns an object with structure as above. That allows us to provide additional parameters. In our case we need to provide two parameters: input and output file names.

There are two additional functionalities that we need to complete this task. One is to tell Rollup to watch for changes in our file. Another is to save our file to the destination folder. Rollup provides so called plugin context utility functions to help us accomplish those tasks. Those functions are methods of the this object, and they are available in most hooks. We will be using utility function this.addWatchFile to set the file to be watched in watch mode, and this.emitFile to define a file that needs to be included in the build output.

Without further ado, here is the plugin that copies a file to the build output folder, and watches for changes:

function copyAndWatch(fileIn, fileOut) {
    return {
        name: 'copy-and-watch',
        async buildStart() {
            this.addWatchFile(fileIn);
        },
        async generateBundle() {
            this.emitFile({
                type: 'asset',
                fileName: fileOut,
                source: fs.readFileSync(fileIn)
            });
        }
    }
}

One can notice that I am using fs. This is a node module that enables interacting with the file system, and it needs to be imported.

Usually, I would save a plugin in a separate file. But here, for simplicity, I am defining it in rollup.config.js, since it is a very short function, and after all, it's been used only for the rollup configuration.

Finaly, here is how my complete rollup configuration file looks like:

rollup.config.js

import fs from 'fs';

export default {
    input: 'main.js',
    output: {
        dir: 'dist',
        format: 'es'
    },
    plugins: [
        copyAndWatch('index.html', 'index.html')
    ]
};

function copyAndWatch(fileIn, fileOut) {
    return {
        name: 'copy-and-watch',
        async buildStart() {
            this.addWatchFile(fileIn);
        },
        async generateBundle() {
            this.emitFile({
                type: 'asset',
                fileName: fileOut,
                source: fs.readFileSync(fileIn)
            });
        }
    }
}

Two Final Points

1) There are many build hooks that can be used for writing a plugin like this one. Although, many would do the job, it is tricky to select just the right one for the job without knowing their particular meaning in the build process. Rollup documentation can be daunting in this regard. It is easy to find similar plugins on the internet and very often they use the load hook for assigning a file to the watcher. I would argue that the load hook is a poor choice in this situation, as this hook is being called for every imported file. Instead, we'd rather add our file to the watcher only once at the beginning of the build process.

2) I have used the fs module for reading a file from disk. I could have used the same module for writing to disk as well. In fact, many solutions exist with this approach, and they work just fine. But using Rollup's utility function this.emitFile is more suitable as it gives the control of writing the files back to Rollup to finish the build process in its own way.