Hamiltonian Maker-Breaker games on small graphs

arXiv:1708.07579v2 [math.CO] 11 Sep 2017

Miloš Stojaković

∗

Nikola Trkulja

∗

Abstract
We look at the unbiased Maker-Breaker Hamiltonicity game played on the edge set
of a complete graph Kn , where Maker’s goal is to claim a Hamiltonian cycle. First, we
prove that, independent of who starts, Maker can win the game for n = 8 and n = 9.
Then we use an inductive argument to show that, independent of who starts, Maker
can win the game if and only if n ≥ 8. This, in particular, resolves in the affirmative
the long-standing conjecture of Papaioannou from [11].
We also study two standard positional games related to Hamiltonicity game. For
Hamiltonian Path game, we show that Maker can claim a Hamiltonian path if and only
if n ≥ 5, independent of who starts. Next, we look at Fixed Hamiltonian Path game,
where the goal of Maker is to claim a Hamiltonian path between two predetermined
vertices. We prove that if Maker starts the game, he wins if and only if n ≥ 7, and
if Breaker starts, Maker wins if and only if n ≥ 8. Using this result, we are able to
improve the previously best upper bound on the smallest number of edges a graph on
n vertices can have, knowing that Maker can win the Maker-Breaker Hamiltonicity
game played on its edges.
To resolve the outcomes of the mentioned games on small (finite) boards, we devise
algorithms for efficiently searching game trees and then obtain our results with the
help of a computer.

1

Introduction

A positional game is a hypergraph (X, F), where X is a ﬁnite set representing the board
of the game, and F ⊆ 2X is a family of sets that we call winning sets. In Maker-Breaker
positional games, the players are called Maker and Breaker. In the course of the game,
Maker and Breaker alternately claim unclaimed elements of the board X, one element at a
time, until all of the elements are claimed. Maker wins the game if he claims all elements
of a winning set, while Breaker wins if he claims an element in every winning set. Each
game can be observed in two variants, depending on which player is to play ﬁrst.
The positional games we intend to study are played on graphs, and in particular, on the
edge set of a complete graph Kn . Our prime interest lies with Hamiltonicity game HAMn ,
where the winning sets are the edge sets of all Hamiltonian cycles in Kn . The game was
ﬁrst introduced by Chvátal and Erdős in [1], and since then it has been one of the most
studied positional games on graphs, see [4, 6]. It was shown in [1] that Maker has a
winning strategy for all suﬃciently large n. Papaioannou [11] later proved that Maker
wins the game for all n ≥ 600, and at the same time conjectured that the smallest n for
∗

Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Serbia.
Partly supported by Ministry of Education and Science, Republic of Serbia, and Provincial Secretariat for
Science, Province of Vojvodina. {milos.stojakovic, nikola.trkulja}@dmi.uns.ac.rs

1

which Maker can win is 8. Hefetz and Stich [5] further improved the upper bound by
showing that Maker wins for all n ≥ 29. We note that these statements hold under the
assumption that Maker is the ﬁrst to play.
In the present paper, we determine the outcome of Hamiltonicity game for every value of
n, and for each of the players starting the game. In particular, this resolves the mentioned
long-standing conjecture of Papaioannou in the aﬃrmative.
Theorem 1. In the Maker-Breaker HAMn game on E(Kn ), Maker, as first or second
player, wins if and only if n ≥ 8.
Next, we look at two games where Maker’s goal is to claim a Hamiltonian path. In
Hamiltonian Path game HP n , ﬁrst introduced in [11], the winning sets are the edge sets
of all Hamiltonian paths in Kn . We are able to show the following.
Theorem 2. In the Maker-Breaker Hamiltonian Path game HP n on E(Kn ), Maker, as
first or second player, wins if and only if n ≥ 5.
This theorem is a strengthening of Papaioannou’s result from [11] where he proved that
Maker, as ﬁrst player, can win HP n if and only if n ≥ 5.
In Fixed Hamiltonian Path game FHP n , the goal of Maker is to claim a Hamiltonian path
between two ﬁxed (predetermined) vertices, u, v ∈ V (Kn ). Even though in the literature
this game does not draw as much interest as HAMn and HP n , it has appeared as an
auxiliary game when studying some other games on graphs, see e.g. [2].
Theorem 3. In the Maker-Breaker Fixed Hamiltonian Path game FHP n on E(Kn ),
Maker, as first player, wins if and only if n ≥ 7, and as second player he wins if and
only if n ≥ 8.
Note that in the game FHP n the edge between the ﬁxed vertices u and v actually does
not participate in any winning set, so right away we obtain the same result for the game
played on E(Kn ) \ {(u, v)}.
Here we also want to mention two other standard positional games, Connectivity and
Perfect Matching, where Maker’s goal is to claim, respectively, a spanning tree and a
perfect matching. For both of these games it is straightforward to determine the outcome
for every size of the board. Maker wins the Connectivity game as ﬁrst player for every n,
and as second player if and only if n ≥ 4. In Perfect Matching game, where n is even,
Maker can win as ﬁrst or second when n is at least 6. On top of that, he wins also for
n = 2 when he plays ﬁrst.
Let us note that even though answering the question of who wins a game on a small board
(with n ﬁxed) is a ﬁnite problem, it still may have a greater scientiﬁc impact for several
reasons. First of all, the approaches we use to resolve standard positional games when n
is large often do not apply for small n, and in that case in order to determine the outcome
we need to develop new methods. As we saw, resolving the “small cases” is straightforward
for some games, but not for all.
Also, standard positional games, like Hamiltonicity, Hamiltonian Path, Connectivity, etc.
are often used as auxiliary games when studying other positional games on graphs. Sometimes these auxiliary games have boards of ﬁxed size, and knowing their outcome is essential
for completing the analysis. An example of that can be found in [3], where one of the problems tackled was to estimate the smallest number of edges m̂(n) a graph on n vertices can
2

