Hacker News Reader

Comment by keiferski | Hacker News Reader

Question for those knowledgeable on AI: what sort of game would be easy for a human to understand, but difficult or impossible for a computer to play or easily defeat humans? I imagine one based purely on randomness, like dice, would be one.

I remember reading somewhere that languages like Finnish and Hungarian are difficult for computers to parse, [1] due to their agglutinative grammatical structure. Not sure if that is actually true, but it seems an interesting starting point.

[1] Discussion sort of about this: https://news.ycombinator.com/item?id=21572261

View on HN

I actually expect computers to do much better on a game with a lot of randomness, since it then becomes statistics.

Genres that would be difficult: - any game based on recognizing images (the first example that pops in my mind is codenames)

- social deduction like werewolf

Codenames is easyfor an all-computer team; it's simply a word vector problem. There are already AIs published.

Pictionary might be harder.

Ah yes, I was thinking of codenames the picture version.

Not the answer you're looking for, but motor racing and simulations of it.

Sounds counter intuitive, but despite doing fast laps when on the circuit alone, even the best AI racers have difficulty surviving a race distance in close pack racing without crashing.

Roborace, the autonomous racing league in development has barely managed to put two cars on track and doing an overtake safely. A lot of money and state of the art research has gone into this.

I expect that AI will be able to beat humans on the (simulated) race track in a decade or two but we aren't there yet.

Wait, I thought autonomous cars are almost out. You ruined my excitement.

Autonomous cars can solve the problem of close-pack driving by avoiding close-packs. That's a great way to lose a race though...

I get that this is true of real cars, but is it really true of simulated cars? Can you share an example?

There are no racing simulators or even games that have reasonable AI opponents that don't cheat.

I, mid-tier sim racer, have no chance against good AI in hotlapping on track in some popular sims, but all of them either yield or cause a crash that would take them to the stewards (or grave) when racing for position on the same piece of track.

Pro racing team have excellent sims these days but they don't have AI opponents.

Do you have any particular reason to believe that the "AI" you refer to are sophisticated ML models built over the sim, rather than hand crafted bots. You say "don't cheat" which makes me think you're referring to the bots included in the sim. Because an AI that's not built into the game shouldn't have any way to cheat.

Forgive this comparison, but the ai drivers in mario kart games also cheat, but aren't particularly representative of current state ML tech. There's likely no ML involved in them at all. There's not much in the way of actual attempts to do this with ML either so it's not proof either way (especially on new untrained courses).

No, they are not sophisticated ML models. Such things don't exist in this space as far as I know.

The ones that cheat are in racing games. The hardcore sims that have AI bots don't usually cheat, and they are the ones that are fast by themselves but hopeless and/or dangerous in a pack.

Roborace is the only place where this kind of research has been done, and after many years and millions of dollars they're past their first baby steps, but still learning to walk before they can run.

When you say "don't cheat" do you mean "are subject to the same physics as human drivers" or "don't engage in illegal overtakes / maneuvers"?

Any game built around word play or humour.

E.g. "I'm sorry I haven't a Clue"[1] or something like Cards Against Humanity.

Though I imagine someone is trying to apply GPT-3 to these sorts of games already.

Beyond that, any sort of narrative based RPG or exploration game (e.g. legend of Zelda) would be hard to do 'properly', i.e. without scripting a bot.

[1] https://en.m.wikipedia.org/wiki/I%27m_Sorry_I_Haven%27t_a_Cl...

Actually, I'd wager that Cards Against Humanity would be one of the games a model would be best at over a human. There are only a limited number of white cards that could work with any given black card and it could fairly quickly bucket a player into certain types most likely to pick certain cards. Would it be perfect? No, but that's the nature of the game and with only seven options and no branching paths it doesn't seem like a stretch to say a trained model can trivially beat an average player and challenge a more "advanced" player.

Dixit would be more interesting here.

Dixit is a bunch of very different pictures and the goal is to say something about the card you've picked such that some of the other players will know which one it was but not all of them, your opponents are listening to your description and can pick from their own hands of cards. You get points for: Identifying the correct card based on the description when it isn't your turn; Playing a card which people mistook for the correct card when it isn't your turn; Some but not all other players guessing your card when it was your turn.

So that ends up being about shared experiences and culture, because if you share culture with someone you can allude to some element of the picture in a way that's completely opaque to everybody who doesn't share that culture, allowing the "in group" to identify your card while everybody else can't do better than luck.

For an AI there are two interesting challenges. Firstly, in "understanding" the pictures shown on the cards. It's not enough to be like "That's a cat" "That's a book" "That's a tree" you need somehow to compete with a human that thinks "Hmm, that's kinda like the Rapunzel story except it's a bird instead of a princess?" and "The dragon looks happy"

But then the AI also needs cultural context like a human player so it can try to judge good descriptions: "Happy Dragon" is obviously this card, "Cat" might be any of half a dozen cards, how about "I am your father" as a reference to the Cloud City scene that looks a bit like this picture - and so it can try to pick cards that match human descriptions to steal points that way.

