[ Question ]

A game designed to beat AI?

by Long try1 min read17th Mar 202029 comments

13

Gaming (videogames/tabletop)AI
Frontpage

It's no surprise LW is dominated by COVID questions right now. My guess is that many of us are holding their ground at home and have more spare time than usual. So here is a question for you: if you are to design a 1v1-type board game and your purpose is to confuse the AIs, to make it as difficult for them as possible, to level the playground between humans & machines, or at least to prolong the period when human players have an upper hand over AIs; then what designs would you use, what elements would you introduce into the game?

Of course, the 2nd most important goal is to make an interesting game, one that fascinate people and keep them playing whenever they have free time - during pandemics, for example.

New Answer
Ask Related Question
New Comment

8 Answers

Arimaa was an earlier attempt to do this. Developed in 2003, a computer beat humans in 2015. This site summarizes some of its anti-AI properties as

  • On average there are over 17,000 possible moves compared to about 30 for chess; this significantly limits how deep computers can think, but does not seem to affect humans.
  • Opening books are useless since the starting position is not fixed. There are over 64 million ways to start the game.
  • End game databases are not helpful since a game can end with all pieces still on the board.
  • Research papers on Arimaa suggest it is more of a strategic and positional game with less emphasis on tactics.
1Max Hodges7moHow about if you have to solve brain teasers by visual analogy. For example: a card shows a drawing of a bear and a 12-inch ruler; answer is "BAREFOOT." A pair of dice showing the value of 2 (one and one); answer: "SNAKE EYES." The word "READ" between two lines; answer: "READ BETWEEN THE LINES." The word "agent" twice; answer: "DOUBLE AGENT." A picture of an Apple and the number 3.14158. You get the point.
1Max Hodges7moRIDDLES Riddle: What month of the year has 28 days? Answer: All of them Riddle: What is full of holes but still holds water? Answer: A sponge Riddle: What is always in front of you but can’t be seen? Answer: The future Riddle. What can you break, even if you never pick it up or touch it? Answer: A promise Riddle: A man who was outside in the rain without an umbrella or hat didn’t get a single hair on his head wet. Why? Answer: He was bald. Riddle: I shave every day, but my beard stays the same. What am I? Answer: A barber Riddle: You see a boat filled with people, yet there isn’t a single person on board. How is that possible? Answer: All the people on the boat are married. Riddle: A man dies of old age on his 25 birthday. How is this possible? Answer: He was born on February 29. Riddle: I have branches, but no fruit, trunk or leaves. What am I? Answer: A bank Riddle: What can’t talk but will reply when spoken to? Answer: An echo Riddle: The more of this there is, the less you see. What is it? Answer: Darkness
1Long try9moTks Kaj. I can see that this designer tried to fuck AIs up by the brute force way, which is not efficient and, well, not elegant. The game also kind of suffers from the same problem as Esperanto, that is it's way too "eurocentric". Those summaries from the site sound dubious. Of course that affects humans. This is like sacrificing most of your 2nd goal to get a tiny little bit ahead on your 1st goal. Absurd. Many strategy/abstract games, even chess, can end with all pieces alive. Reviews I read suggest otherwise. Moreover, the game claims that it's among the highest rated on BGG. Following the link reveals that it's down in the 40ish or 50ish ranks, below Go, Xiangqi, Shogi, and even Chess, which it aspires to improve from. Besides, there's a pattern I noticed from reading the reviews. Those high scores for Animaa usually come from earlier years, 2000s. Conversely, the recent ones are dominated by negative views. In them we can see those repeated complaints about slow pace, boring feel and stripping off of chess' aesthetics... So, I'd argue that Animaa isn't really an attempt to do what I asked in the question. It went solely for the 1st goal while completely ignoring the 2nd goal, which weigh about 40-45% of importance IMO. After all, the human element is just something we're having an edge over AIs. And what is a game if it doesn't have people playing??

Excellent question! Once again, late to the party, but here are my thoughts:

It's very hard to come up with any board game where humans would beat computers, let alone an interesting one. Board games, by their nature, are discretized and usually perfect information. This type of game is not only solved by AI, but solved by essentially a single algorithm. Card games with mixed strategy equilibrium like Poker do a little better, although Poker has been solved the algorithm doesn't generalize to other card games without significant feature engineering.