have, knowing that Maker as ﬁrst player can win the Maker-Breaker Hamiltonicity game
played on its edges. It was proved in [3] that 2.5n ≤ m̂(n) ≤ 21n, for all n ≥ 1600. We
show how to apply our results about Hamiltonicity game in Theorem 1 and Fixed Hamiltonian Path game in Theorem 3 to improve this upper bound, eventually obtaining the
following.
Theorem 4. For n ≥ 336, we have m̂(n) ≤ 4n.
Positional games are combinatorial games (sequential two player games with perfect information and no randomness involved), and it is well known (see, e.g., [12]) that we can ﬁnd
out which of the players has a strategy to win by simply traversing the whole game tree of
the game. But this fact alone is of limited practical use, knowing that already for games
on relatively small boards the game trees are way too big (they are exponentially large in
the size of the game board) to be completely
 traversed by acomputer. In particular, if the
board of the game is E(Kn ), its size is n2 , so there are n2 ! diﬀerent game plays.

Often there is no need to search through the whole game tree, as some moves are “analogue”
to the others, we may arrive to the same game position more than once, and on top of that
some game positions are “similar” to the others. In Section 5 we devise a sophisticated set
of algorithms that formalizes and exploits these “similarities” as part of the optimization
of the brute force search algorithm. This enables us to write a computer program that
eﬃciently calculates the outcome of all three mentioned games for enough initial values of
n to inductively determine the outcome of the game for every n.

When implementing the algorithms we aimed at doing it in a generic way to make our
code easily adaptable for other positional games on graphs. Even though some algorithms
are tailored to ﬁt the particularities of the games we analyzed, most of them are generally
applicable for determining the outcome of positional games on graphs with the help of
a computer. Having that in mind, our software can be seen as a general framework for
computer based attacks on positional games.

1.1

Preliminaries and organization

Our graph-theoretic notation is standard and follows the one from [16]. In particular, we
use the following. For a graph G, let V (G) denote its set of vertices and E(G) its set of
edges, where v(G) = |V (G)| and e(G) = |E(G)|. For a set A ⊆ V (G), let G[A] denote the
subgraph of G induced on the vertex set A and let EG (A) denote the set of edges of G
with both endpoints in A.
Results presented in this paper rely on the following statement, see e.g. [4].
Theorem 5. If Maker (or Breaker) has a winning strategy in some positional game as
second player, then he also has a winning strategy if he starts the game.
If a Maker-Breaker game played on edges of a graph is in progress, Maker’s (respectively,
Breaker’s) vertex degree of a vertex v, denoted by dM (v) (respectively, dB (v)), is the
number of edges incident to v that are claimed by Maker (respectively, Breaker). Maker’s
edge degree of an edge e = (u, v), denoted by edM (e), is deﬁned to be edM (e) := dM (u) +
dM (v), and Breaker’s edge degree is edB (e) := dB (u) + dB (v).
The rest of the paper is organized as follows. In Section 2 we prove Theorem 1, in Section 3 we prove Theorem 2 and in Section 4 we prove Theorem 3. Section 5 contains the
3

description of the algorithms and optimization methods used in our computer programs,
as well as the results we obtain with their help. In Section 6 we show how our results can
be applied in solving other problems in theory of positional games, by proving Theorem 4.
Finally, in Section 7 we give some open problems and ideas for future work.

2

Hamiltonicity game

The following lemma lies in the foundation of our proof of Theorem 1.
Lemma 6. Independent of who starts the game HAMn , Breaker wins for n ∈ {4, 5, 6, 7},
and Maker wins for n = 8 and n = 9.
We prove this result with the help of a computer. Description of the approach used is
postponed to Section 5.
The previous result gives us a ﬁrm induction base for proving that Maker can win HAMn
for all n ≥ 8. We note that Papaioannou already proved the induction step of size 2
for Maker as ﬁrst player, which can be paired up with our Lemma 6 to resolve the case
when Maker is ﬁrst. Inspired by his work, in the following lemma we prove the same
induction step for Maker playing as second player, which eventually completes the proof
of Theorem 1.
Lemma 7. If Maker, as second player, wins HAMn , he can also win HAMn+2 as second
player.
Proof. Suppose that Maker, as second player, has a strategy to win HAMn . We will
present Maker’s winning strategy for HAMn+2 .
At the beginning of the game, Breaker will claim some edge (u, v) and Maker’s response
will be to claim an edge m = (v, w) for some w. Let V1 := V (Kn+2 ) \ {v, w}. We can
now partition the set of all unclaimed edges into two sets, the ﬁrst set being E1 = E(V1 )
and the second one E2 = E(Kn+2 ) \ (E1 ∪ {m, (u, v)}). These edge sets are shown in the
Figure 1.
u
v
m

