Oh yeah, I can relate to that experience. My chess app had an "undo turn" button, where you could jump back an arbitrary number of turns. The most frustrating thing wasn't the AI winning, but realising that the AI had already won several turns ago and you're just a dead man walking, with all remaining options leading to failure.
I never hated A* as much as during those games.
One thing about predictable AI's that irks me is once an optimal strategy is discovered, variance from that strategy is no longer rewarded. This creates a tactical endgame I wish didn't exist.
For instance, I played a lot of Gears of War Horde mode and difficulty is increased by increasing health, accuracy, and damage of the enemies. And the same strategy will win over and over. That's great for a grind-y game like Gears 4 Horde, but beyond a certain level it becomes a race to build an automated killing machine that once solved is no longer engaging.
Once you build a wall of turrets, why in god's name would an enemy keep rushing? Just the smallest bit of learning would go so far. The game would be way harder, but also WAY more interesting. Playing on normal where you actually have to hunt the enemy instead of holing up and waiting for them to rush your lane would have been awesome!
That's just one example in one game that I'm very familiar with, but isn't a unique problem. Even in 2019 there is a lot of room to make a challenging and fun AI.
The trick is to make every match feel like you could lose, not like you can't win. AI/ML should figure out what makes close games close, and keep evolving the enemy's strategy to keep them close, not just their stats.
Imagine chess but with 100+ different pieces and an element of collecting/upgrading pieces.
My friend was working on a chess variant for years, and it was very easy for him to make the AI be very, very difficult but that isn't fun at all! It would always win.
He then tried adding an element of randomness to it to dumb it down. But then the AI just looked perfect most of the time while occasionally making bizarrely dumb moves.
He later added "personalities" to the AI, where each one would try their own sets of strategies and attributes. He continued to make it better and better.