6 ms·
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
by keiferski 6y ago
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 https://news.ycombinator.com/item?id=21572261
- monsieurbanana 6y agoI 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
- gowld 6y agoCodenames is easyfor an all-computer team; it's simply a word vector problem. There are already AIs published. Pictionary might be harder.
- warrenq 6y agodude, get with the program :) https://quickdraw.withgoogle.com/ https://quickdraw.withgoogle.com/
- monsieurbanana 6y agoAh yes, I was thinking of codenames the picture version.
- sasaf5 6y agoThere'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 https://en.m.wikipedia.org/wiki/Arimaa
- chillee 6y agoRandomness 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.
- wrsh07 6y agoI 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-complex-cooperative-games-with-hidden-information/ https://ai.facebook.com/blog/building-ai-that-can-master-com...
- chillee 6y agoHanabi 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.
- Ensorceled 6y agoOnly 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.
- jasim 6y agoAgglutinative 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-complexity/ 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.
- tjah1087 6y agoAny 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_Clue https://en.m.wikipedia.org/wiki/I%27m_Sorry_I_Haven%27t_a_Cl...
- tanjtanjtanj 6y agoActually, 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.
- tialaramex 6y agoDixit 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.
- whack 6y agoLeetcode 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.
- ummonk 6y agoI imagine AI could score very highly on the SAT.
- exDM69 6y agoNot 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.
- erfgh 6y agoWait, I thought autonomous cars are almost out. You ruined my excitement.
- aidenn0 6y agoAutonomous cars can solve the problem of close-pack driving by avoiding close-packs. That's a great way to lose a race though...
- klmadfejno 6y agoI get that this is true of real cars, but is it really true of simulated cars? Can you share an example?
- exDM69 6y agoThere 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.
- klmadfejno 6y agoDo 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).
- glaberficken 6y agoBridge (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 https://en.wikipedia.org/wiki/Computer_bridge
- tanjtanjtanj 6y agoThat's because the AI isn't allowed to cheat. The skill of "world class" bridge play mainly lies in creative ways to cheat.
- User23 6y agoI 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.
- tanjtanjtanj 6y agoWell 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.
- User23 6y agoI 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.
- 6y ago
- throwaway49990 6y agoTry 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
- klmadfejno 6y agoHmm, 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.
- grraaaaahhh 6y agoI 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.
- klmadfejno 6y agoBy 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.
- scotty79 6y agoDodgeball. Cup stacking. Or any other game that requires bipedal movement or quick and precise adaptive manual manipulation.
- warrenq 6y agododgeball is solved https://www.youtube.com/watch?v=MHTizZ_XcUM https://www.youtube.com/watch?v=MHTizZ_XcUM
- tingle 6y agoMaybe Diplomacy ? https://en.wikipedia.org/wiki/Diplomacy_(game) https://en.wikipedia.org/wiki/Diplomacy_(game)
- mellosouls 6y agoThis 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.
- bratao 6y agoI would bet on drinking games
- recursivecaveat 6y agoStarting 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.
- tialaramex 6y agoYou'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/ 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.
- klmadfejno 6y agoAI 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.
- 3PS 6y agoRecently 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/S0004370219300116 https://www.sciencedirect.com/science/article/pii/S000437021... [2] https://arxiv.org/pdf/1912.02318v1.pdf https://arxiv.org/pdf/1912.02318v1.pdf
- awal2 6y agoCalvinball? https://xkcd.com/1002/ 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.
- QuesnayJr 6y agoI 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.
- wrsh07 6y agoEven 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-single-demonstration/ 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