E1

E2
w

Figure 1: Game board, with the partition into two sets.
From this point on, Maker will try to respond to every move of Breaker by claiming the
edge in the same edge set as Breaker e.g. whenever Breaker claims an edge in Ei Maker will
also try to claim an edge from Ei , i = 1, 2. If this is not possible, he will claim an arbitrary
4

edge in the other set. It is generally true that such “extra” edges can be “forgotten”, i.e. if
Maker can accomplish something in the other set without the extra edge, he will still
manage to do it with the extra edge, see e.g. [4].
Maker will play in E1 using his winning strategy for HAMn , meaning that by the time
all edges in E1 are claimed he will fully occupy some n-cycle Hn in E1 .
When playing in E2 Maker’s goal is to make sure that by the time all the edges are claimed
(in both E1 and E2 ) he claimed a Hamiltonian cycle. This Hamiltonian cycle will be an
extension of Hn to a cycle on two more vertices, now also containing the edge m. More
precisely, in order to extend the cycle Hn = (x1 , x2 , . . . , xn , x1 ), Maker wants to claim
edges (xi , y1 ), (xi+1 , y2 ) ∈ E2 , such that the edge (xi , xi+1 ) ∈ Hn and (y1 , y2 ) = m. That
way, Maker would claim a Hamiltonian cycle Hn+2 = (x1 , . . . , xi , y1 , y2 , xi+1 , . . . , xn , x1 ),
as shown in Figure 2.
xi−2
x2

xi−1

x1

xi

Hn+2
y1
m

Hn
xi+1

xn

y2

xi+2
xn−1
xi+3
Figure 2: Extension of Hn to Hn+2 .
During the game, if for a vertex x ∈ V1 both edges (x, v) and (x, w) are claimed by Maker
(Breaker), we say the vertex x is isolated by Maker (Breaker). If one of the edges (x, v)
and (x, w) is claimed by Maker (Breaker) and the other one is unclaimed, we say the the
vertex x is half isolated by Maker (Breaker). Finally, if both edges (x, v) and (x, w) are
unclaimed, we say that the vertex x is free. When all the edges are claimed, we observe
the following two situations.
Situation 1: Breaker isolated at most one vertex, and Maker claimed an edge in E2
incident to each of vertices v and w.
Situation 2: Breaker isolated two vertices, Maker has one isolated vertex a, and Maker
claimed an edge from E2 \ {(a, v), (a, w)} incident to each of vertices v and w.
First, let us prove that in each of the two above mentioned situations Maker created
a Hamiltonian cycle and thus won the game. We can apply simple labeling procedure,
assigning a label set to each vertex x ∈ Hn . This set contains 0 if and only if edge (x, v)
is claimed by Maker and 1 if and only if edge (x, w) is claimed by Maker.
In Situation 1, since Maker claimed an edge in E2 incident to each of vertices v and w, at
least one vertex is labeled with 0, and at least one vertex is labeled with 1. Also, there
is at most one vertex with empty label set, so in every Hamiltonian cycle Hn there must
exist two adjacent vertices xi and xi+1 containing labels 0 and 1, respectively. Maker will
then use these vertices xi and xi+1 to extend the cycle Hn .
5

In Situation 2 there is a vertex a with label set {0, 1}. If this vertex is adjacent to some
vertex x whose label set is not empty, Maker can extend the cycle Hn using a and x.
Otherwise, if vertex a is adjacent to vertices whose label set is empty (two vertices isolated
by Breaker), then Maker will be able to extend Hn for the same reasons as in Situation 1,
since he claimed an edge from E2 \ {(a, v), (a, w)} incident to each of vertices v and w.
Next, we are going to give a strategy for Maker that will enable him to always end up in
one of these two situations.
Maker’s strategy on E2 . In each move, Maker will apply the ﬁrst applicable rule in
the following list:
1. If there is only one free vertex x ∈ V1 left, and Maker has not claimed any edges
incident to a vertex y ∈ {v, w}, he claims the edge (x, y).
2. If there exists a vertex half isolated by Breaker, Maker picks an arbitrarily half
isolated vertex x and claims the other edge incident to x.
3. If there exists a free vertex, Maker picks an arbitrarily free vertex and claims one
of its free edges. Of the two edges, he prefers the edge incident with the vertex in
{v, w} incident with less edges claimed by Maker (if such vertex exists).
4. Maker claims a free edge incident to a vertex half isolated by Maker. Of all such
edges, he prefers edges incident with the vertex in {v, w} incident with less edges
claimed by Maker (if such vertex exists), breaking ties arbitrarily.
As any free edge is incident either with a vertex half isolated by Breaker, or a free vertex,
or a vertex half isolated by Maker, this is a valid strategy.
Initially, Breaker has claimed one edge, the edge (u, v). For his ﬁrst move in E2 he essentially has only three diﬀerent choices, shown in Figure 3 (along with the move of Maker
that will follow in each of the cases).
v
w

