Hamiltonian Maker-Breaker games on small graphs
Miloš Stojaković Nikola Trkulja










Hamiltonian Maker-Breaker games on small graphs
    
	Miloš Stojaković
		[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]
	Nikola Trkulja
		[1]

    
================================================================================================================================================================================================================================================================================================================================================





We look at the unbiased Maker-Breaker Hamiltonicity game played on the edge set of a complete graph K_n, 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 <cit.>.

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.






§ INTRODUCTION


A positional game is a hypergraph (X,ℱ), where X is a finite set representing the board of the game, and ℱ⊆ 2^X 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 first. One of the main questions in the theory of positional games is the existance of a winning strategy for one of the players, when both are playing optimally. The player that has a strategy to win the game is referred to as the winner of the game.

The positional games we intend to study are played on graphs, and in particular, on the edge set of a complete graph K_n. Our prime interest lies with Hamiltonicity game _n, where the winning sets are the edge sets of all Hamiltonian cycles in K_n. The game was first introduced by Chvátal and Erdős in <cit.>, and since then it has been one of the most studied positional games on graphs, see <cit.>. It was shown in <cit.> that Maker has a winning strategy for all sufficiently large n. Papaioannou <cit.> later proved that Maker wins the game for all n ≥ 600, and at the same time conjectured that the smallest n for which Maker can win is 8. Hefetz and Stich <cit.> 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 first 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 affirmative. As the trivial cases n ≤ 3 can be handled directly, from now on we assume n ≥ 4.
 
In the Maker-Breaker _n game on E(K_n), 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 ℋ𝒫_n, first introduced in <cit.>, the winning sets are the edge sets of all Hamiltonian paths in K_n. We are able to show the following.
 
In the Maker-Breaker Hamiltonian Path game ℋ𝒫_n on E(K_n), Maker, as first or second player, wins if and only if n ≥ 5.

This theorem is a strengthening of Papaioannou's result from <cit.> where he proved that Maker, as first player, can win ℋ𝒫_n if and only if n ≥ 5.
	
In Fixed Hamiltonian Path game ℱℋ𝒫_n, the goal of Maker is to claim a Hamiltonian path between two fixed (predetermined) vertices, u,v∈ V(K_n). Even though in the literature this game does not draw as much interest as _n and ℋ𝒫_n, it has appeared as an auxiliary game when studying some other games on graphs, see e.g. <cit.>.
 	
