A game designed to beat AI?
post by Long try · 2020-03-17T03:51:33.199Z · LW · GW · No commentsThis is a question post.
Contents
Answers 11 Kaj_Sotala 6 maximkazhenkov 5 Charlie Steiner 2 lsusr 2 Max Hodges 1 seed 1 Max Hodges 1 Zian None No comments
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.
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.
↑ comment by Max Hodges (max-hodges) · 2020-05-05T14:41:48.036Z · LW(p) · GW(p)
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.
↑ comment by Max Hodges (max-hodges) · 2020-05-06T10:23:37.533Z · LW(p) · GW(p)
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
↑ comment by Long try · 2020-03-18T04:54:09.388Z · LW(p) · GW(p)
Tks 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.
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.
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.
End game databases are not helpful since a game can end with all pieces still on the board.
Absurd. Many strategy/abstract games, even chess, can end with all pieces alive.
Research papers on Arimaa suggest it is more of a strategic and positional game with less emphasis on tactics.
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.
↑ comment by lsusr · 2020-05-14T04:19:12.017Z · LW(p) · GW(p)
In 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 [LW · GW] no matter how many times you play the game.
↑ comment by Long try · 2020-05-04T04:50:32.320Z · LW(p) · GW(p)
Thanks 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.
Replies from: None, None↑ comment by [deleted] · 2020-05-13T13:44:01.237Z · LW(p) · GW(p)
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? Is fogbusting even possible in a real life board game?
Yes. 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.
What does it have to do with Markov property?
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).
Is fogbusting even possible in a real life board game?
Yes, hidden identity chess for instance.
BTW, what is RL?
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.
Replies from: Long try↑ comment by Long try · 2020-05-14T02:58:47.421Z · LW(p) · GW(p)
Ah, 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.
↑ comment by [deleted] · 2020-06-23T21:53:32.696Z · LW(p) · GW(p)
I think I have found an example for my third design element:
Patterns that require abstract reasoning to discern
The old Nokia game snake 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, this way you'll never run into a wall or yourself until the snake literally covers the entire playing field. But a reinforcement learning 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 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.
↑ comment by Max Hodges (max-hodges) · 2020-05-06T10:17:16.953Z · LW(p) · GW(p)
Good 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://www.youtube.com/watch?v=kVmp0uGtShk
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:
- 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.)
- 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.
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.
↑ comment by Long try · 2020-05-06T04:49:25.279Z · LW(p) · GW(p)
I 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.
Replies from: max-hodges, Charlie Steiner↑ comment by Max Hodges (max-hodges) · 2020-05-06T10:07:44.105Z · LW(p) · GW(p)
The 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:
What occurs only in the middle of each month, in all of the seasons, except summer and happens only in the night, never in the day?
And this one, from Zork, a text-based adventure game I played in the 80s
What is as tall as a house, round as a cup, and all the king's horses can't draw it up?Replies from: Long try
↑ comment by Long try · 2020-05-07T09:26:31.025Z · LW(p) · GW(p)
OK 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...
Replies from: max-hodges↑ comment by Max Hodges (max-hodges) · 2020-05-07T09:48:31.817Z · LW(p) · GW(p)
Thanks! 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.
Replies from: Long try↑ comment by Charlie Steiner · 2020-05-06T06:59:06.390Z · LW(p) · GW(p)
I 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.
Replies from: Long try↑ comment by Long try · 2020-05-07T09:23:24.544Z · LW(p) · GW(p)
Of 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.
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.
↑ comment by lsusr · 2020-05-14T03:30:59.428Z · LW(p) · GW(p)
You 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:
- A robotic body that can perform the same functions as human biology.
- A robotic body aesthetically indistinguishable from a human body.
- An artificial mind that can convincingly simulate human behavior.
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
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.
↑ comment by Long try · 2020-03-19T04:40:39.899Z · LW(p) · GW(p)
Er... 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.
Replies from: tetraspace-grouping↑ comment by Tetraspace (tetraspace-grouping) · 2020-05-07T22:05:33.139Z · LW(p) · GW(p)
The AI Box game, 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.
No comments
Comments sorted by top scores.