u
B
M

x i1
B

xin−1
...

(a) Breaker claims (w, xi1 ),
Maker claims (w, u).

v
w

u
B
M

x i1
B

xin−1
...

(b) Breaker claims (v, xi1 ),
Maker claims (w, u).

v
w

u
B
B

x i1
M

xin−1
...

(c) Breaker claims (u, w),
Maker claims (w, xi1 ).

Figure 3: Three options for Breaker’s ﬁrst move in E2 followed by Maker’s response, shown
in the form of incidence matrix.
Now, let us analyze each of the three cases from Figure 3 individually.
Case (a): In this case, Breaker ﬁrst has an option to isolate a vertex xi1 . If he indeed does
so, Maker will apply Rule 3 and claim an edge incident to a vertex v, otherwise Maker will
apply Rule 2 and claim an edge incident to v. When Breaker isolates a vertex, Maker will
apply Rule 2 in the remainder of the game to prevent Breaker from isolating more vertices.
The proposed strategy thus inevitably puts Maker in Situation 1.

6

Case (b): Again, Breaker can start by isolating a vertex xi1 which inevitably puts Maker
in Situation 1 as this is analogous to Case (a). Otherwise, Maker will wait (by applying
Rule 2) for Breaker to isolate some vertex, until there is only one free vertex left. If Breaker
isolates a vertex during this period of the game Maker will apply Rule 3 claiming an edge
incident to v and he will spend the remainder of the game applying Rule 2 in order to
prevent Breaker from isolating more vertices. It can happen that Breaker does not isolate
any vertex by the time there is only one free vertex left, in which case Maker will end the
game by applying the Rule 1 as shown in Figure 4. Therefore, Maker will inevitably ﬁnd
himself in Situation 1.
v
w

u
B
M

x i1
B
M

x i2
B
M

...

xin−4
B
M

xin−3
B

xin−2
B

xin−1
M

Figure 4: Breaker can play so that Rule 1 is applied
Case (c): In this case we will need to further analyze each of the three possible Breaker’s
moves. Breaker can either claim an edge incident to the only vertex half isolated by Maker,
or for some free vertex x ∈ V1 he can claim (x, w) or (x, v). These three possibilities are
shown in Figure 5 (along with the move of Maker that will follow in each of the cases).
v
w

u
B
B

x i1
B
M

x i2
M

...

(i) Breaker claims (v, xi1 ),
Maker claims (v, xi2 ).

v
w

u
B
B

x i1
M

x i2
M
B

...

(ii) Breaker claims (w, xi2 ),
Maker claims (v, xi2 ).

v
w

u
B
B

x i1
M

x i2
B
M

...

(iii) Breaker claims (v, xi2 ),
Maker claims (w, xi2 ).

Figure 5: Further analysis of Case (c) from Figure 3.
In cases (i) and (ii), which are essentially the same, Maker claimed an edge incident to
each of vertices v and w while Breaker already isolated a vertex u. Maker will continue the
game with only goal to prevent Breaker from isolating more vertices, by applying Rule 2
whenever it is possible, and hence the game will eventually end up in Situation 1.
In the third case we will ﬁrst analyse the game until there is only one free vertex left.
Maker is again focused on preventing the Breaker from isolating a vertex by applying
Rule 2 whenever possible. If during this period of the game Maker claims some edge
incident to v, Rule 1 will not be applied, and the game will ﬁnish in Situation 1. If it
happens that Rule 1 needs to be applied, Maker will claim an edge (v, xin−1 ), where xin−1
is the last free vertex. Depending if Breaker now isolates a vertex xin−2 or not, the game
can end up in diﬀerent situations. If Breaker does not isolate xin−2 the game ends in
Situation 1. Otherwise, after vertex xin−2 is isolated by Breaker, Maker isolates xi1 and
the game ends in Situation 2.
Hence, Maker can always create one of the two winning situations.

7

3

Hamiltonian path game

In order to complete the proof of Theorem 2 we used our computer program to obtain
following result.
Lemma 8. Independent of who starts the game HP n , Breaker wins for n = 4, and Maker
wins for n ∈ {5, 6, 7}.
Description of the proof and the approach used is postponed to Section 5.
With the help of the previous lemma and Theorem 1, the proof of Theorem 2 is straightforward.
Proof of Theorem 2. It is easy to see that Maker’s win in Hamiltonicity game implies
Maker’s win in Hamiltonian path game since each Hamiltonian cycle contains a Hamiltonian path. This means that Theorem 1 also tells us that Maker can win HP n for all n ≥ 8
as second player. When we combine this with the result from Lemma 8 proof of Theorem 2
is complete.

4

Fixed Hamiltonian Path game

