Keywords

Reach mahjong (or riichi mahjong) is a gambling game for 4 players. A game (or hanchan) is played over several rounds. In each round, players seated at a table sequentially draw and discard tiles in an attempt to form a winning hand of 14 tiles. At the end of the round, the losing players pay a number of points to the winner, according to the value of his hand. The player with the most points at the end of the game is the winner.

Reach mahjong is most popular in Japan, although it is played throughout the world. In Europe, a few hundred amateur players compete in tournaments arranged throughout the year and around the continent. Tournaments are typically organised locally, but run following rules published by the European Mahjong Association (EMA) [1], which has approved and ranked tournaments since 2008. This raises the question of how best to schedule games in a tournament.

We report on our experience of using the pseudoboolean (PB) solver clasp [8] to generate tournament schedules (such as Table 1) for tournaments run in the United Kingdom since 2013. This includes generating a schedule for 128 players over 10 sessions for the 2016 European Riichi Mahjong Championship (ERMC), which satisfied a complex combination of constraints. Our software CoMaToSe (Constraint Mahjong Tournament Scheduler) and benchmarks are online [13].

In Sect. 1 we describe some details of the tournament scheduling problem and the constraints that they lead to. Then, in Sect. 2, we describe how we encode those constraints. The scheduling problem is essentially an extension of the Social Golfer Problem (SGP), which is amenable to solution using SAT solvers [9, 12], but we found that for larger tournaments, and with our extended set of constraints, a PB formulation was more tractable. To our knowledge, there is no previous published work considering mahjong tournament scheduling; our encoding of the constraints extending the SGP is original. We evaluate our approach in Sect. 3. Finally, in Sect. 4 we discuss related work on the SGP, and more generally on tournament scheduling for games with more than 2 players, before concluding.

1 Problem Description

Size, length and format. A number of practical constraints and conventions have arisen over time that essentially fix the format of a tournament. Tournaments typically take place at the weekend, so usually last 1–2 days. Players may travel to a tournament and expect to play throughout; tournament rules specify that all players should play the same number of games and, after adding up each player’s score in every game, the player with the highest score should be the winner. Games are played to a time limit in a session of 90 min. Allowing time for breaks and so on, it is usual to have 3–5 sessions in a day, for a total of 4–10 sessions in a tournament. A 2-day tournament might typically attract around 48 players. Every 3 years, a European Championship (ERMC) is held, which lasts longer and attracts more players. The main phase of the 2016 championship in the UK had 128 players over 10 sessions; the 2019 championship in the Netherlands had 140 players over 12 sessions. A tournament venue usually has enough tables and equipment to allow all participants to play simultaneously, although this may be variable in quality.

Table 1. A tournament schedule for 24 players and 5 sessions (SGP 6-4-5) with \(d=10\).
Full size table

Wind Allocation. During each round, each player is allocated a different compass point (East, South, West or North) as his wind. The East player is the dealer. When he wins, he gets 50% more points and stays as dealer for the next round. If he does not win, the wind allocations rotate. He becomes North for the next round, the South player becomes East, and so on. In a full game, each player gets to be East twice; being North initially (and hence East last) may be an advantage because it confers some control over when the game ends. However, if a game is curtailed because of a tournament time limit, being North or West initially puts one at a disadvantage, as one often misses a second turn as dealer.

The core problem is thus how best to schedule 4–12 sessions of a 4-player game for 16–140 players. Initial wind allocations for a table can be included in the schedule, or they can be drawn at random by the players before the game. Players might feel aggrieved if they have a disadvantageous wind allocation, even if it was produced at random. Balanced allocation of winds in the schedule avoids this and reduces setup time at the start of the game.

1.1 Constraints

The following have been suggested as desirable properties in a schedule:

  • Socialisation: Players want to play as many different opponents as possible.

  • Wind balance: In order to share the potential penalty of not getting a second turn as dealer across all players, each player should be allocated each starting wind position roughly an equal number of times. Obviously, this is not possible when the number of sessions is not a multiple of 4 and even then, it may not always be possible.

  • Table movement: To reduce the chances of cheating, and to share the inconvenience of playing on a table with low-quality equipment, a player should not play on the same table twice.

Of these, most players consider socialisation most important. With just this requirement, tournament scheduling is an instance of the well-studied SGP. With the relatively low ratio of players to sessions in many tournaments, satisfying just this requirement leaves relatively little scope for changing who plays who in each round. However, in larger tournaments, we may also wish to consider what properties are desirable in the tournament graph of “who plays who”. Intuitively, we can view a tournament as a process by which points flow along edges from losing players to winning players. We then expect that the final scores of players are indicative of a linear ordering of their skill, but this depends on there being adequate potential for points to flow between any two players. This leads to the following desirable properties of the tournament graph:

  • Graph connectedness: The tournament graph should be connected.

  • Graph diameter: The diameter of the tournament graph (greatest distance between any pair of players) of the tournament should be as low as possible. In our setting, this usually means 2. This is a stronger version of the requirement that the graph be connected, with the same motivation. If two players cannot face each other directly, points can still flow between them via other players, but we would like the route to be as short as possible.

  • Multiple short paths: If two players in the tournament graph are not adjacent, there should be multiple paths between them, ideally of length 2. This increases the potential for indirect flow of points between them.

