Collaborative Gomoku Mosaics

Year: 2022 Authors: Robert Bosch; Xiaoyun Gong

Core claim

Discrete optimization can generate visually recognizable Gomoku mosaics that look like plausible ongoing games with balanced stones and no five-in-a-row.

Topics

optimization, mosaic design, Gomoku, image approximation

Domains

discrete optimization, mixed-integer linear programming, quadratic objectives, constraint modeling, mosaic art, visual design, game-piece art, opt art

Methods

target-image gridding, binary variables, sum-of-squared residuals, error diffusion model

Media

Go board, black stones, white stones, grayscale images

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2022 Conference Proceedings

Collaborative Gomoku Mosaics

Robert Bosch and Xiaoyun Gong

Oberlin College, Oberlin, Ohio, USA; rbosch@oberlin.edu

Abstract

We use mathematical optimization techniques to design mosaics that simultaneously resemble well-known target images and can be interpreted as the current state of a game of Gomoku, which is played with Go pieces (black and white stones) on an $n\times n$ Go board.

Introduction

Imagine that two friends come across a gray Go board, plenty of black Go stones, and plenty of white Go stones. The friends don’t know how to play Go, but they do know the rules of Gomoku, a much simpler game. In Gomoku, one player plays black, the other plays white, and the two take turns placing their stones—one at a time—on the board’s empty intersection points. A player wins when they have placed their stones in such a way that they form an unbroken chain (horizontal, vertical, or diagonal) of length five. But here we imagine that the friends decide that instead of playing Gomoku in the traditional competitive fashion, they will invent their own collaborate version of the game. They will use the stones and board to form a recognizable image. When they are done, the gray board will contain an equal number of black stones and white stones, with no unbroken chains (horizontal, vertical, or diagonal) of length greater than four. (They want it to look like the current state of a potentially ongoing Gomoku game.) And if all goes well, when they step back and view their work from a distance, the black stones, the white stones, and the gray board will collectively look like the target image. Figure 1 displays an example in which the target image is based on a public domain publicity photo of Boris Karloff as Frankenstein’s Monster [4].

Figure 1: (a) a $19\times 19$ Gomoku board, (b) a $19\times 19$ target image, and (c) a $19\times 19$ Gomoku mosaic.

The work we describe within this paper was inspired by other game-piece mosaics: the domino mosaics of Ken Knowlton [6], Donald Knuth [7], and Robert Bosch [1], as well as Ken Knowlton’s 999-dice portrait of Albert Einstein (“God doesn’t play dice with the universe”) [5]. To design our collaborative Gomoku mosaics, we use the discrete mathematical optimization techniques popularized by Bosch in his previous research, which is summarized in his book Opt Art: From Mathematical Optimization to Visual Design [1].

Bosch and Gong

A (Relatively) Simple Model: Data, Variables, Constraints, and Objective Function

We start by extracting data from the target image, partitioning its pixels into an $n\times n$ grid of square cells. (In Figure 1, $n=19$ .) For each of these cells, we compute the average grayscale value of the pixels that belong to the cell. We then rescale these averages, letting ${\beta }_{i,j}\in [0,1]$ denote the average brightness (the average grayscale value) of the row- $i$ , column- $j$ cell. If ${\beta }_{i,j}=0$ , then cell $(i,j)$ is completely black. If ${\beta }_{i,j}=1$ , then cell $(i,j)$ is completely white. If 0 < \beta_{i,j} < 1 , then cell $(i,j)$ is some other shade of gray. The larger that ${\beta }_{i,j}$ is, the brighter that cell $(i,j)$ is. (The top left cell of Figure 1(b) appears to be midrange gray, and the bottom right cell is almost white. So it shouldn’t surprise the reader to learn that ${\beta }_{1,1}=0.50$ and ${\beta }_{19,19}=0.94$ .)