The following lemma will cover several ﬁnite cases in the proof of Theorem 3.
Lemma 9. When Maker starts the game FHP n , Breaker wins for n ∈ {4, 5, 6}, and Maker
wins for n ∈ {7, 8, 9}.
When Breaker is the one who starts, he wins for n ∈ {4, 5, 6, 7}, while Maker wins for
n ∈ {8, 9}.
We prove this result with the help of a computer. Description of the approach used is
postponed to the following section.
It remains to determine the outcome of the game FHP n for larger values of n. We will not
perform an induction step, but rather rely on our knowledge of the outcome of HAMn .
Combining the following result with Theorem 1, along with Lemma 9 that covers the few
initial cases, we readily prove Theorem 3.
Lemma 10. If Maker, as second player, wins HAMn , he can also win FHP n+2 as second
player.
Proof. Suppose that Maker, as second player, has a strategy to win HAMn . We will
present Maker’s winning strategy for FHP n+2 , with two ﬁxed vertices u and v.
As we already noted, the edge e = (u, v) is not interesting to either of the players since it
is not contained in any of the winning sets. Let V1 := V (Kn+2 ) \ {u, v}. We can partition
the set of all unclaimed edges into two sets, the ﬁrst set being E1 = E(V1 ) and the second
one E2 = E(Kn+2 ) \ (E1 ∪ {e}).
Now the goal of Maker is exactly the same as in the proof of Lemma 7 – he wants to
build an n-cycle on E1 , and he wants to play on E2 to connect vertices u and v to two
neighboring vertices of that n-cycle. As the structure of E1 and E2 here is exactly the
same, with exception of E2 having one more unclaimed edge (which is only beneﬁcial for
Maker), he can follow the same strategy as in the proof of Lemma 7 and win the game.
8

5

Algorithmic analysis

In this section we present the techniques and approaches used in our computer program
to solve games HAMn , HP n and FHP n when game boards are relatively small, as well
as some of the major challenges we encountered during the process.
Our program is available at http://people.dmi.uns.ac.rs/~nikola.trkulja/ham.html,
where one can ﬁnd all the information on how to run and use it, along with the source
code.

5.1

Traversing the game tree

As we already noted, in order to determine the winner of a particular game, we need
to completely traverse the game three, which essentially comes down to simulation of all
possible plays. This means that in each round we need to explore all valid moves a player
can play. To achieve this we used the following algorithm which represents an adaptation
of the standard and well-known game theoretic algorithm – Minimax [12].
Algorithm 1
Play(G, P )
1 winner = nil
2 for i = 1 to G.freeEdges.size
3
DoMove(G.freeEdges[i ], G, P )
4
if PlayerWins(G, P )
5
winner = P
6
else
7
winner = Play(G, P.otherPlayer )
8
RevertMove(G.freeEdges[i ], G, P )
9
if winner == P
10
return P
11 return P.otherPlayer

Main procedure of our algorithm is procedure Play, in charge of recursively exploring the
whole game subtree starting from the given tree node (containing the current game board
G, and the identity of the player P whose turn it is). The value returned by procedure
Play corresponds to the player winning the game on board G, when player P moves ﬁrst.
As the name suggests, procedures DoMove(e, G, P ) and RevertMove(e, G, P ) are used
to mark and unmark, respectively, the edge e as claimed by player P on board G.
The winner detection is an essential part of the algorithm, done by procedure PlayerWins.
Every time the winner is not immediately detected by procedure PlayerWins, we continue recursively exploring the game tree. The algorithm stops processing the remaining
possible moves for current player P as soon there is a move which guaranties the win. On
the other hand, if it turns out that there is no such move, we know that the other player
wins the game.

9

5.2

Isomorphism pruning

Basic version of the algorithm we just described can be improved so that the same game
subtrees are not explored multiple times. This is where transposition table [10] jumps into
picture. Straightforward application of transposition table would be to store the winner for
each game tree node, and then use these values to skip processing identical nodes. But the
exponential size of the game tree renders such solution impossible because it would require
huge amounts of computer memory. Much more eﬃcient way of handling this situation is
to recognize the isomorphic nodes of the game tree. For this task we implemented Brendan
McKay’s canonical labeling algorithm [7]. Canonical labeling of a graph is deﬁned in the
following way.
Definition 11. Canonical labeling is a function C mapping graphs to graphs, such that
every graph G1 is isomorphic to C(G1 ), and for every graph G2 isomorphic with G1 we
have C(G2 ) = C(G1 ).
In other words, canonical labeling gives a unique representative for each class of isomorphic
graphs, and with McKay’s algorithm we can deﬁne and compute this graph in an eﬃcient
manner. That enables us to prune the game tree signiﬁcantly, as we can store the winner
only for canonical labelings.
5.2.1

Edge colored graphs

When a Maker-Breaker game is played on the edge set of a graph, the situation on the
game board can be seen as a 3-coloring of the edges, as each edge is either unclaimed
(black), claimed by Maker (red), or claimed by Breaker (blue).
One of the issues in application of McKay’s canonical labeling algorithm emerges right here
because the original version only handles non-colored and vertex colored graphs out of the
box. In [9] the author of the algorithm described how edge colored graph can be transformed into equivalent vertex colored graph which can then be fed as an input to canonical
labeling algorithm (an interested reader can ﬁnd more details in [13]). Unfortunately this
transformation produces a graph with more vertices than the original graph (even when
we have just two colors, the number of vertices doubles), so we did the implementation
from scratch, having [15] in mind.
5.2.2

