Comment Re:4x strategy when? (Score 1) 58
You've just done what the programmers do. Introduce higher-level heuristics into the rules by pushing everything into blocks of actions.
No different to "find enemy", "target enemy", "shoot enemy". The problem is not breaking down a problem given the goal (in your example, every path taken to get from "I want to build a farm" to "I have built a farm here" is equal-cost to the computer) - a simple optimisation removes them from the tree, yes.
But then you either get them, say, building on tiles that are the most at risk from attack because "it doesn't matter which tile". You know that because you infer it from other information, the computer doesn't. Either it has to specifically check EVERY time (game tree), or pick a random / northernmost grassland to upgrade first (programmed heuristic).
Although the exact tree is prunable, the above is the way to get yourself into the same order of magnitude. And computers can, and do, and will struggle with trees of that magnitude for even simple actions unless they are following heuristics.
But, the biggest part you've skipped over - knowing that you need a farm to do X to do Y to do Z in N moves time is the real struggle, the real key. Optimising a tree for the low-hanging fruit (pardon the pseudo-pun) is trivial and can be done automatically and save you a handful of necessary steps.
But what if the system is attacked halfway through the process? Do we abandon? Start again? Fight on valiantly until we get where we want no matter the cost? How do we decide we need a farm? That's where the VAST majority of the game tree decisions are made and that's where the decision matters and THAT'S the difficult question to answer such that a computer can't do it in real-time given the possibilities and the impact of those. Or you'll see it build farms while you quietly strip away its land, units, etc. and it won't "notice".
Think of pathfinding, because that's what you're doing (just through a "directed graph"). There is no difference, to the computer, between A* pathfinding through a terrain and working out the best way through a game tree.
Some routes are muddy and slow you down, some routes lead to loops where you come back to where you are, some routes take more "steps" but get you there quicker, some routes are only a single step but take forever to walk through, some steps are more risky, some steps are safer.
Evaluating those for a computer means enumerating them, and their children, and their grandchildren - and virtually all of them until there's a point that you know it's definitely worse than some other route. How deep you go down the tree increases the complexity, but also increases the chance you have a strategy that works in the long-run. Not traversing to a certain depth means you're only thinking in the short-term.
And every time you enumerate some risk, factor or cost, you are required to formulate it into a single calculation ("edge cost" in graph theory terms). That means giving it a weighting (heuristics!) or determining a weighting dynamically, performing calculations, maybe looking at the surrounding areas (this path is quicker but is nearer the enemy etc.).
I studied graph theory for several years at uni. This stuff sounds really basic, boring, easy and predictable. We all know how mini-max algorithms work on simple games like draughts/checkers. But as soon as you try to scale to anything even vaguely complex you see factors, costs and weighting that are required and which greatly affect the performance of the search (and, hence, the AI).
If there are only 10-20 options like explore and they each take, say, 10 turns to complete, then the computer is only making a decision every 10 turns in effect. Which means it can't react. Sure, you could program an interrupt on certain events. But then it might ignore your attack for 5 turns so being "dumb" and giving you an advantage. Or if you interrupt it every turn with SOMETHING, it's basically back to having to evaluate every single move.
Computer AI is just a series of programmed heuristics and shortcuts to make the real game-tree-traversal possible and practical precisely because they get too large otherwise. The programmed heuristics are basically programmed orders, programmed weaknesses, programmed ignorance. That's where the AI falls down. Someone has told it that "a knight is worth three pawns" in effect, and while that's a general rule that children are introduced to, even they know that it's not a written-in-stone rule to be obeyed every exchange. It's much more complex than that. Someone, somewhere has told the AI in Civilisation, etc. that losing X unit is half as costly as losing Y unit, or building tile Z.
Without those rules, the game tree is too huge to traverse in time. With those rules, the AI is crippled by hard-coded, predictable actions. And there's also the problem that NOBODY wants to play against an unbeatable AI and the only point we can put in a limit is the game-tree depth, or use of heuristics.
And, proper, true, real AI (and human intelligence) is about forming those rules on their own just by playing enough, and knowing when to break those rules as the situation has differed too much. We do it by inference, which you can't program. AI can't yet do it except by things like neural nets etc. which - while useful - have major limitations.
Otherwise, literally, all the Age of Empires modding community could have made a quick, unbeatable AI in the 15-years since it's release and the modding community being able to program their own AI. I used to tweak the QuakeC code for Quake bots back in the day. Things like OpenTTD (and TTDPatch, which is decades old) have allowed huge communities of clever people to create bots to play against on a game which those people are ABSOLUTELY expert at. Yet, still, the bots don't challenge a seasoned player unless they cheat.
Game-tree depth is the killer. And as soon as you prune a branch, you've introduced a heuristic which is a predictable weakness in the AI's operation.