With hidden movement, say that both sides could do an average of 50 choices per "unit time". The computer would need to evaluate it's 50 choices on Turn 1, and evaluate 50 enemy moves as well. That's 2500 combos to process in the opening turn. But because there's hidden movement, on turn 2, the player only know which of 50 moves it took, but doesn't know which of the 50 the enemy took. Hence, on turn 2, the computer must process 50 different "possible" current board positions, multiplied by the further 50x50 choices each player could make on that move. Hence, not only is there a vastly number of branches to evaluate, each "unit time" adds 50x to the number of potential current boards you have to evaluate.
This *might* be feasible to tackle with a large enough memory. The computer could store all evaluated branches and only delete them when some new information pruned the possible states. But that would only work well for boards with discrete locations. With per-pixel unit placement, direction facing etc, trying to exhaustively evaluate not only the current actual board, but all possible board positions in the hidden space would be in the realm of uncomputable information (e.g. longer than the age of the universe stuff).