In the Maker-Breaker Fixed Hamiltonian Path game ℱℋ𝒫_n on E(K_n), 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 ℱℋ𝒫_n the edge between the fixed 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(K_n) ∖{(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 first 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 first or second when n is at least 6. On top of that, he wins also for n=2 when he plays first.

Let us note that even though answering the question of who wins a game on a small board (with n fixed) is a finite problem, it still may have a greater scientific 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 fixed size, and knowing their outcome is essential for completing the analysis. An example of that can be found in <cit.>, where one of the problems tackled was to estimate the smallest number of edges m̂(n) a graph on n vertices can have, knowing that Maker as first player can win the Maker-Breaker Hamiltonicity game played on its edges. It was proved in <cit.> that 2.5n ≤m̂(n) ≤ 21n, for all n ≥ 1600. We show how to apply our results about Hamiltonicity game in Theorem <ref> and Fixed Hamiltonian Path game in Theorem <ref> to improve this upper bound, eventually obtaining the following.
 	
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., <cit.>) that we can find 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 a computer. In particular, if the board of the game is E(K_n), its size is n2, so there are n2! different 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 <ref> 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 efficiently 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 fit 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.





 §.§ Preliminaries and organization


	Our graph-theoretic notation is standard and follows the one from <cit.>. 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 E_G(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. <cit.>.
	 
	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 d_M(v) (respectively, d_B(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 ed_M(e), is defined to be ed_M(e) := d_M(u) + d_M(v), and Breaker's edge degree is ed_B(e) := d_B(u) + d_B(v).

The rest of the paper is organized as follows. In Section <ref> we prove Theorem <ref>, in Section <ref> we prove Theorem <ref> and in Section <ref> we prove Theorem <ref>. Section <ref> contains the description of the algorithms and optimization methods used in our computer programs, as well as the results we obtain with their help. In Section <ref> we show how our results can be applied in solving other problems in theory of positional games, by proving Theorem <ref>. Finally, in Section <ref> we give some open problems and ideas for future work.





§ HAMILTONICITY GAME



The following lemma lies in the foundation of our proof of Theorem <ref>.

	
Independent of who starts the game _n, 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 <ref>.

The previous result gives us a firm induction base for proving that Maker can win _n for all n ≥ 8. We note that Papaioannou already proved the induction step of size 2 for Maker as first player, which can be paired up with our Lemma <ref> to resolve the case when Maker is first. 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 <ref>.
	
 
If Maker, as second player, wins _n, he can also win _n+2 as second player.



Suppose that Maker, as second player, has a strategy to win _n. We will present Maker's winning strategy for _n+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 V_1:= V(K_n+2) ∖{v,w}. We can now partition the set of all unclaimed edges into two sets, the first set being E_1 = E(V_1) and the second one E_2 = E(K_n+2) ∖
		(E_1 ∪{ m, (u,v) }). These edge sets are shown in the Figure <ref>.
		
		

		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 E_i Maker will also try to claim an edge from E_i, i= 1, 2. If this is not possible, he will claim an arbitrary 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. <cit.>.
		
		Maker will play in E_1 using his winning strategy for _n, meaning that by the time all edges in E_1 are claimed he will fully occupy some n-cycle H_n in E_1.
		
		When playing in E_2 Maker's goal is to make sure that by the time all the edges are claimed (in both E_1 and E_2) he claimed a Hamiltonian cycle. This Hamiltonian cycle will be an extension of H_n to a cycle on two more vertices, now also containing the edge m. More precisely, in order to extend the cycle H_n=(x_1, x_2, …, x_n, x_1), Maker wants to claim edges (x_i, y_1), (x_i+1, y_2) ∈ E_2, such that the edge (x_i,x_i+1) ∈ H_n
		and  (y_1,y_2) = m. That way, Maker would claim a Hamiltonian cycle H_n+2=(x_1, …, x_i, y_1, y_2, x_i+1, …, x_n, x_1), as shown in Figure <ref>.

 			
		
During the game, if for a vertex x ∈ V_1 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 E_2 incident to each of vertices v and w.

Situation 2: Breaker isolated exactly two vertices, Maker has one isolated vertex a, and Maker claimed an edge from E_2 ∖{(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 ∈ H_n. 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 E_2 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 H_n there must exist two adjacent vertices x_i and x_i+1 containing labels 0 and 1, respectively. Maker will then use these vertices x_i and x_i+1 to extend the cycle H_n.

In Situation 2 there is a vertex a with label set {0,1}. If this vertex is adjacent to some vertex x ∈ H_n whose label set is not empty, Maker can extend the cycle H_n 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 H_n for the same reasons as in Situation 1, since he claimed an edge from E_2 ∖{(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 E_2. In each move, Maker will apply the first applicable rule in the following list:




  * If there is only one free vertex x ∈ V_1 left, and Maker has not claimed any edges incident to a vertex  y ∈{v, w}, he claims the edge (x,y).


  * If there exists a vertex half isolated by Breaker, Maker picks an arbitrarily vertex x half isolated by Breaker and claims the other edge incident to x.


  * 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).


  * 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 first move in E_2 he essentially has only three different choices, shown in Figure <ref> (along with the move of Maker that will follow in each of the cases).
		
		
		
	Now, let us analyze each of the three cases from Figure <ref> individually.


		Case (a): In this case, Breaker first has an option to isolate a vertex x_i_1. 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.
		
		Case (b): Again, Breaker can start by isolating a vertex x_i_1 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 <ref>. Therefore, Maker will inevitably find himself in Situation 1.
		
		
		
		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 ∈ V_1 he can claim (x,w) or (x,v). These three possibilities are shown in Figure <ref> (along with the move of Maker that will follow in each of the cases).
		
		


		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 first 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 finish in Situation 1. If it happens that Rule 1 needs to be applied, Maker will claim an edge (v,x_i_n-1), where x_i_n-1 is the last free vertex. Depending if Breaker now isolates a vertex x_i_n-2 or not, the game can end up in different situations. If Breaker does not isolate x_i_n-2 the game ends in Situation 1. Otherwise, after vertex x_i_n-2 is isolated by Breaker, Maker isolates x_i_1 and the game ends in Situation 2.
		
		Hence, Maker can always create one of the two winning situations.
	
	
	
		Applying mathematical induction, with Lemma <ref> as the base case and Lemma <ref>
		as the induction step we get that Maker, as second player, wins _n for all n ≥ 8. Combining this 
		result with the result from Theorem <ref> we complete the proof of Theorem <ref>.
	




§ HAMILTONIAN PATH GAME



In order to complete the proof of Theorem <ref> we used our computer program to obtain following result.
	
	
	
Independent of who starts the game ℋ𝒫_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 <ref>.

With the help of the previous lemma and Theorem <ref>, the proof of Theorem <ref> is straightforward.
	
	
		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 <ref> also tells us that Maker can win ℋ𝒫_n for all n
		≥ 8 as second player. When we combine this with the result from Lemma <ref> proof of
		Theorem <ref> is complete.
	




§ FIXED HAMILTONIAN PATH GAME




The following lemma will cover several finite cases in the proof of Theorem <ref>.
	
	
When Maker starts the game ℱℋ𝒫_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 ℱℋ𝒫_n for larger values of n. We will not perform an induction step, but rather rely on our knowledge of the outcome of _n.
Combining the following result with Theorem <ref>, along with Lemma <ref> that covers the few initial cases, we readily prove Theorem <ref>.
	
	
	
		If Maker, as second player, wins _n, he can also win ℱℋ𝒫_n+2 as second player.
	
	
Suppose that Maker, as second player, has a strategy to win _n. We will present Maker's winning strategy for ℱℋ𝒫_n+2, with two fixed 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 V_1:= V(K_n+2) ∖{u,v}. We can partition the set of all unclaimed edges into two sets, the first set being E_1 = E(V_1) and the second one E_2 = E(K_n+2) ∖ (E_1 ∪{ e }).

Now the goal of Maker is exactly the same as in the proof of Lemma <ref> – he wants to build an n-cycle on E_1, and he wants to play on E_2 to connect vertices u and v to two neighboring vertices of that n-cycle. As the structure of E_1 and E_2 here is exactly the same, with exception of E_2 having one more unclaimed edge (which is only beneficial for Maker), he can follow the same strategy as in the proof of Lemma <ref> and win the game.
	




§ ALGORITHMIC ANALYSIS


	
	In this section we present the techniques and approaches used in our computer program to solve games
	_n, ℋ𝒫_n and ℱℋ𝒫_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 find all the information on how to run and use it, along with the source code.
	
	


 §.§ Traversing the game tree
	
	
	As we already noted, in order to determine the winner of a particular game, it is enough to completely
	traverse the game tree, 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 <cit.>.
	
	
	
	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 first.
    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.
		
	


 §.§ 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 <cit.>
	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 efficient 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
	<cit.>. Canonical labeling of a graph is defined in the following way.
	
	
	Canonical labeling is a function C mapping graphs to graphs, such that every graph G_1 is isomorphic to C(G_1), and for every graph G_2 isomorphic with G_1 we have C(G_2)=C(G_1).
	
	
	In other words, canonical labeling gives a unique representative for each class of isomorphic
	graphs, and with McKay's algorithm we can define and compute this graph in an efficient manner. That enables us to prune the game tree significantly, as we can store the winner only for canonical labelings.

	


  §.§.§ 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 <cit.> 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 find more details in <cit.>). 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). Because of this, we did the implementation from scratch, 
	having <cit.> in mind, where authors adapted the canonical labelling algorithm to work with edge
	colored graphs by distinguishing the vertices according to the colors of incident edges.

	


  §.§.§ 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
    predefined 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 defined in the following way.


	
	We say that graph G_1 with predefined vertices u_1, v_1 ∈ V(G_1) is in the same isomorphism
	subclass as graph G_2 with predefined vertices u_2, v_2 ∈ V(G_2) if and only if C(G_1) =
	C(G_2), and isomorphism functions f_1 and f_2 transforming G_1 and G_2	into C(G_1), respectively, are such that { f_1(u_1), f_1(v_1) } = { f_2(u_2), f_2(v_2) }.
	
	
	Applying this definition to our problem, we chose sets { u_1, v_1 } and { u_2, v_2 } to be
	sets of endpoints of winning sets in ℱℋ𝒫_n, meaning that Maker wins the game on	G_1 if and only if he wins on G_2.
	
	


 §.§ 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 find 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 defining
	the order of the iteration over free edges in line <ref> of Algorithm <ref>.
	
	We relied on sorting the free edges according to a predefined criterion. Particularly, free edges are sorted in non-decreasing order according to Maker's edge degree ed_M for Maker's moves, and in non-increasing order according to Breaker's edge degree ed_B 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” first.
	
	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 significantly smaller.
	
		


 §.§ 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 game[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.]. In order to efficiently
	implement this task we always did pre-computation of the set ℱ of winning sets that are free of Breaker's edges. E.g. in
	game _n we pre-generate the set ℱ of all Hamiltonian cycles in K_n, and then we constantly
	update ℱ so that in each moment it contains only the winning sets without any edges claimed by Breaker.
	
	


 §.§ 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 efficiency. Sets are used to implement graphs, canonical labelings, winning
	sets and most importantly transposition tables. Of course, we needed efficient implementations of
	sets and for that job we used bitsets and high-performance 3rd party set implementations (in the form
	of Trove library <cit.>).
	
	After all this effort, 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 efficient 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 fixed integer d, so whenever we detect that the 
	table is full all entries coming from depths larger than d are removed from the table.
	
	


 §.§ 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 <cit.>.
    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 flexible and tailor the algorithm fully to our needs. We note that there are implementations of related algorithms available online (e.g. <cit.>).
	
	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 modifications 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 different versions of three different operating systems,
	Windows, Mac OSX and Linux, all in the effort 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 effort 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 <cit.> for many different types of graphs.
	
	The 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.
	
	
		
		

			
			
			2-7
 			1c|     _4     _5
 								      _6     _7
 								      _8     _9 

			Running timeMaker as first player     0s     0s     0.1s     1s     2s     30s 

			Winner     Breaker     Breaker     Breaker     Breaker     Maker     Maker 

			
			
		

		

			
			
			2-7
 			1c|     _4     _5
 								      _6     _7
 								      _8     _9 

			Running timeMaker as second player     0s     0s     0.1s     1s     3s     68s 

			Winner     Breaker     Breaker     Breaker     Breaker     Maker     Maker 

			
			
		
		
	

	
		
		

			
			
			2-5
 			1c|     ℋ𝒫_4     ℋ𝒫_5
 								      ℋ𝒫_6     ℋ𝒫_7 

			Running timeMaker as first player     0s     0s     0s     0.3s 

			Winner     Breaker     Maker     Maker     Maker 

			
			
		

		

			
			
			2-5
 			1c|     ℋ𝒫_4     ℋ𝒫_5
 								      ℋ𝒫_6     ℋ𝒫_7 

			Running timeMaker as second player     0s     0s     0.1s     0.3s 

			Winner     Breaker     Maker     Maker     Maker 

			
			
		

	

	
		
		

			
			
			2-7
 			1c|     ℱℋ𝒫_4     ℱℋ𝒫_5
 								      ℱℋ𝒫_6     ℱℋ𝒫_7
 								      ℱℋ𝒫_8     ℱℋ𝒫_9 

			Running timeMaker as first player     0s     0s     0.5s     3s     110s     3990s 

			Winner     Breaker     Breaker     Breaker     Maker     Maker     Maker 

			
			
		

		

			
			
			2-7
 			1c|     ℱℋ𝒫_4     ℱℋ𝒫_5
 								      ℱℋ𝒫_6     ℱℋ𝒫_7
 								      ℱℋ𝒫_8     ℱℋ𝒫_9 

			Running timeMaker as second player     0s     0s     0.1s     2s     230s     16286s 

			Winner     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 <cit.> for examples) that such a strategy relies on strategies for one or more auxiliary positional games, where the auxiliary games are often confined 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 fixed size. An example of that can be found in <cit.>, when estimating the smallest number of edges m̂(n) a graph on n vertices can have, knowing that Maker as the first player can win the Maker-Breaker Hamiltonicity game played on its edges. Using our results from Theorem <ref> and Theorem <ref>, we are able to improve the upper bound on m̂(n).


In <cit.> it was showed that m̂(n) ≤ 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 game playing on E(G'_n). The graph G'_n was constructed by dividing n vertices into sets V_0, V_1, … , V_m-1, V', with m ≥ 40, such that d ≤ |V_i| ≤ d+1, where d = 38, and V' = { u_0, …, u_m-1} contains  exactly m vertices. As for the edges of G_n, for every 0 ≤ i <m, every two vertices in V_i are connected with an edge (i.e. the graph induced on V_i is a clique), and on top of that, for every 0 ≤ i < m, there is an edge between u_i and every vertex of both V_i and V_i+1 (indices are observed modulo m). All of this totals to no more than (d/2 + 2)n = 21n edges.

To prove that Maker can win Hamiltonicity game on E(G'_n), the authors of <cit.> relied on the fact that Maker wins _n on E(K_n) for all n ≥ 38, as n=38 was the smallest known such n at the time. This was later improved by Hefetz and Stich <cit.> to n=29, and now our Theorem <ref> 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 V_i by setting d=8, and getting an immediate improvement of the upper bound to m̂(n) ≤ 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.

	
		We will first describe our construction of the graph G_n 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 G_n are partitioned into m sets
        V_0, V_1,… , V_m-1, such that |V_i|=d+1, 0 ≤ i < r, and |V_i|=d, r ≤ i < m. Next,
		we arbitrarily pick vertices a_i ∈ V_i, 0 ≤ i < m, and define W_i:= { a_i-1}∪ V_i, where indices are observed modulo m.
        The set of edges of G_n is defined with
        
    E(G_n) = ⋃_i=0^m-1{ (v_1, v_2)  |     v_1, v_2∈ W_i,    v_1 ≠ v_2,   { v_1, v_2}≠{ a_i-1, a_i}}.

        In other words, the graph G_n 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 G_n is
        
    E(G_n)    = r92 + (m-r)82 - m  
        =  m(82 -1 ) + 8r 
       ≤n/7(4· 7 - 1 ) + 48.

        If n ≥ 336, this is upper bounded by 4n.

        To win Hamiltonicity game on E(G_n), Maker simply plays m Fixed Hamiltonian Path games in parallel, one on each of graphs G_n[W_i], 0 ≤ i < m.
        More precisely, in each of those games Maker, as the second player, plays the game ℱℋ𝒫_|W_i|, with fixed vertices a_i-1 and a_i. As we previously observed, the edge (a_i-1, a_i) does not participate in any winning sets, so Theorem <ref> guarantees Maker's win in all those games. Hence, for every 0 ≤ i < m, Maker can claim a Hamiltonian path on G_n[W_i] with endpoints a_i-1 and a_i. These paths together form a cycle that covers all vertices of G_n, so Maker wins the Hamiltonicity game on E(G_n).
	

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 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.





§ 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). Our approach was not efficent enough to handle Hamiltonian-Connectivity game since the nature of the winning sets is too complex making our pruning and winner detection procedures much less effective. 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 finding 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.
	


abbrv-pages