If I were to design a board game to stump AIs, I would use these elements:

  • Incomplete information, with the possibility of information gathering ("scouting") at a cost (like in Starcraft 2) to invalidate Markov property
  • Lengthy gameplay (number of moves) to make the credit assignment problem as bad as possible for RL agents
  • Patterns that require abstract reasoning to discern (e.g. the pigeonhole principle lets you conclude immediately that 1001 pigeons don't fit in 1000 pigeonholes; an insight that can't practically be learned through random exploration of permutations)

The last element in particular is a subtle art and must be used with caution, because it trades off intractability for RL against intractability for traditional AI: If the pattern is too rigid the programmer could just hard-code it into a database.

If we considered video games instead, the task becomes much easier. DOTA 2 and Starcraft 2 AIs still can't beat human professionals at the full game despite the news hype, although they probably can beat the average human player. Some games, such as Chronotron or Ultimate Chicken Horse, might be impossible for current AI techniques to even achieve average human level performance on.

2lsusr7moIn addition to your ideas, I would add long tales and chaotic systems. It's hard to train an AI on 1,000,000 datapoints when the value function of the 1,000,001st datapoint could outweigh all the previous cumulative results. To generalize this mathematically, a board game ought to have a value function that never converges [https://www.lesswrong.com/posts/xkWEJPwEArWFKH5jM/small-data#Divergent_Series] no matter how many times you play the game.
1Long try7moThanks a bunch Maxim! I remember you in my hypothetical "drop all water on Earth" question - so, a usually late guy but always arrives with excellent answers :) 1 of the main differences between board & card games that I can discern is that 1 has perfect info, as you pointed out, the other not. Thus if we integrate imperfect info into a board game, can programmers just combine the 2 algorithms to solve it, or they will have to find another approach? Unlike the Earth water question, I have some difficulties understanding the technical terms fully: * I don't really know SC2 but played Civ4, so by 'scouting' did you mean fogbusting? And the cost is to spend a unit to do it? What does it have to do with Markov property? Is fogbusting even possible in a real life board game? * Lengthy gameplay, IMHO, is bad when our 2nd goal is to attract people. Especially in this age of distraction, where youngsters can't concentrate for 20 minutes. * I learnt in a Crash course that computer science is essentially many layers of abstracting, so I'm a bit surprised when it turns out that AIs can't see the obvious 101 pigeons in 100 holes. Can we conclude that what separate us humans from AIs is that ability of insight? Also, I'm curious as to how you'd apply this last element in a real game example. * BTW, what is RL? Real-life? :) Video games has some advantages regarding AI over board games. While boards are restricted by real life physics & amount of materials (1 can't have 9 pawns in chess!), software offers virtually endless options & things to add. The amount of variations & positions are also tremendous, thus brute force is inefficient. The examples you linked show that. Therefore, it is in board games that we have to apply our ingenious the most to fuck those AIs up.
3maximkazhenkov7moYes. There has to be some cost associated with it, so that deciding whether, when and where to scout becomes an essential part of the game. The most advanced game-playing AIs to date, AlphaStar and OpenAI5, have both demonstrated tremendous weakness in this respect. Markov property refers to the idea that the future only depends on the current state, thus the history can be safely ignored. This is true for e.g. chess or Go; AlphaGoZero could play a game of Go starting from any board configuration without knowing how it got there. It's not easily applicable to Starcraft because of the fog of war; what you scouted inside your opponent's base a minute ago but isn't visible right now still provides valuable information about what's the right action to take. Storing the entire history as part of the "game state" would add huge complexity (tens of thousands of static game states). Yes, see Magic the Gathering for instance (it's technically a card game, but plenty of board games have card elements integrated into them). Or, replace chess pieces with small coin-like tokens with information about their identity written on the down-facing side (this wouldn't work for chess in particular because you can tell the identity by the way pieces move, but perhaps some other game with moving pieces). RL stands for reinforcement learning, basically all recent advances in game-playing AI has come from this field and is the reason why it's so hard to come up with a board game that would be hard to solve for AI (you could always reconfigure the Turing test or some other AGI-complete task into a "board game" but that's cheating). I'd even guess it's impossible to design such a board game because there is just too much brute force compute now.
1Long try7moAh, I see. All of your explanations led to 1 thing: imperfect information. Fogged Markov tiles or coin-like tokens are ways to confuse AI and force it to ramp up the brute power exponentially without much effort from the puzzler &/or much effect in game. And since it doesn't know the info, it can't accurately calculate the value of that info, that's why AI sucks at scouting. Coincidently, I've already invented a board game that incorporates imperfect info to beat AI back in 2016. I guess I'd need to put some more into it.
2maximkazhenkov5moI think I have found an example for my third design element: The old Nokia game snake [https://playsnake.org/] isn't technically a board game, but it's close enough if you take out the reaction time element of it. The optimal strategy here is to follow a Hamilton cycle [https://en.wikipedia.org/wiki/Hamiltonian_path], this way you'll never run into a wall or yourself until the snake literally covers the entire playing field. But a reinforcement learning [https://www.youtube.com/watch?v=-NJ9frfAWRo] algorithm wouldn't be able to make this abstraction; you would never run into the optimal strategy just by chance. Unfortunately, as I suggested in my answer, the pattern is too rigid which allows a hard-coded AI [https://www.youtube.com/watch?v=tjQIO1rqTBE] to solve the game.

Manual dexterity. I'm pretty sure I can whoop any AI at Jenga, for the next 3 years or so. And the more fiddly, the bigger my expected advantage - Men at Work is an example of an even more challenging game, with many more possible game states.

2Max Hodges7moGood idea! Maybe but something with more variety than Jenga. I'd bet hard-cash a dedicated team could make a Jenga champion in fraction of that time. Sounds like a fun challenge. Here's are a few impressive robot dexterity projects: https://openai.com/blog/learning-dexterity/ [https://openai.com/blog/learning-dexterity/] https://www.youtube.com/watch?v=kVmp0uGtShk [https://www.youtube.com/watch?v=kVmp0uGtShk] https://www.youtube.com/watch?v=ZiqC9emBk00 [https://www.youtube.com/watch?v=ZiqC9emBk00] https://www.youtube.com/watch?v=-KxjVlaLBmk [https://www.youtube.com/watch?v=-KxjVlaLBmk]
1Long try7moHmm. Well, anything physical can be a challenge to AI, since we don't have many real-life machines playing games physically. While technically the idea rings true, my question didn't intend to explore much of this approach :)

