I suspect that you're right that in principle and possibly even in practice an optimal AI could be built for this game to determine who can win from the starting position, though it would likely take more computing power than you're likely to have readily available. The best approach for brute-force solving a game like this is something close to what user1873 suggests in comments: rather than considering all lines of play, simply consider all board positions and determine the value of each board position. This is the approach that's typically taken for solving Chess endgames; while this board has many more cells (I count roughly 200, although the diagram isn't very clear) than the average chessboard, the fact that all the pieces are identical here does help a bit, and so it may be within reach; note that the chess endgames with 6 and 7 pieces have been solved for quite a while now. There are roughly (200 choose 3) = 200*199*198/6 = 1313400 positions for one team's chariots, and so roughly 1.7 trillion positions for all the chariots that would need to be evaluated.
Now, note that you don't have to build a 'move matrix' of 1.7 trillion x 1.7 trillion entries explicitly; that would be too large. Instead, the game could be solved with a sort of backtracking: first, identify those positions which are clearly won, and which person is winning them. Next, 'backtrack' - that is, play a turn in reverse - to identify all of the positions from which won positions can be reached, and then forward-evaluate each of those positions with a short move tree for that one turn to determine which of these positions lead to a forced win by one player or the other. You need a 'move tree' here because a turn isn't just a single move, but instead consists of multiple interlocking moves by the two players. Once that first turn's worth of backtracking has been done, another turn's worth can be handled in the same fashion; positions can be continuously added to a queue for evaluation, with a bunch of new 'one-move-back' positions added each time the queue empties.
Unfortunately, the catch here is in that move tree; the branching factor there is large enough that it probably pushes an explicit solve out of the realm of practicality (although perhaps not out of feasibility for someone with enough computing power). A 'move tree' consists of an assignment of the cards 1-5 to 3 chariots (plus a possibility of throwing cards away) for each player, plus some interleaving; this gives roughly (ignoring the throwaway) 75 moves at the first branch (3 different chariots that can be moved, times 10 (picking 3 cards from 5) + 10 (picking 2 cards from 5) + 5 (picking 1 card from 5) possible moves for the picked chariot) and up to 28 moves at the second branch (2 chariots that can be moved, times 4 (picking 3 cards from 4) + 6 (picking 2 cards from 4) + 4 (picking 1 card from 4) possible moves for the picked chariot). Since cards can be thrown away for turns, we'll back-of-the-envelope bump these to 100 and 50, and call it 10 moves at the bottom branch; this gives roughly 50,000 moves for each player that have to be considered in the move tree, or about 2 billion possible branches to examine on the move tree. I suspect this is highly overestimated - possibly by up to a factor of 100 or so - but a more careful analysis would be much trickier to finagle here. Even so, I'd guess there are many million possible ways of each turn playing out, and while doing some standard alpha-beta pruning (using established positional values) will cut that back down, it's still likely to take quite a bit of work at each of the 1.7 trillion nodes to establish a value.
Since positions may have to be evaluated more than once (if the first time determines that they can't be wholly solved yet), the overall work done is likely to be on the order of several exaflop (i.e., quintillions of operations total) worth of computation. That's a lot of operations - but note that you could get yourself access to a petaflop/second's worth of computational power, and thus do the whole solve in a few thousands of seconds - i.e., a few hours (possibly a few days). The biggest bottleneck is likely to be access speed to the database of values for positions, since something on the order of a terabyte (the rough size of that database) is still a bit too large to be kept in memory at this point; it'd have to be carefully designed to keep as much as feasible cached in memory and to be very smart about its disc accesses.
That said - I'd say that this is right on the edge of supercomputer feasibility right now; if the game were a bit better-known, this would make an excellent graduate project for a sufficiently motivated supercomputer programmer (or team).
