Chess is a very simple game mechanically there are six unique pieces: pawn, bishop, knight, rook, queen, king. The board has only 64 possible positions. There are two players. It takes about 5 minutes to explain to someone how to play the game.
With enough processing power you can essentially brute force the game. The computer can look at the chain of outcomes that would occur based on a particular move using pruning techniques to cut off pathways that are obviously bad. Consider that on opening the game there are only ten possible moves, eight pawns and two knights. As it's designers would tell you Deep Blue was really just a very efficient search engine and not AI.
It's the same basic method used to build a perfect tic tac toe game playing "AI" that almost in a low level CS class will end up doing. That game is so simple though a computer can map out all possibilities and ensure it does not lose in a under a second.
HOI4 does not have a set number of pieces (divisions, planes, ships)... in fact you have chose your technologies, then choose variants... then choose what to actually build. The map provides ten of thousands of places to move. There are probably a hundred AI nations going at any time vs 1 human meaning the computer must divide its attention massively. And there are innumerable other features as well beyond just moving pieces around. Think about actually long it takes explaining to someone how to play the game. Not even well, but to actually utilize all the features, a few hours at an absolute minimum.
It is impossible to brute force this game it is too complicated. So what to do?
Well, generally games simplify things by a combination of scripting (e.g. standard design templates, tech choices, focus trees) and strength evaluation. The strength evaluation is actually one of the prime reasons for the AI shuffle, it tries to stop you from getting over strength in a given point on a front line and preventing breakthroughs. So it has a very narrow focus and does not look ahead to realize that actually moving units will worsen its overall position.
There is hope though my friends, probably not for HOI4 but for gaming in general. Deep Learning focuses on the outcome rather than the developers telling it specifically how to play. In this system, the developer will carefully enumerate all the functionality the computer has at it's fingertips and then let it loose against itself or human players. It will lose over and over, thousands of times at the beginning because it literally has no idea what to do but will eventually learn its own strategy that will allow it to start winning. For example, it would likely figure out you can just win as Germany if you paratroop onto London at the beginning of the game.
Still though, that's a ways off, they have systems like that now that can crush humans at Chess but a game like HOI4 would require an insane amount of setup work on the developers part to do. The game would need to be designed with an AI like this in mind from the start. To be more successful it should be trained on a bare bones version first and then implement additional features.