Machine learning is bad at situations where it is provided with limited training data. Therefore I would design a game with frequently-changing rules. In particular, I would create an expansion set for Betrayal at House on the Hill.

Betrayal at House on the Hill is about exploring a haunted house. The gimmick is you do not know the rules of the game before you begin playing. There are many different rules the haunted house might obey.

Humans could beat machines for a long time if the following two eratta were applied:

  1. An intelligence may not have access to information ahead of time about the expansion packs' rules. (It is fair play for the AI's programmers to have access to the base ruleset but not the special iteration-specific rulesets.)
  2. An intelligence only gets points for winning the first time it encounters a particular ruleset.

An AI would need to read the specialized rules on-the-spot and then understand the semantics well enough to devise a strategy. Then the computer would have to execute this strategy correctly on its first try. No software in existence today can do anything like this.

Not only could humans crush machines at this board game, today's best machine learning software cannot even play this game (follow the rules) without its programmers' reading the complete rulebook ahead of time, which is cheating.

As for goal #2, Betrayal at House on the Hill is my favorite board game.

Each player is provided with a board and a male assistant. They're not allowed to use anyone else's help. The winner is the first one to produce a human baby.

I believe this meets the second goal, too.

2lsusr7moYou could achieve a similarly lopsided result faster with the in-person Turing test, albeit at the expense of goal #2. RULES Each player guesses whether the opponent is human or machine. Each player gets one point for a correct guess and one point for convincing the opponent that he/she/it is a human. To beat humans at this, we would need the following developments: 1. A robotic body that can perform the same functions as human biology. 2. A robotic body aesthetically indistinguishable from a human body. 3. An artificial mind that can convincingly simulate human behavior.
1Long try7moI have to say, appropriate user name at that.