To model the placement of the Gomoku stones, we introduce binary variables. We set $x_{i,j,k}=1$ if cell $(i,j)$ is occupied by a stone of shade $k$ and 0 if it is not. Throughout this paper, we use $i$ to index rows, $j$ to index columns, and $k$ to index shades of gray. We use $k=0$ to refer to a black stone, $k=1$ to refer to an invisible gray stone (i.e., an unoccupied cell), and $k=2$ to refer to a white stone. Note that for each cell $(i,j)$ , the linear equation

must hold. Constraint (1) asserts that there are only three possibilities for cell $(i,j)$ . Figure 2 displays these possibilities.

Figure 2: There are three possibilities for cell $(i,j)$ : (a) cell $(i,j)$ is occupied by a black stone $(x_{i,j,0}=1)$ , (b) cell $(i,j)$ is unoccupied $(x_{i,j,1}=1)$ , and (c) cell $(i,j)$ is occupied by a white stone $(x_{i,j,2}=1)$ .

If we reexamine the Gomoku mosaic shown in Figure 1(c), we see that the top left cell is unoccupied and the bottom right cell is occupied by a white stone. In other words, for the Gomoku mosaic shown in Figure 1(c), we have $x_{1,1,1}=1$ and $x_{19,19,2}=1$ . With the average brightness of cell (1,1) being ${\beta }_{1,1}=0.50$ (midrange gray) and the average brightness of cell (19,19) being ${\beta }_{19,19}=0.94$ (nearly white), it makes sense to leave cell (1,1) unoccupied (so that the gray board shows there) and to place a white stone into cell (19,19). To enable ourselves to measure the costs of taking these actions, we need to assign brightness values to the three possibilities shown in Figure 2.

If we let $b_k$ denote the brightness of a stone of shade $k$ and we set $b_0=0$ , $b_1=0.5$ , and $b_2=1$ , then we can write the brightness of cell $(i,j)$ in our Gomoku mosaic as

If, in addition, we let $r_{i,j}$ denote the residual (the error) for cell $(i,j)$ , then we can express this residual as

Collaborative Gomoku Mosaics

And if we want to design a Gomoku mosaic that closely resembles our target image, we should assign values to our $x_{i,j,k}$ stone-placement variables in such a way that we make the length of the vector of the residuals as small as possible. One way to do this is to minimize the sum of the squared residuals. Although this objective function is a quadratic function of the variables, we can easily linearize it. First we note that

$r_{i,j}^2$ $=$ $({\beta }_{i,j}-0.5x_{i,j,1}-x_{i,j,2}{)}^2$ $=$ ${\beta }_{i,j}^2+0.25x_{i,j,1}^2+x_{i,j,2}^2-{\beta }_{i,j}{x}_{i,j,1}-2{\beta }_{i,j}{x}_{i,j,2}+x_{i,j,1}{x}_{i,j,2}.$

Next we see that the first term is a constant, so we leave it alone. Because the second and third terms involve the squares of binary variables and squaring a binary variable does not change it, we replace $x_{i,j,1}^2$ with $x_{i,j,1}$ and $x_{i,j,2}^2$ with $x_{i,j,2}$. The fourth and fifth terms are linear, so we leave them alone too. The final term is the product of two binary variables, but due to equation (1), at most one of the two can equal 1, which implies that the product of the two is 0. Consequently, we can rewrite $r_{i,j}^2$ as

$r_{i,j}^2={\beta }_{i,j}^2+(0.25-{\beta }_{i,j})x_{i,j,1}+(1-2{\beta }_{i,j})x_{i,j,2}.$ (2)

Consequently, if we want to design a Gomoku mosaic that closely resembles an $n\times n$ target image, we can solve the following discrete mathematical optimization problem:

minimize ${\sum }_{i=1}^n{\sum }_{j=1}^n\left({\beta }_{i,j}^2+(0.25-{\beta }_{i,j})x_{i,j,1}+(1-2{\beta }_{i,j})x_{i,j,2}\right)$

