#  A note on null distance and causality encoding

Gregory J. Galloway Research partially supported by the Simons Foundation,
Award No. 850541, Department of Mathematics
University of Miami

###### Abstract

Under natural conditions, the null distance introduced by Sormani and Vega
[10] is a metric space distance function on spacetime, which, in a certain
precise sense, can encode the causality of spacetime. The null distance
function requires the choice of a time function. The purpose of this note is
to observe that the causality assumptions related to such a choice in results
used to establish global encoding of causality, due Sakovich and Sormani [9]
and to Burtscher and García-Heveling [2], can be weakened.

In [10], C. Sormani and C. Vega introduced a novel distance measure on
spacetimes (time-oriented Lorentzian manifolds), called null distance, which,
under reasonable circumstances, has a number of desirable properties. In
particular, under certain conditions, it is a metric on spacetime, in the
standard sense of metric spaces, and, remarkably, at the same time, encodes
the causal structure of spacetime. We will discuss what is meant by the latter
shortly. The construction of such a distance function was motivated in part by
the program to study the convergence theory of Lorentzian manifolds. The null
distance function requires the choice of a time function on spacetime. The
main purpose of this note is to observe that the causality assumptions related
to such a choice, which have been used to establish global encoding of
causality (see [9, 2]) can be replaced by an a priori weaker causality
condition.

We begin by fixing some notation and terminology. By a spacetime we mean a
smooth connected time orientable Lorentzian manifold $(M,g)$, with $\dim M\geq
2$, where $g$ has signature $(-,+\cdots+)$. With regard to causal theoretic
notions such as $I^{\pm}$ (timelike futures and pasts), $J^{\pm}$ (causal
futures and pasts), $D^{\pm}$ (future and past domains of dependence), and
$H^{\pm}$ (future and past Cauchy horizons), we by and large follow the
conventions in O’Neill [7].

Recall, an edge point of an acausal set $A$ is a point $p$ in the closure of
$A$ such that every neighborhood $U$ of $p$, contains a timelike curve from
$I^{-}(p,U)$ to $I^{+}(p,U)$ that does not meet $A$. By an acausal $C^{0}$
spacelike hypersurface in a spacetime $M$, we mean an acausal subset $S\subset
M$ that does not contain any of its edge points. It follows that an acausal
$C^{0}$ spacelike hypersurface is, in fact, a topological submanifold of $M$
of co-dimension one (see [7, Proposition 14.25]). An acausal $C^{0}$ spacelike
hypersurface $S$ is a Cauchy hypersurface for $M$ provided every inextendible
causal curve in $M$ meets $S$ (and by acausality, does so exactly once). The
existence of a Cauchy hypersurface for $M$ is equivalent to $M$ being globally
hyperbolic.

A time function on a spacetime $M$ is a continuous real-valued function
$\tau:M\to{\mathbb{R}}$ that is strictly increasing along all future-directed
causal curves. A basic example of a time function is a smooth function on $M$
which has a past pointing timelike gradient. However, there are types of time
functions, such as the so-called cosmological time function [1], that needn’t
be smooth in general. The level sets $\tau=\tau_{0}$ of a time function $\tau$
on $M$ are clearly acausal. Moreover, it is easy to see, using the continuity
of $\tau$, that the level sets do not contain any edge points. In fact, since
the level sets are closed subsets of spacetime (again by continuity of
$\tau$), all the level sets are edgeless (i.e. have no edge points); cf. [7,
Corollary 14.26]. Thus, the level sets of a time function are edgeless acausal
$C^{0}$ spacelike hypersurfaces. (Such hypersurfaces are sometimes referred to
as partial Cauchy surfaces.) The level sets need not, in general, be
connected.

The null distance function introduced by Sormani and Vega [10] is defined
briefly as follows.111In [10], the authors define null distance with respect
to generalized time functions, which are not required to be continuous. Many
results obtained in [10, 12, 9] apply to such time functions. Here we are only
considering continuous time functions. Suppose $\tau:M\to{\mathbb{R}}$ is a
time function on a spacetime $M$. The null length of a piecewise causal curve
$\beta:[a,b]\to M$, with break points $x_{i}=\beta(s_{i})$, $0\leq i\leq m$,
where each smooth causal segment may be either future pointing or past
pointing, is defined by

$\hat{L}_{\tau}(\beta):=\sum_{i\,=\,1}^{m}|\tau(x_{i})-\tau(x_{i-1})|\,.$

The _null distance function_ $\hat{d}_{\tau}:M\times M\to{\mathbb{R}}$ on $M$
is then defined by taking the inf of the null lengths between any two points
$p$ and $q$,

$\hat{d}_{\tau}(p,q):=\inf\\{\hat{L}_{\tau}(\beta):\beta\textrm{\; is
piecewise causal from \,}p\textrm{\, to \,}q\\}\,.$

See e.g. [10, 12, 9, 2] for a discussion of fundamental properties and
examples.

As observed in [10], the null distance $\hat{d}_{\tau}:M\times M\to[0,\infty)$
is in general a pseudometric, but which can fail to be definite. However,
there is a natural class of time functions $\tau$ for which the null distance
is definite, and hence is a true metric, in the sense of metric spaces. A time
function $\tau:M\to{\mathbb{R}}$ is said to be _locally anti-Lipschitz_
provided for every point $p\in M$ there is a neighborhood $U$ of $p$ that has
a Riemannian metric with a distance function $d_{U}:U\times U\to[0,\infty)$
such that for all $x,y\in U$ one has

$\ x\leq y\implies\tau(y)-\tau(x)\geq d_{U}(x,y)\ ,$ (1)

