Scoring Quantum Tic-Tac-Toe

Question

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, A and B are entangled, and so it is said that X made the move AB: X1 is either in A or 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 A, B and 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. A takes 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 A.

• Write the number of the mark that fills that cell.

Since either X1 or O4 will occupy A, either 1 or 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 A, B, D or 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.

---

Scoring

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.

---

The Challenge

Given a series of moves from a game of quantum tic-tac-toe, determine the score of each player.

Rules

• 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.

---

Test Cases

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

Answer 1

Python 3.8 (pre-release), 419 371 351 bytes

-48 bytes following suggestions from @ovs

-16 bytes thanks to @JBernardo

def s(C,l=[]):
 l=l+[p:=C.pop(0)]
 if 0==p*0:
  del l[~1];r=[p]
  while r:c=r.pop();l=[r.append(t:=sum(e)-c)or t if e*0!=0and c in e else e for e in l]
 if C:s(C,l)
 else:w=[a:=[sum(z.count(j)>2for z in[*zip(*[[k//3,k%3,k%4,6559>>2*k&3]for k in l[i:f+1:2]if 0==k*0])]for j in set(z))for i in[0,1]]for f in range(9)];a[[1,0]in w]/=1+([1,1]==a);print(a)

Try it online!

Takes input with A-I translated to 0-8 in tuples. The collapse choice is represented by the cell the last entanglement collapses to.

Massive Explanation

# Take input C
# I(k) <==> move k is a collapse, not entanglement <==> 'imag'in dir(k) <==> isinstance(k,int) <==> hasattr(k,'imag')
# I have a feeling that collapses vs entanglements can be encoded in a much more byte-efficient manner
I=lambda k:'imag'in dir(k)
# C: list of moves, where a pair entry (e.g. [0,1]) is entanglement (e.g 0-1).
# and an int entry (e.g 1) states collapse of the last entry, (e.g. [0,1] collapsed to 1)
# l: be the list of entangled/collapsed states, built up with recursion
# pair (e.g. [0,1]) represents an existing entanglement, and int (e.g. 1) represents collapsed state
# the owners alternate XOXOXO in the list
def s(C,l=[]):
 l=l[:] # clone l for array operations
 if C:  # deal with end condition: only recurse if C has any mvoes
  l+=[  # append the first move in C to l
    p:=C[0] # assign p to be the first move
  ]
  if I(p):  # if that move is an int, collapse:
   del l[~1];   # delete the entangled move before
   r=[p]        # r will be the list of location to remove
                # start by adding p to r: no entanglement can have the location p anymore
   # I have a feeling this whole while loop can be replaced with a recursive method
   while r:     # while there is still a location to remove:
    c=r.pop()   # take c to be the first location, so we will collapse all states that contain c
    for i,e in enumerate(l):    # for each state e of l:
     if (1-I(e)  # If it is not a collapsed state
        and c in e): # and it contains c
         r+=[       # add to r:
            sum(l[i])-c     # the location besides e of c
         ];
         l[i]=r[~0] # replace e with that collapsed location
  s(C[1:],l) # recurse without the first move and with the modified l
 else:  # end condition: all moves have been processed
       # for case 5 (begins [[0, 1], [1, 4]...),
       # l=[0, 1, 2, 4, [3, 6], 7, [3, 5], 8] (most states are collapsed, except for [3,6] and [3,5])
  w=[  # w will be a list, supposing everything is collapsed as soon as it is intered,
       # of how many 3-in-a-rows each player has after each move
    a:=     # this is a for loop, so `a` gets set to the *last* 3-in-a-row count (the final win state)
        [
            sum(    # take the sum of:
                z.count(j)>2    # the number of directions that have exactly 3 (more than 2) identical entries
                    for z in    # for each of the 3 directions (rows, cols, diags) in
                        [*zip(*[    # the transpose:
                                [
                                    k//3, # floor divide maps items on each row to the same value
                                    k%3, # mod 3 maps items in the same column to the same value
                                    k%4 # mod 4 maps items on the main diagonal to 0
                                    6559>>2*k&3 # k on antidiagonal to 0; 0,1,7,8 to negative; 3,5 to 1 
                                                    # (k in[2,4,6] doesn't work because it also maps all of 0,1,3,5,7,8 to False)
                                ]
                                for k in l[i:f+1:2] # i=0: every even state; i=1: every odd state
                                                    # states limited to from the first f moves
                                if I(k) # only consider the state if it is collapsed
                            ]
                        )]
                    for j in set(z) # take the count for each unique value in the direction
                )
            for i in[0,1] # do this for both player i=0=X and player i=1=O)
        ]
    for f in range(9)   # for each count f of moves from 0 moves to 8 moves, calculate the 3-in-a-row count
  ]
  # now a should be [0,0],[1,0],[2,0],[1,1] or the opposite order
  if[1,1]==a:   # [1,1] is the only case we have to special handle
    a[[1,0]in w]*=.5    # subtract .5 from the second element (O's score) if X got the point first, otherwise subtract from X's score
  print(a)  # finally