For a tournament graph with diameter 2, we will refer to the minimum number of paths of length 2 between any two non-adjacent players in the tournament graph as d. Necessarily, \(d \ge 1\). For the schedule in Table 1, we used graph constraints to enforce \(d=10\); prior to this, the schedule had \(d=9\).

2 Problem Encoding

As the most important constraint is socialisation, we start with a PB encoding for the SGP, then add our other constraints in a monolithic formulation. By convention, we refer to an SGP instance as g-p-w with:

  • g — the number of groups playing simultaneously

  • p — the number of players in a group (always 4 for mahjong)

  • w — the number of sessions (weeks in the SGP)

We chose our solver by evaluating participants in the SAT and PB [4] competitions of 2012, which were the most recent competitions at the time. Of these, we found that clasp [8] was most effective, particularly when run with the crafty preset for combinatorially hard problems.

Initially, we had focused on the use of SAT, as Triska had developed an effective SAT encoding of the SGP [18]. However, his socialisation constraint is \(\mathcal {O}(g^4 p^2 w^2)\). For large numbers of players, we found that just generating the constraints was too slow, so starting with the 2016 European Championship (SGP 32-4-10), we adopted a PB formulation.

We had assumed that, while a PB might not find an optimal solution, if it ceased to make progress, it would at least have found a locally optimal solution. However, a tournament organiser told us he had been able to improve wind balance in a generated schedule by shuffling wind allocations of two tables. We found that, using an encoding that considered only wind balance, we could fine-tune the schedule generated from the monolithic encoding and automate this.

Although the SAT/PB method for solving SGP instances is competitive, the best automated method currently known is Triska’s heuristic-guided local search algorithm [17]; an implementation by Rezaei is available online [15]. Therefore, for tournament schedules that correspond to hard instances of the SGP, we can import a solution to the SGP instance and just tune the wind balance. While fixing group allocations in this way may remove the best solutions from the space considered by the solver, in practice it allows us to find better solutions than using a constraint solver in isolation. In all cases we considered, we were able to find an optimal wind allocation this way.

2.1 Monolithic Constraint Encoding

We now present our monolithic PB constraint encoding of the problem. We set \(n = g . p\) as the number of players. The constraints range over the following Boolean variables, where \(h,i,j \in [1,n]\) with \(j > i\), \(h \ne i\) and \(h \ne j\), \(k \in [1,g]\), \(l \in [1,w]\) and \(s \in [1,p]\):

  • \(P_{i,k,l}\) — true just if i plays in group k in session l

  • \(S_{i,k,l,s}\) — true just if i plays in group k in session l in seat position s

  • \(M_{i,j,l}\) — true if i and j meet in session l

  • \(C_{i,j}\) — true only if i and j meet (compete) in any session

  • \(D_{i,j,h}\) — true only if i and j both meet h (compete indirectly)

We encode East as position 1, South as 2 and so on. Constraint sets are as follows; quantification (\(\forall \), \(\sum \)) of indices is always implicitly over the ranges above.

Each group must have exactly p players:

$$\begin{aligned} \forall k, l . \textstyle \sum \nolimits _i P_{i,k,l} = p \end{aligned}$$
(1)

Each player must play in exactly one group in each session:

$$\begin{aligned} \forall i, l . \textstyle \sum \nolimits _k P_{i,k,l} = 1 \end{aligned}$$
(2)

Optionally, to break symmetries, order players sequentially in the first session:

$$\begin{aligned} \forall i . P_{i,\lceil i / g \rceil , 1} = 1 \end{aligned}$$
(3)

If i and j play in the same group in the same session, then they must meet in that session:

$$\begin{aligned} \forall i, j, k, l . {-P}_{i,k,l} + {-P}_{j,k,l} + M_{i,j,l} \ge -1 \end{aligned}$$
(4)

and they must meet at most once over all sessions:

$$\begin{aligned} \forall i, j . \textstyle \sum \nolimits _l {-M}_{i,j,l} \ge -1 \end{aligned}$$
(5)

i and j competed only if they played in the same group in any session:

$$\begin{aligned} \forall i, j . {-C}_{i,j} + \textstyle \sum \nolimits _{k,l} P_{i,k,l} P_{j,k,l} \ge 0 \end{aligned}$$
(6)

i and j competed indirectly via h only if they both competed with h:

$$\begin{aligned} \forall i, j, h . C_{\min (i,h), \max (i,h)} + C_{\min (h,j), \max (h,j)} + {-2D}_{i,j,h} \ge 0 \end{aligned}$$
(7)

i and j must compete directly, or compete indirectly d times (d configurable):

$$\begin{aligned} \forall i, j . d \cdot C_{i,j} + \textstyle \sum \nolimits _h D_{i,j,h} \ge d \end{aligned}$$
(8)

Each player must play in each group at most once over all sessions:

$$\begin{aligned} \forall i, k . \textstyle \sum \nolimits _l {-P}_{i,k,l} \ge -1 \end{aligned}$$
(9)

If i sits in a position in a group, he must play in that group:

$$\begin{aligned} \forall i, k, l, s . {-S}_{i,k,l,s} + P_{i,k,l} \ge 0 \end{aligned}$$
(10)

If i plays in a group, he must sit in one of its positions:

$$\begin{aligned} \forall i, k, l . {-P}_{i,k,l} + \textstyle \sum \nolimits _s S_{i,k,l,s} \ge 0 \end{aligned}$$
(11)

Exactly one player must sit in every seat:

$$\begin{aligned} \forall k, l, s . \textstyle \sum \nolimits _i S_{i,k,l,s} = 1 \end{aligned}$$
(12)

Each player must play in each position (roughly) the same number of times:

$$\begin{aligned} \begin{array}{ccc} \forall i, s . \textstyle \sum \nolimits _{k,l} S_{i,k,l,s} \ge \lfloor w / p \rfloor&\qquad&\forall i, s . \textstyle \sum \nolimits _{k,l} {-S}_{i,k,l,s} \ge - \lceil w / p \rceil \end{array} \end{aligned}$$
(13)

Constraints 1–5 follow Walser [20]; the rest are original. The constraint sets are largely orthogonal: any of 4–5 (socialisation), 6–8 (enforcing d), 9 (table movement) and 10–13 (wind balance) can be removed independently. Note constraints 6 are non-linear. Concerning size: 4–5 is \(\mathcal {O}(g^2 p^2 w)\) (\(\mathcal {O}(g^2 w)\) smaller than Triska’s SAT encoding); 6–8 is \(\mathcal {O}(g^3 p^3)\); 10–13 is \(\mathcal {O}(g^2 p^2 w)\).

In practice, it may not always be possible to satisfy all constraints simultaneously, whether because there is no solution, or because the solver cannot find one. In these cases, constraint sets 5, 8, 9 or 13 can be made soft, turning the problem into a Weighted Boolean Optimisation (WBO) instance.

Apart from the obvious symmetry breaking of fully specifying session 1, most existing symmetry breaking techniques for the SGP violate the extra constraints in our problem. For example, putting players 1–4 on tables 1–4 in later rounds, or requiring that the tables are ordered by lowest numbered player on the table, violates table movement. Formulations of the pure SGP that encode a table as an ordered list usually benefit from breaking symmetry in the ordering of players. In the PB formulation, native cardinality constraints make it easy to encode a table as an unordered set, so there is no symmetry to break. Of course, when one adds wind allocation, ordering of players at a table is no longer a symmetry.

2.2 Wind Balancing Constraint Encoding

Our constraint encoding for fine-tuning wind allocations uses variables \(W_{i,l,s}\), which are true just if player i is in position s in session l. The constraints depend on a fixed allocation of players to groups, which we refer to using values of P variables from the monolithic encoding; tuning can only change a player’s seat at a table. Our encoding is as follows. Each player must have a seat:

$$\begin{aligned} \forall i, l . \textstyle \sum \nolimits _s W_{i,l,s} = 1 \end{aligned}$$
(14)

Exactly one player in a group can take each seat:

$$\begin{aligned} \forall k, l, s . \textstyle \sum \nolimits _{\{ i \mid P_{i,k,l} \}} W_{i,l,s} = 1 \end{aligned}$$
(15)

Each player must play in each position (roughly) the same number of times:

$$\begin{aligned} \begin{array}{ccc} \forall i, s. \textstyle \sum \nolimits _l W_{i,l,s} \ge \lfloor w / p \rfloor&\qquad \forall i, s. \textstyle \sum \nolimits _l {-W}_{i,l,s} \ge - \lceil w / p \rceil \end{array} \end{aligned}$$
(16)
Table 2. Benchmarks applying monolithic encoding to 2-day tournaments (g-4-8).
Full size table

3 Evaluation

We have used our encoding to generate schedules for the 2016 ERMC and several smaller tournaments in the UK. Timings were generated on a machine running Debian Linux 10 with a 3.4 GHz Intel Core i5-7500 CPU and 64 GB of RAM. We used clasp 3.3.4 with crafty preset and Rezaei’s local search SGP solver [15].