where ‘$x\leq y$’ means that $y$ is in the causal future of $x$, i.e. $y\in
J^{+}(x)$ (which includes $y=x$). As shown in [10], $\hat{d}_{\tau}:M\times
M\to[0,\infty)$ is definite if and only if $\tau$ is locally anti-Lipschitz.
Moreover, in this case, the metric space topology induced by $\hat{d}_{\tau}$
agrees with the manifold topology. Temporal time functions (smooth functions
with past timelike gradient) and regular cosmological time functions [1]
satisfy this locally anti-Lipschitz condtion [10].

A remarkable feature of the null distance is that, under favorable
circumstances, it encodes the causal structure of spacetime. We say that
$\hat{d}_{\tau}:M\times M\to[0,\infty)$ encodes causality provided the
following holds

$p\leq q\quad\text{if and only if}\quad\hat{d}_{\tau}(p,q)=\tau(q)-\tau(p)\,.$
(2)

The ‘only if’ direction follows easily from the definition of null distance.
As shown in [10], the ‘if’ direction does not hold in general. However Sormani
and Vega [10, Theorem 3.25] proved that the null distance encodes causality
for a large class of generalized Robertson-Walker warped product spacetimes.
Sakovich and Sormani [9, Theorem 1.1] proved a local causality encoding result
for time functions $\tau$ that obey the locally anti-Lipschitz condition. To
obtain a global result, they imposed a further condition on the time function.
We paraphrase their result here.

######  Theorem 1 ([9], Theorem 4.1).

Let $\tau:M\to{\mathbb{R}}$ be a proper locally anti-Lipschitz time function.
Then $\hat{d}_{\tau}$ globally encodes causality in $M$, i.e. (2) holds on
$M$.

Here, $\tau$ being proper means that for all
$\tau_{1},\tau_{2}\in\tau(M)$,with $\tau_{1}\leq\tau_{2}$,
$\tau^{-1}([\tau_{1},\tau_{2}])$ is compact. As observed in [2], the
assumption that $\tau$ is proper implies that its level sets $\tau=\tau_{0}$
are compact Cauchy hypersurfaces, and hence that $M$ is globally hyperbolic.
It also follows that if all the level sets of $\tau$ are compact Cauchy
hypersurfaces then $\tau$ is proper. Thus, in the statement of Theorem 1, the
assumption that $\tau$ is proper can be replaced by the assumption that all
level sets of $\tau$ are compact Cauchy hypersurfaces.

From this perspective, A. Burtscher and L. García-Heveling have recently
obtained a generalization of Theorem 1. As described in [2], this is
accomplished by combining the approach of Sakovich and Sormani, together with
the approach of Burtscher and García-Heveling in their proof of an earlier
version of their global causality encoding result [2, Theorem 3.3], which
required a temporal time function.

######  Theorem 2 ([2], Theorem 1.9).

Let $(M,g)$ be a globally hyperbolic spacetime and $\tau$ a locally anti-
Lipschitz time function such that all level sets are Cauchy. Then the null
distance encodes causality, i.e., (2) holds on $M$.

As observed in [2, Remark 3.6], in the statement of Theorem 2, it is
sufficient to assume that all level sets of $\tau$ are future Cauchy. An
acausal $C^{0}$ spacelike hypersurface $S$ in a spacetime $M$ is future Cauchy
if it has no future Cauchy horizon, i.e. $H^{+}(S)=\emptyset$. Similarly $S$
is past Cauchy if $H^{-}(S)=\emptyset$. Future and past Cauchy hypersurfaces
are necessarily connected. If S is both future and past Cauchy then it’s a
Cauchy hypersurface in $M$.

Here we wish to point out that this future Cauchy condition, under which
Theorem 2 holds, can be replaced by a simple causal theoretic condition which
in general is much weaker. An acausal $C^{0}$ spacelike hypersurface is said
to be future causally complete provided for all points $p\in J^{+}(S)$, the
set $J^{-}(p)\cap S$ has compact closure in S. (Past causal completeness is
defined in a time-dual manner.) As a very simple example, consider Minkowski
space N, with standard coordinates $(t,x^{1},\cdots,x^{n})$, and let
$M=N\setminus\\{(1,0,\cdots,0)\\}$. The time slices $t=t_{0}<1$ are future
causally complete, but not future Cauchy. Similarly, the spacelike
hypersurfaces $t=\sqrt{a^{2}+\sum_{i}(x^{i})^{2}}$, $a\in(0,1)$ are future
causally complete, but neither future nor past Cauchy.

Note that all compact acausal $C^{0}$ hypersurfaces, as well as all future
Cauchy hypersurfaces, are future causally complete. (The latter follows from
e.g. [8, Prop. 5.20]. In fact, if $S$ is future Cauchy then $J^{-}(p)\cap S$
is compact for all $p\in J^{+}(S)$.) Future causal completeness was introduced
in [3], and used, for example, to extend Hawking’s cosmological singularity
theorem to the nonspatially closed case in spacetimes not assumed to be
globally hyperbolic. Further applications have been considered in e.g. [4, 11,
5].

We have the following refinement of Theorem 2.

######  Theorem 3.

Let $\tau$ be a locally anti-Lipschitz time function on a spacetime $(M,g)$
such that all the level sets are future causally complete. Then the null
distance encodes causality, i.e. (2) holds on $M$. Furthermore, $(M,g)$ is
globally hyperbolic.

The theorem is an immediate consequence of [2, Theorem 1.9, Remark 3.6] and
the following observation.

######  Lemma 4.

