IOAI Training: Learn AI by solving problems

The problem in brief

You play one seat in a dominoes game in the style of Mexican Train, against $N-1$ opponents who choose uniformly at random among their legal moves. Every player owns a private track, there is one shared side track, and doubles force the next player to answer on the same track. A player who cannot play draws a tile and their private track becomes open to everyone. The game stops when someone empties their hand or when nobody can move, and the player holding the fewest pips wins. You have one special power: after each move you may force any opponent to exchange one of your tiles (your choice) for one of theirs (random). Your program talks to the judge through standard input and output, with a 1 second time limit.

This is not a machine learning task in the usual sense: there is no data, and the opponents are known to be random. It is a lesson in decision making under uncertainty: estimate what is hidden, and pick the action with the best expected effect.

How you are scored

After each game, your percentile $p$ is your rank among the players by remaining pips (0 when nobody has fewer pips than you). The game is worth

\text{Score}(p) = \min\Big(100,\ 100\Big(1-\Big(\frac{\log(1000p+1)}{\log 1001}\Big)^{0.8}\Big)\Big).

The logarithm makes this formula brutally steep:

$p$	0 (best)	1/8	1/4	1/3	1/2	1
score	100	24.8	16.4	12.9	8.1	0

Finishing second out of three already drops you from 100 to about 13. So the objective is, in practice, maximise the probability of finishing with the lowest pip count; the mean score is roughly the win rate plus a little. The statement gives no threshold. The organisers ship a local tester (random-judge.cpp) and a baseline that plays the first legal move and almost never swaps; we use it as the reference. Group 1 uses $M=9$ , $S=6$ ; the other parameters of group 2 are not public, so we test several settings.

One honest caveat: the exact definition of "percentile" is not spelled out. We use $p = \#\{\text{opponents with strictly fewer pips}\}/N$ , which gives 100 to a winner (ties included).

First look at the game

Before writing any strategy, we ported the organisers' judge to Python (same rules, same random opponents) so that thousands of games can be simulated in seconds, and we checked our final program against the original C++ judge as well. A few facts come out of reading the rules carefully:

Pips only hurt if they are still in your hand at the end. A tile you play is gone, whatever its value.
The game often ends early, when a random opponent empties their hand. You do not control the end, so your hand should be light at every moment, not only at the end.
A turn where you cannot play costs twice: you do not shed a tile, and you draw one (plus your track opens to everybody).
The swap is very cheap and very powerful. You give a tile you choose and receive a tile chosen at random from the opponent. If you give your heaviest tile, you receive on average a typical tile, which is lighter.

A first baseline

The organisers' baseline plays the first legal move in the list. Over 1000 simulated games per setting it wins 30 to 38 % of the games with 3 or 4 players, and its mean score is 36 to 44 (table below). A first obvious improvement, "play the heaviest legal tile", only adds 3 to 8 points: shedding pips one tile at a time is slow, because you can only play one tile per turn anyway.

The key idea

Two decisions are made every turn, and each has a clean expected-value argument.

1. The swap: give away your heaviest tile, to the right opponent. Let $d$ be the tile you give and $r$ the random tile you get back from opponent $q$ . Your pip count changes by $\text{pips}(r) - \text{pips}(d)$ , whose expectation is

\mathbb{E}[\Delta] = \mathbb{E}[\text{pips}(r)] - \text{pips}(d) = \mu_q - \text{pips}(d),

where $\mu_q$ is the mean pip value of $q$ 's hand. Two consequences:

Give the heaviest tile you can spare: it makes $\text{pips}(d)$ as large as possible.
Choose the opponent with the smallest $\mu_q$ . We cannot see their hands, but we know a lot: every tile on the table, every tile in our hand, how many tiles each opponent holds (start with $S$ , minus one per move, plus one per draw while the pile is not empty) and, crucially, which heavy tiles we already pushed into whose hand. Our estimate is

\hat\mu_q = \frac{\sum_{t \in G_q}\text{pips}(t) + (h_q - |G_q|)\,\bar u}{h_q},

where $G_q$ is the set of our former tiles that $q$ still holds, $h_q$ its hand size and $\bar u$ the mean pip value of the tiles we have never seen. Without this bookkeeping you keep swapping with the same player and receive your own heavy tiles back.

A swap does not change the number of tiles you hold, but in a game where the end time is random, lowering the weight of your hand at every turn is exactly what wins.

