Ehrenfeucht-Fraïssé game ($G_n(\mathcal{M},\mathcal{N})$)

In each round the Spoiler selects an element from either structure and the Duplicator responds in the other. The paired selected elements must preserve all atomic information and equality, giving a partial isomorphism of structures. In the infinite game the Duplicator wins by avoiding failure at every finite stage. In a timed game the Spoiler first announces the number of rounds, allowing a different response strategy for each horizon.

With $k$ moves remaining, preserve corresponding gap sizes exactly when smaller than $2^k-1$, and otherwise require both gaps to have at least that many points. One move splits a gap; $2^k-1=2(2^{k-1}-1)+1$ permits matching both smaller gaps. This strategy proves that $(\mathbb{N},<)$ and $(\mathbb{N}+\mathbb{Z},<)$ agree at every finite quantifier rank despite the second order containing points with infinitely many predecessors.

For a finite relational first-order language, with finitely many constants allowed, the Duplicator wins the $n$-round game exactly when the structures are rank-n equivalent. Game-winning implies rank equivalence in arbitrary languages; the converse needs a finiteness condition and can fail even for an infinite unary vocabulary. Over a finite relational vocabulary, winning every announced finite horizon is equivalent to elementary equivalence.

For countably many unary predicates $P_i$, let $M$ contain infinitely many copies of each finite membership pattern and let $N$ add an element satisfying all predicates. Every finite vocabulary reduct has infinitely many elements in every Boolean cell in both structures, so $M\equiv N$. The Spoiler nevertheless wins the one-round full-language game by selecting the new element, whose complete atomic pattern has no counterpart in $M$.