Non-transitive winning sets

Another issue with detection of isomorphic game tree nodes emerges when dealing with
Fixed Hamiltonian path game since this game has an additional property compared to
the other two games we worked on – there are two predeﬁned vertices that require special
attention. Therefore, we have to incorporate an additional condition, only taking into
account the isomorphisms which map those two vertices to themselves.
We further slice down each isomorphism class into subclasses deﬁned in the following way.
Definition 12. We say that graph G1 with predefined vertices u1 , v1 ∈ V (G1 ) is in the
same isomorphism subclass as graph G2 with predefined vertices u2 , v2 ∈ V (G2 ) if and only
if C(G1 ) = C(G2 ), and isomorphism functions f1 and f2 transforming G1 and G2 into
C(G1 ), respectively, are such that {f1 (u1 ), f1 (v1 )} = {f2 (u2 ), f2 (v2 )}.

10

Applying this deﬁnition to our problem, we chose sets {u1 , v1 } and {u2 , v2 } to be sets of
endpoints of winning sets in FHP n , meaning that Maker wins the game on G1 if and only
if he wins on G2 .

5.3

Move ordering

Our algorithm is not processing the whole game tree but rather skipping some of the
subtrees whenever it is sure about the outcome of that particular subtree. For example,
when Maker is the one to claim an edge, we will test all the possible moves that he can
play, one after another, until we ﬁnd the one that guarantees his win (provided that such
a move exists). Of course, it would be better that we probe a winning move as early as
possible. Having this in mind we tested a number of heuristics for deﬁning the order of
the iteration over free edges in line 2 of Algorithm 1.
We relied on sorting the free edges according to a predeﬁned criterion. Particularly, free
edges are sorted in non-decreasing order according to Maker’s edge degree edM for Maker’s
moves, and in non-increasing order according to Breaker’s edge degree edB for Breaker’s
moves. The idea behind this is that, informally speaking, Maker may want to prefer playing
where his “weakest link” is, while Breaker may prefer choosing to enforce his “strongest
disconnecting point” ﬁrst.
It turned out this optimization technique, implemented as described, is one of the most
important ones, and it had a tremendous impact on the performance of our algorithm
making the number of traversed game tree nodes signiﬁcantly smaller.

5.4

Winner detection

Procedure PlayerWins(G, P ) is essential for checking if the board of the game G is such
that the player P won the game1 . In order to eﬃciently implement this task we always
did pre-computation of the set F of winning sets that are free of Breaker’s edges. E.g. in
game HAMn we pre-generate the set F of all Hamiltonian cycles in Kn , and then we
constantly update F so that in each moment it contains only the winning sets without any
edges claimed by Breaker.

5.5

Optimization of memory usage

Several optimization techniques applied in our software are on the technical i.e. implementation level, and majority of them are computer memory related. This is natural since we
rely on transposition table in order to keep track of calculated values for visited game tree
nodes, or more precisely their isomorphism classes, and even for relatively small graphs
the number of these classes is extremely large.
Utilizing sets in many components of our program we are able to achieve optimal ratio
of time and memory eﬃciency. Sets are used to implement graphs, canonical labelings,
winning sets and most importantly transposition tables. Of course, we needed eﬃcient
implementations of sets and for that job we used bitsets and high-performance 3rd party
set implementations (in the form of Trove library [14]).
1
If P is Maker, he won if he claimed a whole winning set, and if P is Breaker, he won if he claimed an
edge in each of the winning sets.

11

After all this eﬀort, our transposition tables were still not able to cope with the required
amount of entries because of the limited computer memory. To solve this problem, we
applied various heuristics to clean the tables i.e. to remove the “less important” entries and
free up the memory for the “more important” ones. One eﬃcient technique to do this was
to focus mainly on entries coming from lower depths of the game tree, say depths less than
or equal to a ﬁxed integer d, so whenever we detect that table is full all entries coming
from depths larger than d are removed from the table.

5.6

Implementation, testing and results

Implementation was done using Java programming language, relying only on standard
Java libraries with just one additional component, the already mentioned 3rd party high
performance collections library – Trove [14]. There are two main parts of our computer
program, Minimax algorithm and Brendan McKay’s canonical labeling algorithm. We
chose to implement canonical labeling algorithm on our own in order to be more ﬂexible
and tailor the algorithm fully to our needs. We note that there are implementations of
related algorithms available online (e.g. [8]).
While implementing the algorithm we followed the idea of doing it in a generic way to make
our code easily adaptable for solving other positional games on graphs as well. Examples
of this can be seen when browsing through our code since for all three games we exploited
this approach, using the same code base with just minor modiﬁcations for each particular
game.
For testing purposes we used various revisions of Java version 6 and 7, and on top of that
we ran the program on a number of diﬀerent versions of three diﬀerent operating systems,
Windows, Mac OSX and Linux, all in the eﬀort to minimize the possibility of error coming
from any of these layers. We further conducted thorough testing of both of the main parts
of our implementation using unit tests, in order to eliminate the possibility of errors coming
from smaller components of our program. In the end, we put a lot of additional eﬀort to
verify that our implementation of Brendan McKay’s algorithm is correct by comparing
output of our implementation with the one provided by the author [8] for many diﬀerent
types of graphs.
Thr machine used for testing was Fujitsu Celsius M730 with Intel Xeon E5-1620 processor
running at 3.7 GHz, 32GB of RAM and with Ubuntu operating system. We were able to
prove following statements using this machine.
Proof of Lemma 6.