2. The move: stay playable. Since a blocked turn costs a draw, the most valuable property of a move is that you will still be able to move next turn. Before playing, we simulate each legal move one step ahead and ask: will one of my remaining tiles match the new end of my own track (which only I can change while it is closed)? And the end of the shared track? The move value is

V(m) = \alpha\,[\text{own track still playable}] + \tfrac{\alpha}{2}\,[\text{shared track still playable}] + \text{pips}(m),

with $\alpha = 25$ , larger than any tile, so playability comes first and pips break ties. The swap is coordinated with this: the tile we give away is the heaviest one that is not the one keeping our own track alive.

The full solution

solution.py reads only what the judge sends and reconstructs the table itself:

All tracks start at value $M$ (track $N$ is the shared one). Every move we see, ours or an opponent's, updates the track end: a double $(x,x)$ sets it to $x$ , a tile $(x,y)$ placed on end $x$ sets it to $y$ .
It counts the pile and the opponents' hand sizes (a " $-1$ " line means that player drew a tile if the pile was not empty).
For each legal move it evaluates $V(m)$ and plays the best one.
It then estimates $\hat\mu_q$ for every opponent, picks the lightest-handed one and the heaviest spare tile, and prints SWAP q a b.
When no move is possible it reads the drawn tile and answers -1, as in the sample interaction.

The core of the move choice:

def value(m):
    s, a, b = m
    rest = [d for d in hand if d != (min(a, b), max(a, b))]
    new = {tr: ends[tr] for tr in (0, N)}            # our track and the shared one
    if s in new:
        new[s] = a if a == b else (b if a == ends[s] else a)
    own = any(new[0] in d for d in rest)
    shared = any(new[N] in d for d in rest)
    return ALPHA * own + 0.5 * ALPHA * shared + a + b

Each turn costs a few hundred operations, far below the 1 second limit (a whole game takes about 0.03 s including process overhead). Played against the organisers' own random-judge.cpp on 60 seeds per setting, the program never made an invalid move, scoring 61.7 ( $N=3, M=9, S=6$ ) and 57.3 ( $N=4, M=12, S=8$ ), against 45.2 and 37.0 for the official baseline.

Results

Mean score per game (and win rate) over 1000 simulated games per setting, with our Python port of the judge:

approach	N=3, M=9, S=6	N=4, M=12, S=8	N=6, M=12, S=8	N=3, M=12, S=15
baseline: first legal move	42.8 (37 %)	36.5 (30 %)	27.2 (19 %)	43.6 (38 %)
heaviest legal tile	45.7 (40 %)	40.6 (33 %)	32.5 (23 %)	51.2 (46 %)
heaviest tile + swap heaviest tile	56.2 (52 %)	48.7 (42 %)	36.3 (26 %)	63.6 (59 %)
lookahead move, no swap	52.8 (48 %)	43.7 (37 %)	37.0 (29 %)	57.4 (53 %)
lookahead move + smart swap (final)	62.3 (58 %)	54.9 (49 %)	43.9 (35 %)	71.1 (68 %)
failed idea: plan the longest chain for our track + swap	57.3 (53 %)	48.9 (42 %)	38.4 (29 %)	62.4 (58 %)

Grouped bar chart of the mean score of six strategies in four game settings. The final strategy (lookahead plus swap) is the best everywhere, around 20 points above the baseline; the swap alone and the lookahead alone each give about half of the gain.

What the table teaches:

Swap and lookahead are complementary: each alone gives roughly half of the gain, together about +18 to +28 points over the baseline.
The "longest chain" plan failed. It is the classic advice for human Mexican Train (save a long sequence for your own track and spend other tiles elsewhere), but here it loses to the one-step lookahead. Against random opponents who rarely block you on purpose, a long-term plan is less useful than staying flexible, and keeping chain tiles in hand means holding pips longer.
Wins get harder with more players (more chances that a random opponent empties their hand first), which no strategy can fully prevent.

What to remember

Read the scoring formula first and translate it into an objective. Here the log makes the score almost binary: only finishing first really counts.
Build a simulator of the environment (here a 60-line port of the official judge). It turns opinions about strategy into numbers, with thousands of games in seconds.
Expected value drives every decision: giving tile $d$ and receiving a random tile changes your hand by $\mu_q - \text{pips}(d)$ on average, so give your heaviest tile to the opponent with the lightest expected hand.
Track the hidden state from what you observe (track ends, hand sizes, where your tiles went). Belief tracking is what makes "the lightest opponent" estimable.
Test the textbook strategy, do not assume it: the human-expert "longest chain" heuristic was worse than a simple one-step lookahead in this environment.