Let $\tau$ be a time function on a spacetime $(M,g)$ such that all the level
sets are future causally complete. Then all the level sets are future Cauchy.
In particular, $(M,g)$ is globally hyperbolic.

###### Proof.

The lemma follows from a much more general result [6, Theorem 2.2] concerning
spacetime foliations. Here we give a simple direct proof applicable to
spacetimes with time functions. Let $S_{a}$ denote the level set $\tau=a$. It
suffices to show that for each $a\in\tau(M)$, $H^{+}(S_{a})=\emptyset$.
Suppose to the contrary, for some $a$ there exists a point $q\in
H^{+}(S_{a})$. Then $q$ is the future endpoint of a past directed null
geodesic $\eta$ contained in $H^{+}(S_{a})$, which is either past inextendible
or has a past end point on an edge point of $S_{a}$ ([8, Theorem 5.12]). But
$S_{a}$ is edgless. Hence $\eta:[0,c)\to M$, $s\to\eta(s)$, is past
inextendible in $H^{+}(S_{a})$. Let $\\{s_{k}\\}$ be an increasing sequence of
numbers such that $s_{k}\to c$, and let $q_{k}=\eta(s_{k})$. Then
$\\{\tau(q_{k})\\}$ is a decreasing sequence of numbers; set
$b=\inf\\{\tau(q_{k})\\}\geq a$.

Consider the case $b>a$. Fix a smooth, past directed, timelike vector field
$T$ on $M$. Let $\gamma_{k}$ be an integral curve of $T$, starting at $q_{k}$.
$\gamma_{k}$ meets $S_{a}$ at a point $p_{k}$, say ([7, Lemma 14.51]). Since
$\tau(p_{k})=a<b<\tau(q_{k})$, continuity of $\tau$ implies that $\gamma_{k}$
meets $S_{b}$ at a point $r_{k}$, say. By the future causal completeness of
$S_{b}$, $J^{-}(q_{1})\cap J^{+}(S_{b})$ has compact closure in $S_{b}$.
Hence, by passing to a subsequence if necessary, we may assume that $r_{k}$
converges to a point $r\in S_{b}$.

Let $U$ be a small neighborhood of $r$ in $S_{b}$ with compact closure. Using
the flow of the vector field $T$ near $\overline{U}$, we obtain a small
compact spacetime neighborhood $V\cong\overline{U}\times[-\epsilon,\epsilon]$
of $r$, which is contained in $D(S_{b})=D^{+}(S_{b})\cup D^{-}(S_{b})$. Let
$A$ be the set of all points $x\in M$ such that $x$ lies on an integral curve
of $T$ that passes through $\overline{U}$. Then, by continuity of $\tau$,
there exists $\delta>0$ such that

$\\{x\in A:b-\delta<\tau(x)<b+\delta\\}\subset V\,.$

It follows that for $k$ sufficiently large, $q_{k}\in V\cap
J^{+}(S_{b})\subset D^{+}(S_{b})$. But this means that the null geodesic
$\eta$ must extend to $S_{b}$, which is a contradiction. Hence, in this case,
$H^{+}(S_{a})~{}=~{}\emptyset$.

The argument for the case $b=a$ is essentially the same. The future causal
completeness of $S_{a}$, implies that the $p_{k}^{\prime}s$ subconverge to a
point $p\in S_{a}$. Now apply the same argument around the point $p$ as was
done around the point $r$ above. Thus, in either case, we conclude that
$S_{a}$ is future Cauchy. That $(M,g)$ is globally hyperbolic follows from the
fact that $I^{+}(S_{a})={\rm int}\,D^{+}(S_{a})$ is globally hyperbolic for
all $a\in\tau(M)$. ∎

Theorem 3 immediate implies the following refinement of Theorem 1.

######  Corollary 5.

Let $\tau$ be a locally anti-Lipschitz time function on a spacetime $(M,g)$
such that all level sets are compact. Then the null distance encodes
causality, i.e., (2) holds on $M$. Furthermore, $(M,g)$ is globally
hyperbolic.

Remark. In this case the level sets are Cauchy hypersurfaces. This can be
seen, for example, by applying Lemma 4 and its time dual to each level
surface.

## References

  * [1] L. Andersson, G. J. Galloway, and R. Howard, _The cosmological time function_ , Classical Quantum Gravity 15 (1998), no. 2, 309–322.
  * [2] A. Burtscher and L. García-Heveling, _Global hyperbolicity through the eyes of the null distance_ , 2022, arXiv:2209.15610 [math.DG].
  * [3] G. J. Galloway, _Curvature, causality and completeness in space-times with causally complete spacelike slices_ , Math. Proc. Cambridge Philos. Soc. 99 (1986), no. 2, 367–375.
  * [4] , _Some connections between global hyperbolicity and geodesic completeness_ , J. Geom. Phys. 6 (1989), no. 1, 127–141.
  * [5] G. J. Galloway and C. Vega, _Achronal limits, lorentzian spheres, and splitting_ , Ann. Henri Poincaré 15 (2014), no. 11, 2241–2279.
  * [6] A. Horta, _Studies in Lorentzian geometry and mathematical relativity_ , ProQuest LLC, Ann Arbor, MI, 1993, Thesis (Ph.D.)–University of Miami.
  * [7] B. O’Neill, _Semi-Riemannian geometry_ , Pure and Applied Mathematics, vol. 103, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1983.
  * [8] R. Penrose, _Techniques of differential topology in relativity_ , Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1972, Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 7.
  * [9] A. Sakovich and C. Sormani, _The null distance encodes causality_ , Journal of Mathematical Physics 64 (2023), no. 1, 012502.
  * [10] C. Sormani and C. Vega, _Null distance on a spacetime_ , Classical Quantum Gravity 33, no. 8, 085001.
  * [11] J.-H. Treude and J. D. E. Grant, _Volume comparison for hypersurfaces in Lorentzian manifolds and singularity theorems_ , Ann. Global Anal. Geom. 43 (2013), no. 3, 233–251.
  * [12] C. Vega, _Spacetime distances: an exploration_ , 2021, arXiv:2103.01191 [gr-qc].


