Python, 92 bytes

[🧍‍♂️👫🧍🧑‍🤝‍🧑🧍‍♂️]

This is a community effort: Jonathan Allan's and Mukundan314's significant (-37 bytes) improvements on my original idea.

lambda p,q:all(o:=[p.replace("?",a)<q.replace("?",b)for a,b in["AZ","ZA"]])+[p==q,2][any(o)] 

Attempt This Online!

Anonymous lambda. Returns 3 for left, 0 for right, 2 for undecidable, 1 for equal.

lambda p,q: # f(): Given two words, construct an integer... all( # - adding 1 if all the following inequalities hold: o:= # (inequalities, stored as "o": [p.replace("?",a) # left word with its "?"s filled is <q.replace("?",b) # less than right word with its "?"s filled, for a,b in["AZ","ZA"]]) # the fillings being A and Z first, # then Z and A) +[ # - then adding either p==q, # (A) 1 point (conditional on words being equal) 2 # (B) 2 (unconditional) points ][any(o)] # - with the criterion that (A) is chosen iff # none of the "o" inequalities held. # - left wins = 3 = 1 (all ineqs hold) + 2 (some ineqs hold) # - right wins = 0 = 0 (not all ineqs hold) + 0 (words differ and no ineq holds) # - undecided = 2 = 0 (not all ineqs hold) + 2 (some ineqs hold) # - equal = 1 = 0 (not all ineqs hold) + 1 (words equal and no ineq holds) 

Python, 131 bytes

[🧍‍♂️]

My original submission (with 1 byte from Neil)

k=lambda s:[s.replace("?",y)for y in"AZ"] f=lambda p,q:(p==q)*(not"?"in p)or all(o:=[a<b for a in k(p)for b in k(q)])or any(o)and 9 

Attempt This Online!

Returns True for left, False for right, 9 for undetermined, 1 for equal.