subject to $x_{i,j,0}+x_{i,j,1}+x_{i,j,2}=1$ $1\le i,j\le n$

${\sum }_{i=1}^n{\sum }_{j=1}^n{x}_{i,j,0}={\sum }_{i=1}^n{\sum }_{j=1}^n{x}_{i,j,2}$

$x_{i,j,0}+x_{i,j+1,0}+x_{i,j+2,0}+x_{i,j+3,0}+x_{i,j+4,0}\le 4$ $1\le i\le n,1\le j\le n-4$

$x_{i,j,0}+x_{i+1,j,0}+x_{i+2,j,0}+x_{i+3,j,0}+x_{i+4,j,0}\le 4$ $1\le i\le n-4,1\le j\le n$

$x_{i,j,0}+x_{i+1,j+1,0}+x_{i+2,j+2,0}+x_{i+3,j+3,0}+x_{i+4,j+4,0}\le 4$ $1\le i,j\le n-4$

$x_{i+4,j,0}+x_{i+3,j+1,0}+x_{i+2,j+2,0}+x_{i+1,j+3,0}+x_{i,j+4,0}\le 4$ $1\le i,j\le n-4$

$x_{i,j,2}+x_{i,j+1,2}+x_{i,j+2,2}+x_{i,j+3,2}+x_{i,j+4,2}\le 4$ $1\le i\le n,1\le j\le n-4$

$x_{i,j,2}+x_{i+1,j,2}+x_{i+2,j,2}+x_{i+3,j,2}+x_{i+4,j,2}\le 4$ $1\le i\le n-4,1\le j\le n$

$x_{i,j,2}+x_{i+1,j+1,2}+x_{i+2,j+2,2}+x_{i+3,j+3,2}+x_{i+4,j+4,2}\le 4$ $1\le i,j\le n-4$

$x_{i+4,j,2}+x_{i+3,j+1,2}+x_{i+2,j+2,2}+x_{i+1,j+3,2}+x_{i,j+4,2}\le 4$ $1\le i,j\le n-4$

$x_{i,j,k}\in \{0,1\}$ $1\le i,j\le n,0\le k\le 2.$

We have already discussed the objective function and the first set of constraints. The second constraint ensures that the Gomoku mosaic contains an equal number of black and white stones. The next eight sets of constraints guarantee that the Gomoku mosaic has no unbroken black or white chains (horizontal, vertical, or diagonal) of length greater than four. And the final constraints declare that the variables are binary.

Figure 3 displays three examples of $38\times 38$ Gomoku mosaics. We designed them by using the state-of-the-art Gurobi Optimizer [3] to solve the model we presented above. The Frankenstein’s Monster mosaic required 0.52 seconds on a 2019 MacBook Pro, while the Venus mosaic and the Rembrandt mosaic required 1.67 seconds and 0.18 seconds, respectively.

These two-player black-white-and-gray Gomoku mosaics are successful in that they do resemble their respective target images. If we want to obtain higher quality Gomoku mosaics—ones that more closely

Bosch and Gong

Figure 3: Three two-player $38\times 38$ Gomoku mosaics based on (a) Boris Karloff as Frankenstein’s Monster [4], (b) Sandro Botticelli’s Venus [2], and (c) a Rembrandt van Rijn self portrait [8].

resemble their target images—one option is to allow for additional shades of gray. Figure 4 displays three more Gomoku mosaics based on the same target images. When we designed these mosaics, we imagined that the collaborative Gomoku game could be played by four players—one player with white stones, another with light gray stones, a third with dark gray stones, and the fourth with black stones. As before, the board is midrange gray. And here, as before, we set $x_{i,j,k}=1$ if cell $(i,j)$ is occupied by a stone of shade $k$ and 0 if it is not, but here we allow the index $k$ to take on values from 0 to 4, with $k=2$ standing for midrange gray. After making the appropriate modifications to equations (1) and (2) and the constraints that ensure that each player plays the same number of stones, we turned again to the Gurobi Optimizer. Because the modified model has more variables and constraints, it takes longer for the Gurobi Optimizer to solve it. But not too much longer. The four-player Frankenstein’s Monster mosaic required 0.80 seconds, the four-player Venus mosaic required 2.03 seconds, and the four-player Rembrandt mosaic required 1.86 seconds.