11institutetext: Department of Computer Science and Engineering (DISI)
University of Bologna, Bologna, Italy
11email<EMAIL_ADDRESS>

# An Upper Bound on the Complexity of Tablut

Andrea Galassi ID

###### Abstract

Tablut is a complete-knowledge, deterministic, and asymmetric board game,
which has not been solved nor properly studied yet. In this work, its rules
and characteristics are presented, then a study on its complexity is reported.
An upper bound to its complexity is found eventually by dividing the state-
space of the game into subspaces according to specific conditions. This upper
bound is comparable to the one found for Draughts, therefore, it would seem
that the open challenge of solving this game requires a considerable
computational effort.

###### Keywords:

Board game game-playing game complexity Tafl games.

##  1 Introduction

Tablut is a strategy board game belonging to the family of Tafl games, a group
of Celtic and Nordic asymmetric board games designed for two players, which
share similar rules. Tafl games (sometimes called Hnefatafl games) may derive
from the Roman game Ludus latrunculorum, and have evolved into many different
variants of the original game, such as Tablut, Brandubh, Hnefatafl, and
Tawlbwrdd. The exact rules of these games are difficult to known, since little
documentation has survived until the present days, and Tablut is probably the
one for which most information is available.

Indeed, Carl Nilsson Linnaeus wrote notes about the game in the XVIII century,
after observing Sámi tribes playing it, even if he didn’t know their language,
so he could not be sure about the original rules. In the following centuries,
other researchers [6, 7, 5, 2, 3] have analyzed, translated, and adjusted
Linnaeus’ notes, producing a set of rules which makes the game relatively
balanced and hopefully similar to its original version. Due to this scarce
documentation, Tafl games have never been subject to proper analysis, and
therefore we don’t know their complexity, nor their solution to any degree.111
According to [1], a game can be solved in several degrees: ultra-weakly solved
(the game-theoretic value for the initial position is known), weakly solved (a
strategy is known to obtain the game-theoretic value of the game), and
strongly solved (for any state reachable from the initial position, a strategy
to obtain the game-theoretic value of that state is known.) The purpose of
this work is to provide an initial estimate of the complexity of Tablut, with
the hope to lay the grounds for deeper studies.

In Section 2, the rules and the properties of Tablut are presented. In Section
3 the game is analyzed so to compute an upper bound on its complexity. Section
4 concludes.

##  2 Rules and Properties

Many different variants of Tablut rules do exist. In this work, the rules of
the game are described mostly following the work of Ashton [2].

###  2.1 Terminology, Material, and Setup

The game is played by two players on a square board of $9\times 9$ cells
depicted in Figure 1. The central cell is called the royal citadel, or castle,
or throne. On each board side, there are 4 groups of 4 cells arranges with a
t-shape that are called citadels or camps. For better comprehension, the
former will be addressed as castle, the latter as camps, while the term
citadel will be used with the meaning “either of them”. Any non-camp and non-
corner cell along the edge of the board will be addressed as escape, the
reason will be clear in the next Subsection. Two cells are considered adjacent
if and only if they are aligned horizontally or vertically and they share an
edge. The term side of a checker will be used to indicate any cell which is
adjacent to the cell where the checker is placed.

One player moves the white checkers, which represent the defenders or Swedes,
while the other moves the black checkers, which represent the attackers or
Muscovites. There are 16 black checkers and 9 white checkers.222 In this work,
the terms _checker_ , _stone_ , and _piece_ will be used as synonyms.  One of
the white checkers is the king and it is marked. Any non-king piece will be
addressed as soldier. The checkers are placed as in Figure 1, with the king in
the castle, the black soldiers in the camps, and the remaining white soldiers
aligned by 2 on each side of the king.

Figure 1: The Tablut empty board (left) and the initial setup (right). The
_castle_ cell is represented with the orange color and the cross symbol. The
_camp_ cells are represented in grey with a triangle. The _escape_ cells are
in blue, with a star. The white soldiers starting cells are marked with a
circle. The _king_ checker is marked with a black cross symbol.

###  2.2 Endgame

The game ends when one of the following conditions is met:

  1. 1.

The king reaches one of the escape cells. This results in the winning of the
white player.

  2. 2.

The king is captured. This results in the winning of the black player.

  3. 3.

The game reaches the same state twice. This results in a draw.333 This rule is
added to avoid an endless sequence of repeated moves and to simplify the game
with respect to [2].

  4. 4.

When a player has no possible moves. This results in the winning of the other
player. This is an addition with respect to [2].

###  2.3 Movement and Capture

The two players alternate their turns, which consist of a single movement of a
checker. The white player starts first. A checker can be moved along a single
straight line, horizontally or vertically, by any number of cells. The
movement must not pass over nor end into a cell that is occupied by another
checker. The same holds for cells that are part of a citadel unless the
checker starts its movement from a cell of the same citadel. This implies that
the only checkers that may move inside a citadel are the black checkers, but
only in their starting citadel and only if they have not ever left it.

To make a capture, a player must move one of its own pieces so as to surround
an adversary piece. A checker is considered surrounded according to different
criteria:

  * •