AI is still fairly bad at open ended games, like, say, zelda. Anything where you can't quite train it from start to end is a struggle.

Randomness is not an issue. AI can already play poker at superhuman levels.

At this point, I'd say that AI can't really play collaborative games well, like Diplomacy. They also struggle in continuous games.

I don't think the collaboration is the issue, as Facebook has a paper about playing hanabi: https://ai.facebook.com/blog/building-ai-that-can-master-com...

Hanabi only has limited communication. Of course, it's a bit unfair, since a game like Diplomacy requires large amounts of verbal communication, but I think that's the kind of game that's difficult to solve.

Agglutinative grammar seems to be a difficult nut to crack, and I think Malayalam (my native tongue) is likely the most complex language in that sense. I happened to read "A quantitative analysis of the morphological complexity of Malayalam" (https://kavyamanohar.com/post/malayalam-morphological-comple...) which was published just a few days ago which describes some of the challenges, and has an interesting comparative study of various languages including Finnish and other Indian languages that are known for agglutination, inflection, and derivation from a common root.

Recently there has been a growing interest in developing AI for cooperative games, like Hanabi. I believe the challenge originated from a paper by Google Brain/DeepMind [1], but several other groups have tackled it, including Facebook AI Research [2].

[1] https://www.sciencedirect.com/science/article/pii/S000437021...

[2] https://arxiv.org/pdf/1912.02318v1.pdf

This is a really interesting - and I think, important - question although people ruling stuff out of bounds for AI do have a habit of becoming proven wrong - the classic recent example being Go.

My assumption would be games or activities that are NOT heavily based in pattern finding, maths, statistics, categorising, memory etc.

I think it is more useful perhaps to consider the motivation for game playing which is completely different (at present) for humans/animals compared to computers.

We play because it is fun, or to bond, or to improve social status, make money, whatever.

Computers play because that is what they are told to do.

Maybe Diplomacy ?

https://en.wikipedia.org/wiki/Diplomacy_(game)

Bridge (the cards game) has seen a lot of research over the past decades without the bots ever becoming "world class good".

Of course you could argue that it is a difficult game for humans to understand as well =) So it might not fit exactly what you prompted for.

https://en.wikipedia.org/wiki/Computer_bridge

That's because the AI isn't allowed to cheat. The skill of "world class" bridge play mainly lies in creative ways to cheat.

I don’t know much bridge so please correct me if I’m wrong, but isn’t that “cheating” basically applying steganography to game moves? It’s not like touching your ear at the right time or some other kind of back channel. It’s all represented by game moves. That sounds tractable for an algorithm.

Well yes, that and actual cheating (the competitive scene if rife with cheating of all kinds).

If AI teammates were allowed to have a pre-developed, shared model between them for communication so the other automatically "knows" what the others moves mean then it would be closer to fair grounds but that's considered cheating even though human teammates do the same thing.

I imagine one could apply the semantics of a leadership election algorithm and a recognizer neural net in each AI player to let them develop their messaging in game. If the AI were permitted to store temporary state through the course of a tournament or with a practice round (human players practice too) then I don’t see why it couldn’t work.

I haven't been in the contract-bridge scene in a long time, but had a friend who was competitive at the regional-level, and the impression I got was that partner-signalling was hard to get away with just because opponents would recognize abnormal results so quickly; at that level you would regularly face opponents who could tell you every contract you had bid against them and what the result was from memory.

On the other hand, I worked at a US Team Trials championship game, and the two tables were in separate rooms, with a diagonal partition across the table and completely silent bidding. Presumably they wouldn't go through such gymnastics if cheating weren't a concern. Perhaps the stakes are too low at the regional level (or those who are good enough to get away with it quickly progress to a higher level?).

What? Bidding is all about sharing information with your partner about what's in your hand. There's nothing cheating about that. Cheating would be if you had some side channel that was not the explicit information you were allowed to share as part of the process - e.g. if you were playing online and relaying your bids as "one - clubs" meant something different to your partner than saying "1 - clubs".

basically applying steganography to game moves?

Sort of, except you have to tell your opponents what your algorithm is. Like you can invent a system where an opening bid of "one heart" means "I have exactly three aces" (as opposed to the conventional meaning of "I have a reasonably strong hand with hearts as my longest suit"), but you can't keep that meaning secret.

Starting variation (like Arimaa), takes opening books off the table. In general, high branching factors (possible moves at any situation) are more difficult. Humans have an intuitive sense for which moves are reasonable at any situation, or whether a line of play is productive. Branching factor is part of why Go was so much harder than chess. Hidden information is hard: computers are not good at the "thinking in another's shoes" and inferring hidden facts from known ones, or are too easily tricked by ploys. Poker is an extremely simple hidden information game, but as I understand it, the AIs are still behind humans. Ease of position evaluation is also very important to computers. No one has made a general Magic The Gathering AI that is even mediocre at the game, because it is extremely difficult to heuristically evaluate a general boardstate. There are many non-linearities, and the value of cards is heavily situation and strategy dependent.