Running time
Maker as ﬁrst player
Winner

Running time
Maker as second player
Winner

HAM4

HAM5

HAM6

HAM7

HAM8

HAM9

0s

0s

0.1s

1s

2s

30s

Breaker

Breaker

Breaker

Breaker

Maker

Maker

HAM4

HAM5

HAM6

HAM7

HAM8

HAM9

0s

0s

0.1s

1s

3s

68s

Breaker

Breaker

Breaker

Breaker

Maker

Maker

12

Proof of Lemma 8.

Running time
Maker as ﬁrst player
Winner

Running time
Maker as second player
Winner

HP 4

HP 5

HP 6

HP 7

0s

0s

0s

0.3s

Breaker

Maker

Maker

Maker

HP 4

HP 5

HP 6

HP 7

0s

0s

0.1s

0.3s

Breaker

Maker

Maker

Maker

Proof of Lemma 9.

Running time
Maker as ﬁrst player
Winner

Running time
Maker as second player
Winner

6

FHP 4

FHP 5

FHP 6

FHP 7

FHP 8

FHP 9

0s

0s

0.5s

3s

110s

3990s

Breaker

Breaker

Breaker

Maker

Maker

Maker

FHP 4

FHP 5

FHP 6

FHP 7

FHP 8

FHP 9

0s

0s

0.1s

2s

230s

16286s

Breaker

Breaker

Breaker

Breaker

Maker

Maker

An application

Generally speaking, the most direct way to show that a player wins a positional game is
to exhibit an explicit strategy for the player, proving that it is a winning one. There are
numerous cases (see [4] for examples) that such a strategy relies on strategies for one or
more auxiliary positional games, where the auxiliary games are often conﬁned to some part
of the board and/or some stage of the game play.
Our results are applicable when such auxiliary games have Hamiltonian cycles or Hamiltonian paths as winning sets, and they are played on boards of ﬁxed size. An example
of that can be found in [3, Theorem 1.4], when estimating the smallest number of edges
m̂(n) a graph on n vertices can have, knowing that Maker as ﬁrst player can win the
Maker-Breaker Hamiltonicity game played on its edges. Using our results from Theorem 1
and Theorem 3, we are able to improve the upper bound on m̂(n).
In [3] it was showed that m̂(HAM) ≤ 21n for n ≥ 1600, by explicit construction of
a graph G′n with n vertices and 21n edges, along with a proof that Maker can win the
13