When the king is in the castle, it is considered surrounded if there are enemy
pieces on all four of its sides.

  * •

When the king is adjacent to the castle, it is considered surrounded if there
are three enemy pieces on three of its side and the castle on the fourth.

  * •

When a soldier is adjacent to a citadel, or when the king is adjacent to a
camp, it is considered surrounded if there is an enemy piece on the opposite
side with respect to the citadel/camp. A soldier inside a camp cannot be
captured.

  * •

In any other case, any piece is considered surrounded if there are two enemy
pieces on two opposite sides of its cell so that the three pieces are aligned
horizontally or vertically.

Capture can happen only in an active way, which means that if a player moves
their own piece so to make it surrounded, the piece is not captured. It is
possible to capture multiple pieces (up to 3) with a single move if that move
allows surrounding more than one piece.

###  2.4 Properties

At any moment of the game, the two players know everything about the state of
the game. Given the state of the game, it is also known the consequence of any
possible move, since there are no random components. Finally, the two players
have different starting positions, checkers, and goals. Therefore this is a
complete-knowledge, deterministic, and asymmetric game.

The board is symmetric along 4 axes, so a single board configuration can have
up to 7 symmetric configurations.

##  3 Computing an Upper Bound for the State Space Size

To compute the complexity of the game it is useful to divide the state-space
into subspaces and compute their size separately. Firstly two subspaces are
distinguished: the space without endgame states and the space with endgame
states. Then, additional subspaces are considered according to specific
conditions. The symmetries of the problem will not be taken into account.

###  3.1 State Space without Endgames

It is useful to compute the complexity of the game without considering endgame
positions because the computation of the final state of the game may not be
necessary for some solvers. Indeed, the characteristics of the final move may
be sufficient to determine the conclusion of the game and its winner, reducing
the computational footprint. For example, a move that declares an escape cell
as the destination for the king is an example of this.

Two possible endgames are not taken into account in this work: the endgame by
draw and neither the endgame given by the impossibility for a player to move
if he has still checkers on the board. The former is naturally included in the
subspace without an endgame state. The latter is not investigated in this
work.

It is possible to make the following considerations regarding any state that
is not an endgame state:

  * •

The king has to be on the board, it can not be in a corner cell, and it can
not be on escape cells, otherwise it would mean that one of the players has
already won (respectively, the black or the white). Therefore, it can be in
any of the $7\times 7=49$ cells in the center of the board. Excluding the
camps, there are only 45 possible cells, one of which is the castle.

  * •

There has to be at least one black soldier on the board. Otherwise, it would
mean that the white player has won. Indeed, the black player could lose its
last checker(s) only due to capture by the white player. The turn after that
move, the black player would not be able to move any checker and therefore
would lose.

  * •

The castle can host only the king.

A naive initial upper bound can be computed considering the values that any
cell can assume: 2 for the castle (with and without the king), 2 for the 16
camps cells (with and without the black soldier), 3 for the 20 edge cells
(with a black soldier, a white soldier or neither), 4 for any other of the
remaining 44 cells (with a black soldier, a white soldier, the king, empty).
This would result in $10^{41}$ possible states as given by Equation 1.

$UB_{naive}=2\cdot 2^{16}\cdot 3^{20}\cdot 4^{44}\approx 10^{41}$ (1)

To reduce the upper bound, it is possible to split the state space according
to particular conditions. It is possible indeed to differentiate two
scenarios: when the king is in the castle and when it is not.

In the first scenario, each possible configuration has $1\leq b\leq 16$ black
pieces, $0\leq w\leq 8$ white soldiers, and $e=80-w-b$ empty cells. It can
therefore be modeled as a permutation with repetitions as in Equation 2.

$P_{80}^{(b,w,e)}=\frac{80!}{b!\cdot w!\cdot e!}$ (2)

The second scenario can be defined similarly, but the king would occupy one of
the 44 cells (the castle is excluded). The remaining cells are therefore 79,
so the number of states (for each combination of $b$, $w$, and $e$ value) is
$44\cdot P_{79}^{(b,w,e)}$.

An upper bound to the number of possible states without endgame positions is,
therefore, $6\times 10^{27}$, as given summing these two scenarios for any
configuration of $b$, $w$, and $e$, as in Equation 3.

$UB_{no\\_end}=\displaystyle\sum_{b=1}^{16}\displaystyle\sum_{w=0}^{8}P_{80}^{(b,w,80-b-w)}+44\cdot\displaystyle\sum_{b=1}^{16}\displaystyle\sum_{w=0}^{8}P_{79}^{(b,w,79-b-w)}\approx
6.1\times 10^{27}$ (3)

It is possible to consider one more characteristic: the white checkers cannot
occupy a camp. Therefore, it is useful to treat camps and non-camps cells
separately. A new variable $c$ is now defined as the number of black checkers
inside any camp. The number of black checkers outside the camp is then $b-c$.
The number of possible configuration of black checkers inside the camps is now
given by the permutation $P_{16}^{(c,16-c)}$, with $0\leq c\leq b$. The number
of possible configurations on the non-camps cells can be computed as
previously (considering 16 cells less). According to this new consideration,
an upper bound on the size of the two discussed scenarios is then computed as:

$UB_{no\\_end}^{castle}=\displaystyle\sum_{b=1}^{16}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{64}^{(b-c,w,64-b-w+c)}\approx 3\times 10^{25}$ (4)

$UB_{no\\_end}^{no\\_castle}=44\cdot\displaystyle\sum_{b=1}^{16}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{63}^{(b-c,w,63-b-w+c)}\approx 9.2\times 10^{26}$ (5)

