Codex AI - Has anyone started on one or thought about it?

That’s 3^(19*19) which is more than 1.74x10^172 which is an inconceivably large number. Now I’m not certain Codex is smaller because the math is more complicated, but in terms of game trees Go fans out much quicker at the beginning of the game than Codex does because any open space on the board is a legal move. That means there are 361 legal moves for p1t1 and 360 legal moves for p2t1. If you try to do an alpha beta search more than 3 ply, it gets ridiculous.

2 Likes

Even at it’s most simple Codex has the following decisions:

Player 1 Worker (1 of 5). Turn 1 card play (1 of 8, including 3 heroes), Turn 1 2nd card play (1 of 6, including “no 2nd card”). Times approx. 2^14 possible starting hands

Player 2 Worker, Player 2 card(s) - including building Tech 1, Times starting hands

Player 1 Turn 2 Tech (2 of 30), Another ~240 possible plays.

Player 2 Turn 2. Ditto

Average game length: 12 turns of relevant choices.

So… in any single game, taking the random draws as given, there are about 10^63 different paths just counting tech choices and cards played.
Assuming only 6 shuffles between the players, that’s about another 10^25 paths for a game to take

And none of that counts variations on attacks or patrols.

3 Likes

I think it’s quite a bit less than this, due to the rules of the game. I am not a Go expert or anything, but IIRC if some opposing “unit” is completely surrounded then it dies. That removes a lot of possible board states from the above number.

1 Like

You’re right, clearly I haven’t done combinatorics in a long time. However, my point remains - if you redo my maths you’ll find that tracking 170 cards through 12 game states is 2.89x10^183 possible states. That’s just keeping track of where all the cards in your codex are. Adding in damage, exhaustion and runes gives you a lot more than 12 states, and that’s ignoring all the other stuff.

I agree that training an AI to play T1 and 2 is probably pretty straightforward (though in fairness, teaching an AI to play the first 2 moves of Go is also very straightforward!), and I think you’ll have a lot more success with a classical AI than machine learning. I still think that teaching it to play T3-6 in a way which is even interesting to play against is going to be tough, and it’s laborious because you’re going to have to reprogram it for every different opponent you play against. But I’d love to see some games when you’re done!

1 Like

You’re correct, not all of those states are legal states. A supercomputer calculated and pruned out all the illegal states (billions and billions of them) and the number of valid configurations comes out to “only” 2x10^170. That’s still crazy big!

1 Like

It’s actually very easy to generate a “basic” AI that follows a reasonable script, if all you want is a training dummy.

Step 1: hard code which cards to tech each turn. Avoid anything too complex.
Step 2: now that you know exactly which 20 cards the AI will have access to, create a definitive “worker priority” list, and always worker the top available card until you’re at 10 workers
Step 3: Set up a priority-to-play list (including heroes and buildings) for each of the first few turns, and one for turns 5+
Step 4: Actually do some work to be able to dynamically analyze attack/patrol choices

4 Likes

The nice thing about Codex from a search POV is that there are a lot of restrictions on the transitions. With a only 4 gold and three specs, there are only so many possibilities for p1t1. Likewise on p2t5, if p2 doesn’t have a tech lab and chose growth when they built tech 2, there are only 10 tech2 cards that are legal for them to play. Depending on their econ on turn 4 you can prune out even more transitions. All of those things I think make Codex more tractible for a search based AI because every decision you make actually prunes out a ton of state space.

1 Like

The biggest benefit from machine learning (aside from speed, given enough computational power) is that it could come up with styles of play that humans would never come up with (or at least not in the next 10 years) because it can iterate more rapidly and doesn’t have our built-in assumptions. And some of them might actually work and be surprising.
It can take you much more rapidly through evolutions of the meta, and get you to more accurate appraisals of the relative strengths of different spec combinations.

If you do get surprises, then you find out that the thing you thought was broken isn’t actually, or the thing you thought was bad has a purpose. If you don’t get any surprises, then you have more conclusive evidence that some specs/colors need buffs, or maybe there needs to be a small nerf somewhere.

As an example from other fields: machine learning has been used to suggest recipes that Americans would never consider (though you could maybe imagine an original Iron Chef contestant trying it out) based on chemical components that make up the individual flavors and known lists of things that combine well. The results have apparently (often) been surprisingly tasty.