game playing on E(G′n ). The graph G′n was constructed by dividing n vertices into sets
V0 , V1 , . . . , Vm−1 , V ′ , with m ≥ 40, such that d ≤ |Vi | ≤ d + 1, where d = 38, and V ′ =
{u0 , . . . , um−1 } contains exactly m vertices. As for the edges of Gn , for every 0 ≤ i < m,
every two vertices in Vi are connected with an edge (i.e. the graph induced on Vi is a
clique), and on top of that, for every 0 ≤ i < m, there is an edge between ui and every
vertex of both Vi and Vi+1 (indices are observed modulo m). All of this totals to no more
than ( d2 + 2)n = 21n edges.
To prove that Maker can win Hamiltonicity game on E(G′n ), the authors of [3] relied on
the fact that Maker wins HAMn on E(Kn ) for all n ≥ 38, as n = 38 was the smallest
known such n at the time. This was later improved by Hefetz and Stich [5] to n = 29,
and now our Theorem 1 gives the optimal n = 8. Having this in mind we can repeat the
exact same proof with an adjusted construction of G′n , reducing the size of all Vi by setting
d = 8, and getting an immediate improvement of the upper bound to m̂(HAM) ≤ 6n.
But, it turns out that with the help of Fixed Hamiltonian Path game we are able to alter
the construction and get an even better upper bound.
Proof of Theorem 4. We will ﬁrst describe our construction of the graph Gn whose edge
set will be the board of the game, and then we will prove that on this board Maker indeed
can win Hamiltonicity game.
Let d = 7, and let m and 0 ≤ r < d be integers such that n = md + r. The vertices of
Gn are partitioned into m sets V0 , V1 , . . . , Vm−1 , such that |Vi | = d + 1, 0 ≤ i < r, and
|Vi | = d, r ≤ i < m. Next, we arbitrarily pick vertices ai ∈ Vi , 0 ≤ i < m, and deﬁne
Wi := {ai−1 } ∪ Vi , where indices are observed modulo m. The set of edges of Gn is deﬁned
with
m−1
o
[ n
(v1 , v2 ) v1 , v2 ∈ Wi , v1 6= v2 , {v1 , v2 } =
6 {ai−1 , ai } .
E(Gn ) =
i=0

In other words, the graph Gn consists of a “cycle” of cliques, where each two consecutive
cliques overlap on a vertex, and each clique is missing exactly one edge (between the two
vertices it shares with the neighboring cliques). The number of edges in Gn is
 
 
9
8
E(Gn ) = r
+ (m − r)
−m
2
2
 

8
=m
− 1 + 8r
2
n
≤ (4 · 7 − 1) + 48.
7
If n ≥ 336, this is upper bounded by 4n.
To win Hamiltonicity game on E(Gn ), Maker simply plays m Fixed Hamiltonian Path
games in parallel, one on each of graphs Gn [Wi ], 0 ≤ i < m. More precisely, in each of
those games Maker, as the second player, plays the game FHP |Wi | , with ﬁxed vertices ai−1
and ai . As we previously observed, the edge (ai−1 , ai ) does not participate in any winning
sets, so Theorem 3 guarantees Maker’s win in all those games. Hence, for every 0 ≤ i < m,
Maker can claim a Hamiltonian path on Gn [Wi ] with endpoints ai−1 and ai . These paths
together form a cycle that covers all vertices of Gn , so Maker wins the Hamiltonicity game
on E(Gn ).
Even though our proof works for n ≥ 336, we can similarly obtain a non-trivial upper
bound for any n ≥ 14. Indeed, we can construct a graph consisting of a “cycle” of (two or
14

more) cliques in the exact same way as in the previous proof, just making sure that each
clique has at least 8 vertices. Then we can borrow Maker’s strategy from the previous
proof, as well as the argument that he can claim a Hamiltonian cycle playing on that
graph.

7

Future work

We have resolved three unbiased games played on the edges of a complete graph, Hamiltonicity game, Hamiltonian Path game and Fixed Hamiltonian Path game, for every n and
for each of the players starting the game. One related game that remains out of reach is the
so-called Hamiltonian-Connectivity game, where Maker’s goal is to claim all edges of some
spanning Hamiltonian-connected graph (a graph in which every two vertices are connected
by a Hamiltonian path). This game may be utilized in a similar way as Fixed Hamiltonian
Path game, but with more freedom – what were two fixed (predetermined) vertices in Fixed
Hamiltonian Path game, become any two vertices in Hamiltonian-Connectivity game. For
that reason, we think that knowing the outcome of the game for every n would be valuable.
One consequence of ﬁnding the winner of a game using a computer is that typically we
do not have a compact graph-theoretic description of a winning strategy for the winner.
This is true for all games on small boards that we looked at – we know who wins, but this
knowledge is not accompanied by a coherent strategy (other than a huge list of winning
moves, one for each game position).
Because our computer program is implemented in a generic way it could be fairly easily
adapted for attacking other positional games when played on small (enough) boards. We
are hoping that other positional games can be solved using the tools developed in this
paper.

References
[1] V. Chvátal and P. Erdős. Biased positional games. Annals of Discrete Mathematics,
2:221–229, 1978.
[2] D. Clemens, A. Ferber, R. Glebov, D. Hefetz, and A. Liebenau. Building spanning trees quickly in Maker-Breaker games. SIAM Journal on Discrete Mathematics,
29(3):1683–1705, 2015.
[3] D. Hefetz, M. Krivelevich, M. Stojaković, and T. Szabó. Global Maker–Breaker games
on sparse graphs. European Journal of Combinatorics, 32(2):162–177, 2011.
[4] D. Hefetz, M. Krivelevich, M. Stojaković, and T. Szabó. Positional Games. Oberwolfach Seminars 44. Birkhäuser, 2014.
[5] D. Hefetz and S. Stich. On two problems regarding the Hamiltonian cycle game. The
Electronic Journal of Combinatorics, 16(1):R28, 2009.
[6] M. Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1))n/ ln n.
Journal of the American Mathematical Society, 24(1):125–131, 2011.
[7] B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45–87,
1981.
15

[8] B. D. McKay and A. Piperno. Practical graph isomorphism, II. Journal of Symbolic
Computation, 60(0):94–112, 2014.
[9] B. D. McKay and A. Piperno. Nauty and Traces User’s Guide (Version 2.6). Technical
report, 2016.
[10] I. Millington and J. Funge. Artificial Intelligence for Games, Second Edition. Morgan
Kaufmann Publishers Inc., 2nd edition, 2009.
[11] A. Papaioannou. A Hamiltonian game. Annals of Discrete Math, 13:171–178, 1982.
[12] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall
Press, 3rd edition, 2009.
[13] C. Spermann and M. Leuschel. ProB gets Nauty: Eﬀective Symmetry Reduction for
B and Z Models. In TASE, 15–22. IEEE Computer Society, 2008.
[14] Trove. Trove - High Performance Collections for Java.
systems.com. Online; accessed December 19, 2016.

http://trove.starlight-

[15] E. Turner, M. Leuschel, C. Spermann, and M. Butler. Symmetry Reduced Model
Checking for B. In TASE, 25–34. IEEE Computer Society, 2007.
[16] D. West. Introduction to Graph Theory. Prentice Hall, 2001.

16

