In the description of this challenge, the following board will be used as a reference for positions:
ABC DEF GHI
For instance, in a game of ordinary tic-tac-toe,
B E A C G D F H I describes the following:
-X- -X- XX- XXO XXO XXO XXO XXO XXO --- -O- -O- -O- -O- OO- OOX OOX OOX --- --- --- --- X-- X-- X-- XO- XOX
Quantum Tic-Tac-Toe Gameplay
In quantum tic-tac-toe, players' moves are superpositions of moves in classical tic-tac-toe. Players mark two cells per move instead of just one, and those cells become entangled. Each quantum mark is given a subscript telling the number of the turn in which it was placed.
In the above board,
B are entangled, and so it is said that X made the move
X1 is either in
B but the true position cannot be known with certainty until later in the game.
Consider the following board, made with the sequence
AB BE DE AE (X makes the move
AB, O makes the move
BE, X makes the move
DE, O makes the move
AE; note that the relative positions of quantum marks in a cell in the image do not actually matter):
Here, there has arisen a cyclic entanglement between cells
E. Consider the following image, in which a line represents an entanglement:
After a cyclic entanglement (which does not necessarily have length 3) is formed, measurement takes place, in which every quantum mark involved in the cycle collapses into a known state and becomes a classical mark. This includes entanglements like the red one above that are merely accessories to the cyclic entanglement, and don't actually complete the cycle. After one player forms a cyclic entanglement, the other player chooses which state the board assumes. Since X formed the cyclic entanglement, it is up to O to choose between these two states:
There are only ever two possible states to choose from, because all individual entanglements only involve two cells. To record which state was chosen, the following methodology will be used:
Find the first cell (i.e.
Atakes precedence over
B, etc) in the cyclic entanglement which cannot be removed without breaking the cycle (meaning entanglements like the red one above are excluded). In this case this is
Write the number of the mark that fills that cell.
O4 will occupy
4 will be written. This would mean the above boards would be described by the sequences
AB BE DE AE 1 and
AB BE DE AE 4, respectively. After measurement occurs, no more moves can be made in
E because it is now known what lies in those cells.
A single-cell entanglement, e.g.
AA 1, is not allowed under ordinary circumstances, as that would mimic the behavior of a classical mark. This sort of move is only allowed when just one cell not occupied by a classical mark remains.
A game continues until at least one tic-tac-toe is formed or until the board is filled with classical marks. Multiple tic-tac-toes can be made only if they appear simultaneously after a measurement; this is because the presence of one or multiple tic-tac-toes disallows the placement of any additional quantum marks.
The first number corresponds to X's score and the second to O's.
If neither player has a tic-tac-toe, then both players get zero points.
If there is only one tic-tac-toe present, then the player with the tic-tac-toe gets one point and the other player gets zero points.
If one player gets two tic-tac-toes after a measurement, then they get two points and the other player gets zero. It is not possible for one player to get one tic-tac-toe while the other gets two, nor is it possible for both players to get two, nor one player to get three.
If both players get a tic-tac-toe after a measurement, then the player with the least maximum subscript in their tic-tac-toe will get one point and the other player will get one half-point.
For clarification on that last point, consider the board made by the sequence
AI EG BE EH DG AI 1 BC CE 3:
The maximum subscript in X's tic-tac-toe is seven, while the maximum subscript in O's tic-tac-toe is six. Because of this, O has the least maximum subscript and gets one point while X gets one half-point.
Given a series of moves from a game of quantum tic-tac-toe, determine the score of each player.
Input and output may be given in whatever form is most convenient, but it must be explained if it differs from what is described above. Changes can be slight, like describing locations or scores differently, or more drastic. For instance, writing the number of the classical mark that fills the cell of the last quantum mark placed can be done instead of writing the number of the mark that fills the first cell alphabetically.
One must always be able to tell which score corresponds to which player. For instance, always putting the winner's score first is not acceptable unless the output also tells which player won or lost. If a specific player's score is always given first, that does not have to be included in the output (as seen in the test cases).
Assume only valid input is given.
Spaces are not necessary; they were added for the purpose of legibility.
This is code-golf so the smallest program in bytes wins.
In: AB Out: 0 0 In: AI EG BE EH DG AI 1 BC CE 3 Out: 0.5 1 In: IA EG EB EH GD AI 1 CB CE 3 Out: 0.5 1 In: DE AB DE 1 AH CF CH CG BC 2 Out: 1 0.5 In: AE BF EI DH AI 1 Out: 1 0 In: CE BD EG FH CG 1 Out: 1 0 In: AB AD BC CF AC 5 Out: 1 0 In: AB BE BC CE 2 DG HI DF HI 6 Out: 0 1 In: BC BE CF EF 1 AD AG GH DG 6 II 9 Out: 0 0 In: DI AE AB BF EH AH 2 DI 7 CG CG 8 Out: 0 0 In: AD BH EF CI EF 3 HI DG BI 2 AG 1 Out: 2 0