Alice and Bob want to communicate, but the bot is attempting to impersonate Bob. Can Alice authenticate Bob?

This depends on what sort of shared secrets they have. Obviously, if they agreed ahead of time on a shared password and counter-password then the computer couldn't do it. If they, like, went to the same high school then the bot couldn't do it, unless the bot also knew what went on at that school.

So we need to assume Alice and Bob don't know each other and don't cheat. But, if they had nothing in common (like they don't even speak the same language) then they would find it very hard to win. There needs to be some sort of shared culture. How much?

Let's say there is a pool of players who come from the same country, but don't know each other and have played the game before. Then they can try to find a subject in common that they don't think the bot is good at. The first thing you do is talk about common interests with each player and find something you don't think bots can do. Like if they're both mathematicians then talk about math, or they're both cooks than talk about cooking.

If the players are skilled and you're playing to win then this is a difficult game for a bot.