An Alternate Objective Function that Incorporates Error Diffusion

As a thought experiment, imagine that our $n\times n$ target image is a light gray square in which each average brightness value ${\beta }_{i,j}$ is 0.75, and suppose that (for the moment) we have decided to do away with the Gomoku constraints (including the constraint that states that the total number of black stones played must equal the total number of white stones played). Note that if we were to leave each cell unoccupied, the sum of the squared residuals would be

Collaborative Gomoku Mosaics

Figure 4: Three four-player $38\times 38$ Gomoku mosaics based on (a) Boris Karloff as Frankenstein’s Monster, (b) Sandro Botticelli’s Venus, and (c) a Rembrandt van Rijn self portrait.

And if we were to place a white stone in each cell, the sum of the squared residuals would be

the same value. And so would a checkerboard pattern of cells containing white stones and cells left unoccupied. But due to its diffusion of the errors, this checkerboard pattern would look better to the eye—more like the light gray target image—than the “all unoccupied” or “all white” solutions.

Our alternate model incorporates error diffusion by using an alternate objective function, one that is a weighted sum of the original sum-of-squared-residuals objective function and a sum-of-squared-sum-residuals objective function (the error diffusion term). For each cell $(i,j)$ with $1\le i,j\le n-1$ we define cell $(i,j)$ ‘s sum residual as follows:

For any nonnegative scalar $w$ , we can minimize

instead of the original sum-of-squared-residuals objective function. Note that the larger the value of $w$ we use, the greater the weight we place on the original objective function term. For the six Gomoku mosaics displayed in Figure 5, we used $w=5$ .

Linearizing the alternate objective function requires that we introduce additional binary variables (and additional constraints to link them to the stone-placement variables), but the resulting models are still tractable with the Gurobi Optimizer. The two-player Frankenstein’s Monster mosaic required 17.70 seconds, the two-player Venus mosaic required 6.9 seconds, and the two-player Rembrandt mosaic required 12.48 seconds. The

Bosch and Gong

Figure 5: Six $38\times 38$ Gomoku mosaics designed with the alternate (error diffusion) model.

four-player Frankenstein’s Monster mosaic required 73.13 seconds, the four-player Venus mosaic required 248.90 seconds, and the four-player Rembrandt mosaic required 69.66 seconds.

To our eyes, the mosaics produced with the alternate (error diffusion) model are more appealing, particularly when viewed from a distance. We invite readers to compare the mosaics in Figure 5 to those in Figures 3 and 4. We contend that the Figure 5 mosaics look less posterized, particularly the four-player ones.

References

[1] Robert Bosch. Opt Art: From Mathematical Optimization to Visual Design. Princeton University Press, Princeton, 2019. [2] Sandro Botticelli. The Birth of Venus, c. 1485-1486. Tempera. Uffizi Gallery, Florence. [3] Gurobi optimization. http://www.gurobi.com/products/gurobi-optimizer [4] Boris Karloff as Frankenstein’s Monster. https://commons.wikimedia.org/wiki/File:Frankenstein%27s_monster_(Boris_Karloff).jpg [5] Ken Knowlton. Albert Einstein, portrait in dice, 1999. 999 dice. Collection of Al Seckel. https://www.knowltonmosaics.com/pages/AEdice.htm [6] Ken Knowlton. Knowlton mosaics. https://www.knowltonmosaics.com/index.htm [7] Donald E.. Knuth. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM Press, 1993. [8] Rembrandt van Rijn. Self-Portrait with Two Circles, c. 1665-1669. Oil on canvas. Kenwood House, London.