"""SAIO "Jumex-train": an agent for the modified Mexican Train game.

Strategy (see correction.md):
  1. Track the whole table from the interaction alone: the open end of every track
     (all start at M), which tiles were played, how many tiles each opponent holds,
     and which of our tiles we have pushed into each opponent's hand by swapping.
  2. Move choice: among legal moves, prefer the one after which we can still play
     on our own track next turn (and, less, on the shared track); break ties by
     playing the heaviest tile (pips only count if they stay in our hand).
  3. Swap after every move: hand over our heaviest tile that is not needed to keep
     our own track playable, to the opponent whose hand has the lowest expected
     pip value (we know which heavy tiles we already gave to whom).
After a pass we answer with a bare "-1", as in the sample interaction.
"""
import sys

ALPHA = 25.0          # weight of "still playable on our track" vs pips


def main():
    data = sys.stdin
    rd = lambda: data.readline().split()
    N, M, S = map(int, rd())
    ends = [M] * (N + 1)                  # track N is the shared side track
    seen = set()                          # tiles on the table
    count = [S] * N                       # hand sizes
    pile = (M + 1) * (M + 2) // 2 - 1 - N * S
    given = {p: [] for p in range(1, N)}  # our tiles known to sit in p's hand

    def apply(track, a, b):
        t = (min(a, b), max(a, b))
        seen.add(t)
        e = ends[track]
        ends[track] = a if a == b else (b if a == e else a)
        return t

    def unknown_mean(hand):
        known = seen | set(hand) | {d for v in given.values() for d in v}
        u = [i + j for i in range(M + 1) for j in range(i, M + 1)
             if not (i == j == M) and (i, j) not in known]
        return sum(u) / len(u) if u else M

    while True:
        line = rd()
        if not line or int(line[0]) == -2:
            return
        moves = [tuple(map(int, rd())) for _ in range(int(line[0]))]
        hand = [tuple(sorted(map(int, rd()))) for _ in range(int(rd()[0]))]

        if not moves:                                 # we must draw
            drawn = rd()                              # the drawn tile (or -1 -1)
            if pile:
                pile -= 1
            print("-1", flush=True)
        else:
            def value(m):
                s, a, b = m
                t = (min(a, b), max(a, b))
                rest = [d for d in hand if d != t]
                new = dict((tr, ends[tr]) for tr in (0, N))
                if s in new:
                    new[s] = a if a == b else (b if a == ends[s] else a)
                own = any(new[0] in d for d in rest)
                shared = any(new[N] in d for d in rest)
                return ALPHA * own + 0.5 * ALPHA * shared + a + b
            s, a, b = max(moves, key=value)
            t = apply(s, a, b)
            hand.remove(t)
            count[0] -= 1
            out = [f"{s} {a} {b}"]
            # ---- swap: dump the heaviest tile we do not need for our own track
            mu = unknown_mean(hand)
            best_p, best_e = None, 1e9
            for p in range(1, N):
                h = count[p]
                if h <= 0:
                    continue
                k = given[p]
                e = (sum(x + y for x, y in k) + (h - len(k)) * mu) / h if h >= len(k) else mu
                if e < best_e:
                    best_p, best_e = p, e
            if hand and best_p is not None:
                d = max(hand, key=lambda x: x[0] + x[1] - (ALPHA if ends[0] in x else 0))
                out.append(f"SWAP {best_p} {d[0]} {d[1]}")
                given[best_p].append(d)   # we do not learn which tile we receive
            else:                         # until the next hand listing, see below
                out.append("NO-SWAP")
            print("\n".join(out), flush=True)

        # ---- opponents' moves
        for p in range(1, N):
            r = rd()
            if not r:
                return
            v = int(r[0])
            if v == -2:
                return
            if v == -1:
                if pile:
                    pile -= 1
                    count[p] += 1
                continue
            t = apply(v, int(r[1]), int(r[2]))
            count[p] -= 1
            if t in given[p]:
                given[p].remove(t)


if __name__ == "__main__":
    main()