Their sum, (Equation 6) provides an upper bound $UB_{no\\_end}^{\prime}\approx
9.5\times 10^{26}$

$UB_{no\\_end}^{\prime}=UB_{no\\_end}^{castle}+UB_{no\\_end}^{no\\_castle}\approx
9.5\times 10^{26}$ (6)

Another fact that could be taken into account is that if three black pieces
are in the ends of a camp, also the fourth black piece has to be in that camp,
but this is will not be considered in this work.

###  3.2 State Space of Endgames

To make a proper comparison with other board games, an upper bound has to be
computed considering also the endgame positions. This is done considering all
the possible endgame scenarios computing an upper bound for each one.

Excluding the case when the king is captured, a first endgame scenario is
obtained considering the states when all the black soldiers have been
captured. As done previously, it is possible to divide the scenarios where the
king is inside or outside the castle.

$UB_{\alpha}=\displaystyle\sum_{w=0}^{8}P_{64}^{(w,64-w)}+44\cdot
P_{63}^{(w,63-w)}\approx 2.0\times 10^{11}$ (7)

Another endgame scenario is given by the successful escape of the king to one
of the 16 escape cells. The cell adjacent to the cell used to escape has to be
empty, therefore only 62 cells can host black and white soldiers. In these
cases, the lower bound on $b$ increases once again to 1, since without black
soldiers the game would have already been finished.444It is possible for the
king to make a capture in the same movement in which it reaches the escape,
but this does not change the number of cases. On the opposite, this
consideration would lower the number of states. This contributes to the final
upper bound with a term

$UB_{\beta}=16\cdot\displaystyle\sum_{b=1}^{16}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{62}^{(b-c,w,62-b-w+c)}\approx 2.3\times 10^{26}$ (8)

The last endgame condition is given by the capture of the king, which could
occur in many different cases. In the following scenarios, the variable $b$
will assume the meaning of the number of black soldiers on the board, that are
not involved in the capture of the king.

  1. 1.

When the king is inside of the castle, 4 black soldiers are necessary to
capture it, therefore those checkers and those cells are determined. The
number of cells which can host any other checker is therefore reduced from 64
to 60, while the highest possible value of $b$ is 12. The contribution of this
case is:

$UB_{\gamma}=\displaystyle\sum_{b=0}^{12}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{60}^{(b-c,w,60-b-w+c)}\approx 2.8\times 10^{22}$ (9)

  2. 2.

When the king is adjacent to the castle (4 possible positions), 3 black
soldiers are necessary to capture it. As for the previous case, the cells
surrounding the king are for sure occupied by 3 black checkers. This reducing
the number of cells to consider to 60 and the highest value of $b$ to 13. The
upper bound is therefore computed as follows:

$UB_{\delta}=4\cdot\displaystyle\sum_{b=0}^{13}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{60}^{(b-c,w,60-b-w+c)}\approx 5.1\times 10^{23}$ (10)

  3. 3.

When the king is adjacent to a camp (12 possible positions), 1 black soldiers
is sufficient to capture it. In 8 case, the capturing checker can be in 2
positions, while in 4 it has to be in a specific position, therefore the
possible scenarios are 20. The highest value of $b$ is 15 and the number of
cells to consider are 62. The possible configurations for this scenario are:

$UB_{\epsilon}=20\cdot\displaystyle\sum_{b=0}^{15}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{62}^{(b-c,w,62-b-w+c)}\approx 8.0\times 10^{25}$ (11)

  4. 4.

Finally, when the king is captured in any other position (28 possible cells),
2 black soldiers are necessary. For any position, there are 2 possible
configurations of black soldiers, so the cases are 56. The highest number of
black soldier on the board not involved in the capture is 14, and the cells to
be taken into account are 61. So the possible configurations for this scenario
are :

$UB_{\zeta}=56\cdot\displaystyle\sum_{b=0}^{14}\displaystyle\sum_{w=0}^{8}\displaystyle\sum_{c=0}^{b}P_{16}^{(c,16-c)}\cdot
P_{61}^{(b-c,w,61-b-w+c)}\approx 1.6\times 10^{26}$ (12)

Taking all these scenarios into account as in Equation 13, the upper bound on
the number of endgame states is $UB_{end}\approx 4.6\times 10^{26}$.

$UB_{end}=UB_{\alpha}+UB_{\beta}+UB_{\gamma}+UB_{\delta}+UB_{\epsilon}+UB_{\zeta}\approx
4.6\times 10^{26}$ (13)

###  3.3 Total State Space

Summing the contribution of Equation 6 and Equation 13, the final upper bound
on the state space is $UB_{end}\approx 1.4\times 10^{27}$:

$UB_{end}=UB_{no_{e}nd}^{\prime}+UB_{end}\approx 1.4\times 10^{27}$ (14)

Taking into account possible endgames given by impossibility to move, or some
other properties, would lead to an improvement of this estimation. For now, it
is fair to assert that would be difficult to find even a weak solution for
this game, since games with a similar state space are still unsolved, as
illustrated in Table 1.

Table 1: Comparison of upper bound on state-space complexity in different board games  | Tablut |  | Nine Men’s
---
Morris
| English
---
Draughts
| International
---
Draughts
Othello | Chess | Go
$UB$ | $1.4\times 10^{27}$ | $3\times 10^{11}$ | $5\times 10^{20}$ | $10^{30}$ | $10^{28}$ |  $10^{43}$, $10^{50}$ | 2 $\times 10^{170}$
Solution | No | Strong | Weak | No | No | No | No
Source |  | [4] | [8] | [1] | [1] | [1] | [9]