Riddles


Riddle: What month of the year has 28 days?
Answer: All of them

Riddle: What is full of holes but still holds water?
Answer: A sponge

Riddle: What is always in front of you but can’t be seen?
Answer: The future

Riddle. What can you break, even if you never pick it up or touch it?
Answer: A promise

Riddle: A man who was outside in the rain without an umbrella or hat didn’t get a single hair on his head wet. Why?
Answer: He was bald.

Riddle: I shave every day, but my beard stays the same. What am I?
Answer: A barber

Riddle: You see a boat filled with people, yet there isn’t a single person on board. How is that possible?
Answer: All the people on the boat are married.

Riddle: A man dies of old age on his 25 birthday. How is this possible?
Answer: He was born on February 29.

Riddle: I have branches, but no fruit, trunk or leaves. What am I?
Answer: A bank

Riddle: What can’t talk but will reply when spoken to?
Answer: An echo

Riddle: The more of this there is, the less you see. What is it?
Answer: Darkness

How about if you have to solve brain teasers by visual analogy. For example: a card shows a drawing of a bear and a 12-inch ruler; answer is "BAREFOOT." A pair of dice showing the value of 2 (one and one); answer: "SNAKE EYES." The word "READ" between two lines; answer: "READ BETWEEN THE LINES." The word "agent" twice; answer: "DOUBLE AGENT." A picture of an Apple and the number 3.14158. You get the point.

1Long try7moI think this approach tries to use puns to confuse AI... but it'll get old quickly for humans. Once the card is answered, it can no longer be of much value next times.
2Max Hodges7moThe same is true for Trivia Pursuit. The solution is the same: sell expansion sets. My idea doesn't even merit an upvote? ;) Here are some riddles which I think would be a challenge: And this one, from Zork, a text-based adventure game I played in the 80s
1Long try7moOK here's an upvote for you ;) Nevertheless, I do think that selling expansion sets is an exploitative way to milk money. Maybe I'm biased by my wanting to protect the environment & avoid too much waste...
1Max Hodges7moThanks! Was there any requirement that it needed to be a physical set? I assumed the AI would probably be interested in a digital environment. The set could have a bunch of "cards" to start; or maybe the whole thing is open-sourced if you're philosophically opposed to the idea of people making their own decisions about trading money for things they find valuable. But those issues seem rather secondary to the spirit of the challenge here.
1Long try7moNo, I'm not against that trading money for valuable stuffs part. And while the game can be digital, it does not hurt to have some physical sets for the human elements.
2Charlie Steiner7moI know several children who would play this game happily. As for re-use, many games have decks of problems or questions. Cranium or Trivial Pursuit, for examples - both use the same "roll, move, answer a question" kind of format that loosely wraps a progression/scoring mechanism around the trivia questions.
1Long try7moOf course it's to each their own, but while some children like those games, it doesn't mean they are great. Both Cranium & TP's scores on BGG are really low, indicating the majority of people don't like that approach. Our 2nd biggest goal is to make the game appealing to the population.

Couldn't you just pick a game that was most similar to the unsolved problems in AI? For example, you could say that the AI box experiment is a game.

0Long try9moEr... I'm not sure I follow. In the sentence, if the word "you" means "the individual me" then no, I don't think the AI box ex is a game. It's merely a thought experiment, and actually a pretty stupid one. If a box is designed to completely separate an AI from the real world then allowing it to interact with outside personnel destroys the purpose of the box in the 1st place. It's about as much a game to me as Roko's basilisk. If the word "you" mean "people in general" then no, unsolved AI problems are complicated and boring to the population. Something must be fun for people to consider it a game. Just because a part of LWers are obsessed with AI doesn't mean everyone is, too.
2Tetraspace Grouping7moThe AI Box game [http://yudkowsky.net/singularity/aibox], in contrast with the thing it's a metaphor for, is a two player game played over text chat by two humans where the goal is for Player A to persuade Player B to let them win (traditionally by getting them to say "I let you out of the box"), within a time limit.