For the 2016 ERMC (32-4-10), we used our monolithic encoding, incrementally turning on constraints to obtain the best schedule possible. Enforcing just socialisation took 18 s. We turned on table movement and wind balance, tightening the wind constraints (13) to give each player 2 turns in each seat plus 1 turn as East or South and 1 turn as West or North; solving this took 2 m 10 s. The schedule’s tournament graph already had diameter 2, but \(d=1\). Adding the constraint \(d=2\), it took 14 m to solve. Changing to \(d=3\), clasp found no solution in 1 h. So finally, keeping the hard constraint \(d=2\) and adding a soft constraint \(d=3\), with a timeout of 1 h, we generated a schedule violating only 122 of \(\left( {\begin{array}{c}128\\ 2\end{array}}\right) = 8128\) soft constraints. Overall, the instance had 1.3M variables and 3.9M constraints. Appendix A shows benchmarks for similar instances.

Table 3. Comparison of NLC WBO solvers. Constraints violated after 10 m (g-4-8).
Full size table

For comparison, solving the SGP instance with local search and balancing the winds using our constraint formulation yielded a solution in less than 1s. The tournament graph had diameter 2, but with \(d=1\), and there is no easy way to tune the graph while maintaining socialisation.

For the smaller tournaments, the tournament graph was necessarily low diameter, so we did not enforce it with constraints. 1-day tournaments usually had 5 sessions and ranged from 24 to 52 players (6-4-5 to 13-4-5). 2-day tournaments usually had 8 sessions and ranged from 32 to 68 players (8-4-8 to 17-4-8). We benchmarked our monolithic encoding on these intervals, setting a solver time limit of 10m and making wind balance a soft constraint. For instances in the 1-day interval, it took less than 0.5 s to solve constraints for a schedule with maximal socialisation, table movement and wind balance, except for 6-4-5, which took 3.6 s. For the 2-day interval (see Table 2), the 8-4-8 instance is significant as it is the original formulation of the SGP, and remains out of reach for SAT- and PB-based methods, including ours, so we imported a solution to balance. For 9-4-8 and 10-4-8, clasp solved the constraints only with wind balance turned off. For the rest of the interval, clasp found solutions with 2–21 wind constraint violations. In all cases, whether using schedules generated by our monolithic encoding, or importing schedules generated by local search, we were able to tune wind balance perfectly, satisfying all constraints, usually in under 2 s.

To confirm that clasp was still an appropriate choice of solver, we compared up-to-date versions of entrants in the relevant track (WBO SOFT-SMALLINT-NLC) of the most recent PB Competition (2016), as well as experimental versions of SAT4J using the cutting planes and rounding SAT techniques. Table 3 shows the comparison. Although the standard SAT4J solver is competitive, clasp is still best. Some new PB solvers have participated in the more active MaxSAT Evaluation competition, but none supports WBO with non-linear clauses.

Summary: For large instances, where the tournament graph structure was of concern, our monolithic constraint encoding allowed the graph to be optimised at the same time as allocating wind positions. For hard SGP instances, we necessarily had to import an SGP solution, but our wind encoding successfully tuned this. In other cases, there was little difference between the quality of schedules generated: using our monolithic encoding, then tuning wind allocations if necessary; and using a local search SGP solver, followed by tuning wind allocation. However, the latter was considerably faster.

4 Related Work and Conclusions

The SGP was posted on the Usenet group sci.op-research in 1998. The original SGP, to find the highest w for which 8-4-w is solvable, is problem 10 in CSPLib [10]. Optimal solutions of the SGP are entry A107431 in OEIS [2]. Walser suggested a PB encoding [20]. Later, Gent and Lynce proposed a SAT encoding [9]. Much work on solving SGP instances focuses on breaking symmetries [3, 6, 7, 11]. Triska studied the problem extensively [16,17,18].

Recently, Lardeux and others revisited the SAT encoding, exploring efficient, correct translation of set constraints [12]; they seem unaware of PB problems/solvers. Liu and others investigated solving SGP instances in parallel [14].

We found no previous research specifically on scheduling a mahjong tournament. Bridge and whist are 4-player games, but played by 2 co-operating pairs, not 4 competing individuals. Individual bridge tournaments [19] were played in the past, but are currently not popular. Whist games are shorter than mahjong games, and partnership is still significant, which leads to different goals [5].

We have shown how to generate good tournament schedules for reach mahjong tournaments run according to the conventions of the European Mahjong Association. Since 2013, our approach has been used to generate schedules for several tournaments hosted in the UK, including the 2016 ERMC. Our experience reaffirms the message that SAT/PB solvers are an effective and convenient but imperfect tool for solving complex problems that arise in real life. We think it is likely that a custom local search algorithm that considered all our constraints simultaneously would outperform our approach. However, this would have been far less convenient than applying an existing solver.