##  4 Conclusion and Discussion

For the first time, an upper bound for the state-space complexity of the board
game Tablut has been computed. The game seems to be comparable with the game
of Draughts, therefore finding the strong solution of Tablut would probably
require a great computational effort. Nonetheless, many characteristics of the
game have not been taken into account, therefore it is still possible to
reduce this upper bound. Moreover, since no lower bound has been computed, its
real complexity may be greatly inferior to what has been estimated in this
work.

Due to the separation of the sub-spaces of the game, it is possible to know
which are the scenarios that contribute the most to this upper bound. For what
concerns the non-endgame subspace, they are the cases where the king is not in
the castle. Among the end-game scenarios, they are the scenarios where the
king escapes successfully. Hopefully this initial investigation will encourage
to compute a more accurate evaluation of the complexity of this game and to
find a solution for it.

## References

  * [1] Allis, L.V.: Searching for solutions in games and artificial intelligence. Ph.D. thesis, Maastricht University (1994)
  * [2] Ashton, J.C.: Linnaeus’s game of tablut and its relationship to the ancient viking game hnefatafl. The Heroic Age: A Journal of Early Medieval Northwestern Europe 13, 1526–1867 (2010), https://www.heroicage.org/issues/13/ashton.php
  * [3] Duggan, E.: A game on the edge: an attempt to unravel the gordian knot of tafl games. Discussion paper, University of Suffolk (March 2020), http://oars.uos.ac.uk/1264/
  * [4] Gasser, R.: Solving nine men’s morris. Computational Intelligence 12(1), 24–41 (1996). https://doi.org/10.1111/j.1467-8640.1996.tb00251.x, https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8640.1996.tb00251.x
  * [5] Helmfrid, S.: Hnefatafl — the strategic board game of the vikings (2005)
  * [6] Murray, H.J.R.: A history of chess. Clarendon Press (1913)
  * [7] Murray, H.J.R.: A history of board-games other than chess. Clarendon press (1952)
  * [8] Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., Sutphen, S.: Checkers is solved. Science 317(5844), 1518–1522 (2007). https://doi.org/10.1126/science.1144079, http://science.sciencemag.org/content/317/5844/1518
  * [9] Tromp, J., Farnebäck, G.: Combinatorics of go. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) Computers and Games. pp. 84–99. Springer Berlin Heidelberg, Berlin, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75538-8_8


2019 Extended abstract – MIDL 2019 submission Thomas L. A. van den Heuvel1,2
<EMAIL_ADDRESS>
1 Diagnostic Image Analysis Group, Department of Radiology and Nuclear
Medicine, Radboud University Medical Center, Nijmegen, the Netherlands
2 Medical Ultrasound Imaging Centre, Department of Radiology and Nuclear
Medicine, Radboud University Medical Center, Nijmegen, the Netherlands and
Chris L. de Korte2,3
3 Physics of Fluids Group, MIRA, University of Twente, the Netherlands
Bram van Ginneken1,4
4 Fraunhofer MEVIS, Bremen, Germany

# Automated interpretation of prenatal ultrasound using a predefined
acquisition protocol in resource-limited countries

###### Abstract

In this study, we combine a standardized acquisition protocol with image
analysis algorithms to investigate if it is possible to automatically detect
maternal risk factors without a trained sonographer. The standardized
acquisition protocol can be taught to any health care worker within two hours.
This protocol was acquired from 280 pregnant women at St. Luke’s Catholic
Hospital, Wolisso, Ethiopia. A VGG-like network was used to perform a frame
classification for each frame within the acquired ultrasound data. This frame
classification was used to automatically determine the number of fetuses and
the fetal presentation. A U-net was trained to measure the fetal head
circumference in all frames in which the VGG-like network detected a fetal
head. This head circumference was used to estimate the gestational age. The
results show that it possible automatically determine gestational age and
determine fetal presentation and the potential to detect twin pregnancies
using the standardized acquisition protocol.

###### keywords:

Prenatal, Ultrasound, Deep Learning, Resource-limited countries

##  1 Introduction

World Health Organization et al. (2014) reported that 99% of all maternal
deaths occur in resource-limited countries. This corresponds to more than 800
women that die each day as a consequence of their pregnancy. Ultrasound
imaging is widely used to detect maternal risk factors during the pregnancy.
Unfortunately, ultrasound imaging remains often out of reach for pregnant
women in resource-limited countries, since there is a lack of trained
sonographers that can acquire and interpret the images. DeStigter et al.
(2011) have introduced the obstetric sweep protocol (OSP). Figure
LABEL:fig:resultFrameClassification.A shows the OSP, which consists of six
predefined free-hand sweeps over the abdomen of the pregnant women. The OSP
can be taught to any health care worker within two hours, which obviates the
need to extensively train sonographers for months. In this work we
investigated if it was possible to automatically determine the number of
fetuses, estimate gestational age (GA) and determine fetal presentation using
the OSP.

##  2 Methods

###  2.1 Data acquisition

The OSP was acquired from 280 pregnant women in Wolisso, Ethiopia. This data
represents the target population of our research, since Ethiopia still has a
high maternal mortality ratio World Health Organization et al. (2014). A
gynecologist determined the number of fetuses and measured the reference fetal
head circumference (HC) in the standard plane. This reference HC was used to
obtained the reference GA for each single pregnancy. The gynecologist also
determined for all single pregnancies if the fetus lay in cephalic or breech
presentation.

###  2.2 Automated interpretation