You're definitely wrong about Poker.

The state of the art for Poker goes like this:

Heads Up Limit Texas Hold 'Em is effectively solved.

http://poker.srv.ualberta.ca/

Not just "There's an AI which is very good at it" there is literally a fixed strategy I can reveal in advance and that strategy will statistically break even against an equally efficient strategy or else gradually take all your chips if you don't have a similar perfect strategy. Even though you know exactly what the strategy is, you can't beat it anyway.

At No Limit the clear champion is AI. Pluribus, Libratus and Deepstack all play clearly better poker, it's not practical to conceive a "solved" or even "near solved" like Cepheus strategy for No Limit, but the AI is tireless and it's disheartening for humans to just find every strategy countered so I expect them to get worse not better.

I don't expect any further exhibition type matches for AI versus professionals at poker because of this success.

Now, full ring is different, but largely because of the social dynamics. If you're at a table with six humans and one AI, obviously all of the humans will co-operate to force out the AI since the alternative is the AI wins. So that's not a very interesting problem.

Even still, AIs are not able to "figure out" exploration heavy games, like montezuma's revenge [1]

I suspect games that will give ai the most trouble: games with super sparse signals or ambiguous directions (others mention RPGs, and that tracks)

Games that are hard to simulate will be hard from a training perspective (I think both starcraft and dota2 needed patches to give the AIs reasonable tools to understand the game)

At one point, before go was solved, it seemed like maybe adding significant depth or randomness to a game might make it "hard", but now I'm more convinced that difficulty simulating & exploring tends to be a bigger factor

[1] https://openai.com/blog/learning-montezumas-revenge-from-a-s... It gets it but hard to make a general ai that understands it and the other atari games

Dodgeball. Cup stacking. Or any other game that requires bipedal movement or quick and precise adaptive manual manipulation.

Leetcode style coding competitions.

Short story writing competitions featuring specific prompts/themes.

SAT test taking.

Short story writing might be more subjective, but the other two are much more objective in nature, and can be easily gamified. AFAIK, AI has a long way to go before it can engage in anything that requires thinking critically.

I imagine AI could score very highly on the SAT.

There's Arimaa [0], designed by an AI researcher with the goal of favoring humans over AI. However on 2015 AI has overtaken humans in Arimaa.

[0] https://en.m.wikipedia.org/wiki/Arimaa

Try Magic: the Gathering.

>I remember reading somewhere that languages like Finnish and Hungarian are difficult for computers to parse

I wonder how much of that is due to AI researchers being speakers of Indo-European languages and not being able to wrap their mind around languages outside that family

Hmm, that's going to be a maybe.

If the AI needs to interpret the rules of a card based on it's text and figure out how to use them, it would indeed be a very difficult challenge.

If the AI can simply learn how to play the game with a predefined deck, it'll probably do just fine, outperforming humans but not all the time due to random chance.

I think you'd have to go even narrower by predefined the AI's opponent's deck as well before you'd get an AI that consistently outperformed humans. Even the most all in combo or burn deck will drop lose percentage points if they don't take into account what they're playing against and what hate cards to play around.

By predefined, I meant comprised from a pool of cards that the AI is familiar with. But now that I think about it, it is a much more interesting problem. Most of the big name bots, like the dota one, do have some model for picking a character. But the scope of choices is very limited to the point where even if it's "one model" it can have a large space dedicated to specifically that character. Would current techniques be sufficient to, given enough training data on each individual card, be able to compose a deck to fit arbitrarily assigned constraints and find a way to play it effectively? I don't know, but the answer sounds a lot closer to the idea of "strategy" that researchers are trying get at but missing the mark on in Starcraft and what not.

I have no idea how they'd handle that. It's a great way to prevent the bot from learning a single dominant strategy and trying to just execute it perfectly.

Only social games that require you to amuse your fellow participants, like Apples to Apples and the like. Even then, they'll beat people with poor social skills.

Role playing games.

Random dice games, like Yahtzee, are trivial to write programs to play "prefectly" ... it's just stats and your program will avoid both wishful thinking and pattern matching traps humans fall into.

I think it would be interesting to look for games that are the same kind of game as chess or Go (zero-sum games without randomness), but are harder for Alpha Zero than people. Something where it's hard to learn through self-play alone.

I would bet on drinking games

Calvinball?

https://xkcd.com/1002/

That comic is from 2012, and since then Arimaa, Go and Poker have moved solidly into the "Computers Can Beat Top Humans" category. Jeopardy would probably be there too if there was a consistent effort behind it. I think the Starcraft AI is pretty good these days, but people argue over things like APM restrictions.

Reply on news.ycombinator.com