Every time I see episodes of star trek where someone beats Spok or Data at some game like chess I start thinking about this. Especially data, because my gut instinct is to always say that's not possible, he should always win.
But upon further inspection I think it's not so farfetched after all. If you imagine a game like chess each move is like a single node on an ever expanding tree of all possible moves. There's even actual databases like that where you can just go and look up your current chessboard configuration and see which moves you can make next that have the highest probability of your side winning.
But that's all it ever is, probability.

But it can still be tricky, because probabilities are weighted and it's not always possible to stay ahead. Even if you could provably make every single move with the highest probability of you winning you can still lose, because it takes both players to carve out a branch through that tree and along the way there are fluctuations.
So just playing the odds will not always win. Of course the further ahead you can see the more you can make better choices (e.g. maybe you go down a path that has only a 50% chance of you winning rather than 60% which might be due to stupid mistakes that you know your opponent won't make). It would seem that to actually have the best chance of winning you would want to combine those probabilities along with some knowledge of your opponent.

So I would say chess is a perfect example of the kind of game you're looking for. It would be fun if there was a "bot chess league" where players just pit their chess A.I.'s against one another and then can also refine their code as they observe matches played by other A.I.'s. I don't think such a league could ever actually stagnate. It should always be possible to 1-up any A.I.
I would say that any game which has an exploding tree of possible moves (as opposed to a shrinking or constant one) should be an ideal game for this.

>Are there any games or competitions where it's allowed and expected for both players to use AI to guide their decisions?
Yes you posted it. There's something called "Advanced Chess" where both human players use chess programs to help decide on moves.

Additionally, even traditional chess players at the highest level use chess programs to decide moves. They plan for different positions that the opponent is likely to play and use computers to find good moves. Of course this is all done before the start of the match, possibly days or weeks before.

>>2
>It would be fun if there was a "bot chess league"
Such leagues do in fact exist.
http://icga.org

>>2
I remember something from the 2001 book, about how they would play chess with HAL. Being a sentient supercomputer, he could easily win every single game, but in order to maintain morale he was programmed to lose intentionally around 50% of the time. Dave and Frank conveniently pretended not to know that when playing chess with HAL to pass the time. I could imagine Data, with his overwhelming desire to become more humanlike, would also purposely lose sometimes. For one thing, if you win 100% of the time, you'll soon find that no one wants to play with you. I also remember an episode where he was playing a game of future space-chess or whatever against a master of the game and actually wasn't able to win, but he was able to aim for draws and drag out the game until his opponent, being an organic, got tired and started to make mistakes or something.

I just noticed the chess in OP's image is incomprehensible. I think that's a pawn on the back row.