The automated interpretation of the OSP data consists of five steps:
First, a deep learning network, inspired on the VGG-net of Simonyan and
Zisserman (2014), was trained to classify which frames within the OSP data
present the fetal head, the fetal torso in the transverse direction, the fetus
in sagittal direction and when the transducer was detached from the abdomen of
the pregnant women in between the six sweeps van den Heuvel et al. (2019).
Secondly, the frames in which the transducer was detached from the abdomen
were used to automatically separate the six sweeps. Each sweep was resampled
to 100 frames per sweep using nearest neighbor interpolation.
Thirdly, a Random Forest classifier (RFC) Breiman (2001) was used to determine
the number of fetuses using the frame classification of the six separated
sweeps.
Fourthly, a second deep learning system, inspired on the U-net of Ronneberger
et al. (2015), was trained to measure the HC in all frames in which the first
deep learning system has detected a fetal head completely present. Since the
HC measured in the standard plane is on of the largest circumference one can
measure from the fetal head, the 75th percentile of all estimated HCs was used
as the final HC. The curve of Hadlock et al. (1984) was used to determine the
GA from the automatically estimated HC.
Finally, a second RFC was used to determine fetal presentation using the frame
classification of the six separated sweeps.
All systems were trained using a five-fold cross-validation.

##  3 Results

The data included a total of 247 single and 33 twin pregnancies for which the
result of the automated system is shown in Table 2. The reference HC
measurement was not acquired from 7 single pregnancies and 15 of the HCs fell
outside the limits of the Hadlock curve, so a total of 225 GAs were included.
The median difference between the reference GA measured in the standard plane
and the automatically estimated GA measured from the OSP data was -0.4 days
with an interquartile range (IQR) of 15.2 days. The median difference was -0.4
with an IQR of 9.3 days in the second trimester (14 weeks until 28 weeks of
gestation). The 247 single pregnancies contained 216 fetuses in cephalic
presentation and 31 fetuses in breech presentation. Table 2 shows the results
of the automated detected presentation. Figure
LABEL:fig:resultFrameClassification.B shows an example of a fetus in breech
presentation. The frame classification shows that that the fetal head (blue)
lies above the fetal torso (green).

Table 1: Results for number of fetuses No. fetuses | Correct | Incorrect
---|---|---
Single | 244 | 3
Twin | 20 | 13

Table 2: Results for fetal presentation Presentation | Correct | Incorrect
---|---|---
Cephalic | 215 | 1
Breech | 31 | 0

##  4 Discussion

In this work we combined the OSP with automated image analysis to
automatically interpret the ultrasound data, with the aim to obviate the need
for a trained sonographer.
The results show that it possible automatically determine gestational age with
a IQR of 9.3 days in the second trimester, which could be used to indicate in
which week the health care worker should send the pregnant women to a health
care facility when a maternal risk factor is detected. This is very important
in resource-limited settings, since it can take more than one day for a
pregnant woman to reach a hospital.
Table 2 shows that all breech presentations were correctly detected and 99.5%
of the fetuses in cephalic presentation were correctly detected. When taking
into account that 33 of the 247 single pregnancies showed some kind of
abnormality, we conclude that the system is able to robustly determine the
fetal presentation. The system could therefore give health care workers the
option to refer a fetus in breech presentation to a health care facility.
Table 2 shows that 98.8% of all single pregnancies were correctly detected.
The system only detected 60.6% of all twin pregnancies, because the system was
not able to detect twins that lie in the same presentation (e.g. both
cephalic). This shows potential to detect twin pregnancies, but it leaves room
for improvement in the future.

fig:resultFrameClassification

Figure 1: A. Visualization of the six sweeps of the obstetric sweep protocol.
B. Result of the frame classification, showing a fetus in breech presentation.

We thank Dr. Hezkiel Petros and Dr. Stefano Santini from St. Luke’s Catholic
Hospital for their help with the acquisition of the ultrasound data that was
used in this study.

## References

  * Breiman (2001) L. Breiman.  Random forests.  _Machine Learning_ , 45(1):5–32, 2001.  ISSN 0885-6125.
  * DeStigter et al. (2011) K. K. DeStigter, G. E. Morey, B. S. Garra, M. R. Rielly, M. E. Anderson, M. G. Kawooya, A. Matovu, and F. R. Miele.  Low-cost teleradiology for rural ultrasound.  In _IEEE Global Humanitarian Technology Conference_ , pages 290–295, 2011.  10.1109/ghtc.2011.39.
  * Hadlock et al. (1984) F. P. Hadlock, R. L. Deter, R. B. Harrist, and S. K. Park.  Estimating fetal age: computer-assisted analysis of multiple fetal growth parameters.  _Radiology_ , 152(2):497–501, 1984.  10.1148/radiology.152.2.6739822.
  * Ronneberger et al. (2015) O. Ronneberger, P. Fischer, and T. Brox.  U-Net: Convolutional networks for biomedical image segmentation.  volume 9351, pages 234–241, 2015.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.  URL http://arxiv.org/abs/1409.1556.
  * van den Heuvel et al. (2019) Thomas L A van den Heuvel, Hezkiel Petros, Stefano Santini, Chris L de Korte, and Bram van Ginneken.  Automated fetal head detection and circumference estimation from free-hand ultrasound sweeps using deep learning in resource-limited countries.  45(3):773–785, 2019.  10.1016/j.ultrasmedbio.2018.09.015.
  * World Health Organization et al. (2014) World Health Organization, UNICEF, UNFPA, The World Bank, and the United Nations Population Division.  Trends in maternal mortality: 1990 to 2013: estimates by WHO, UNICEF, UNFPA, The World Bank and the United Nations Population Division.  2014\.