Explanation (not that it's really necessary):

k=lambda s: # ┑k(): Given a string, return: [ # └─ in a list, s.replace("?",y) # the result of replacing all '?'s with: for y in"AZ"] # 'A', then 'Z'. # ~ ~ ~ ~ f=lambda p,q: # ┑f(): Given two words, return: (p==q)*(not"?"in p) # ├─ `1` if identical and without '?'s. or # │ Otherwise: all( # │ o:=[a<b # │ ╭ First, compare left < right ╮ for a in k(p)for b in k(q)] # │ ╰ for each combination in k(1st)×k(2nd) ╯ ) # ├─ `True` if all inequalities hold. or # │ Otherwise: any(o)and 9 # ├─ `9` if any of the above inequalities holds. # └─ (`False` if all 'or's are exhausted). 

Jelly,  19  16 bytes

Ḳj¥þØAZŒpM€§QḌ«4 

A monadic Link that accepts a pair of lists of characters (from A-Z plus the space character for representing NaCs), and yields an integer from \$[1,4]\$ where \$1\$ means right first, \$2\$ means left first, \$3\$ means equal, and \$4\$ means insufficient data.

Try it online! Or see the test-suite (uses ? rather than the space character and casts output to the 2 1 = ~ given in the question's text).

How?

Ḳj¥þØAZŒpM€§QḌ«4 - Link: [L, R] ØA - alphabet -> "ABC...XYZ" (terser than ⁾AZ -> "AZ") þ - table of {[L, R]} x {"ABC...XYZ"} with x: ¥ - last two links as a dyad - f(String, Char): Ḳ - split {String} at space characters j - join with {Char} Z - transpose Œp - Cartesian product -> All pairs of altered strings M€ - maximal indices of each pair (left less:[2], right less[1], equal:[1,2]) § - sums Q - deduplicate Ḍ - convert from decimal «4 - minimum with four 

Charcoal, 34 bytes

≔⪪θ?ζ≔⪪η?εＩ∨⁻›⪫ζA⪫εZ‹⪫ζZ⪫εA∧№⁺θη?² 

Try it online! Link is to verbose version of code. Outputs -1 if the first string is less, 0 if they equal, 1 if the first string is greater and 2 if they are incomparable. Explanation:

≔⪪θ?ζ≔⪪η?ε 

Split the input strings on ?s separately, as this saves a byte.

Ｉ∨⁻›⪫ζA⪫εZ‹⪫ζZ⪫εA∧№⁺θη?² 

• If joining the first string on Zs results in a string that precedes joining the second string on As, then output -1.
• If joining the second string on As results in a string that precedes joining the first string on Zs, then output 1.
• If neither is true and neither string contains ?s then output 0.
• Otherwise output 2.

Perl 5 -pl, 69 bytes

$_=(($b=<>)=~y/_/Z/r cmp y/_/A/r)-($b=~y/_/A/r cmp y/_/Z/r)||$_ cmp$b 

Try it online!

Strings are entered on separate lines. Underscore (_) is used as the NaC placeholder.

How?

The cmp operator is the string equivalent of <=> which exists in many languages.

First compare the worst case scenarios, replacing the NaC with Z in the second string and A in the first string. Then, change the replacement so that NaC becomes A in the second string and Z in the first string. If the difference between these two values is 0 indicating that the sorted order of the strings is the same both times, a definitive result can be determined, and the two original strings are compared with each other to determine the result.

05AB1E, 16 bytes

1„AZSδ:ø`R‹2βIËM 

Port of NicolaSap's Python answer (which I've then golfed further using 05AB1E's strengths), so make sure to upvote that answer as well!

Uses 1 as NaC. Outputs 3012 for 12=~ respectively.

Try it online or verify all test cases.

Explanation:

1 # Push a 1 „AZS # Push "AZ" and convert it to a list: ["A","Z"] δ # Apply double-vectorized using the (implicit) input-pair: : # Replace all 1s with the character ø # Zip/transpose; swapping rows/columns ` # Pop and push both pairs separately to the stack R # Reverse the second pair ‹ # Vectorized compare the values in the two pairs: # (note: this will result in [0,0], [1,0], or [1,1], but never [0,1]) 2β # Convert it from a base-2 list to a base-10 integer # ([0,0]→0; [1,0]→2; [1,1]→3) I # Push the input-pair again Ë # Check whether both inputs are the same M # Push a copy of the largest value on the stack to the stack # (which is output implicitly as result) 

Examples:

Retina, 89 bytes

¶ ¶$`¶$`¶$'¶ T`@`A`¶.*¶ T`@`Z`¶.* @ \w 1,O` ~L$`^.* %a`$& ¶ 1{5} = .1100 1 .0011 2 ..+ ~ 

Try it online! Takes input on separate lines and uses @ as NaC but link is to test suite that expects input in the provided example format and outputs the computed and expected output. Explanation:

¶ ¶$`¶$`¶$'¶ 

Create two more copies of the first string and a second copy of the second string.

T`@`A`¶.*¶ 

Change the @s to As in one copy of each string.

T`@`Z`¶.* 

Change them to Zs in another copy of each string.

@ \w 

Change them to \ws in the original copy of the first string.

1,O` 

Sort all of the strings except the first.

~L$`^.* %a`$& 

Using the first string as a regex, match it against each of the strings in turn.

¶ 

Join the match results together to simplify testing.

1{5} = 

If all of the strings were identical then they were equal all along.

.1100 1 

If the first string only matches the first two strings then it was less.

.0011 2 

If the first string only matches the last two strings then it was greater.

..+ ~ 

Otherwise the result is indeterminate.

Zsh, 144 bytes

Uses _ for NaC and : for insufficient data.

set "${@//_/A}" "${@//_/Z}" case "${(j<.>)${(@o)@}}" { $4.$3.$2.$1)<<<=;; $1.$2.$4.$3|$2.$3.$1.$4|$2.$1.$3.$4)<<<:;; $1.$3.$2.$4)<<<1;; *)<<<2 } 

Try it online!

The general idea here is create four strings by expanding all NaC to either all As or all Zs. Then by sorting the four strings and comparing to certain permutations, we can determine which case we fall under.

After looking through how all permutations of the arguments matched the sorted arguments, this was the smallest subset of matches I could find which worked.

JavaScript (Node.js), 86 bytes

a=>b=>g(a,0)==g(b)||[g(a,'A')<=g(b,'Z'),g(a,'Z')>=g(b,'A')] g=(a,c)=>a.replace(/1/g,c) 

Try it online!

First check if a==b and both contain no ? by replacing ? in a into 0 and in b into undefined (both are invalid char)