4
\$\begingroup\$

Until recently, Go used to be of the last bastions of turn-based no information-hiding games where world-class human players could not be defeated by computers. But now this bastion has fallen, as the program AlphaGo managed to beat one of the world top players.

However, Go was never designed as a game which is hard for AI. It was developed thousands of years ago. Being hard for computers was an unintentional side-effect of the game design, not a stated design goal.

What game mechanics make a turn-based strategy game without information hiding hard for AI, yet still playable for humans?


In case someone wonders "Why is this question also relevant for video game developers"?

  1. because it shows us how to design competitive multiplayer games where players can not cheat by using an AI assistant.
  2. For single player games it shows us what to avoid when we plan to add an AI opponent later.
\$\endgroup\$
  • \$\begingroup\$ You may be interested to read this, Facebook wrote AI to beat human players at Go: bbc.com/news/technology-35419141 \$\endgroup\$ – ManoDestra Mar 16 '16 at 20:35
  • 1
    \$\begingroup\$ I've been saying for a while that someone needs to figure out the rules for, and create, the Go/Chess hybrid game in the anime series Hunter x Hunter (post Greed Island, I forget the name of the mutant ant arc). That might have a computational space that exceeds even Go. \$\endgroup\$ – Draco18s Mar 17 '16 at 4:59
  • \$\begingroup\$ I think, to answer this question properly, one should be AI expert instead of game development expert. Therefore, it could be a good idea to ask this question on main SO instead. \$\endgroup\$ – Maxim Kamalov Mar 19 '16 at 0:04
  • \$\begingroup\$ All of them and none of them. No one wants play a game that is easy and its always difficult to make an AI for any game with any significant depth. \$\endgroup\$ – user2617804 Mar 23 '16 at 1:29
6
\$\begingroup\$

Go is difficult for computers because there are many, many possible moves for the player in each board state, too many for the computer to brute-force and calculate all possible outcomes (unlike, for example, tic-tac-toe).

Traditionally, chess playing computer programs would calculate all possible moves a few turns into the future and pick one of the moves that would lead to the "best" state, maximising the possible advantage of the computer player and minimising the possible advantage of the other player.

However, there's more possible moves in a complete game of chess than there are atoms in the universe, and this applies even moreso for Go, where there are many more possible board states. There are simply too many possible moves for a modern computer to calculate in any reasonable time. Instead, different approaches to AI need to be used to play "better" at games like Go, such as deepmind being able to "learn" how to get better at a task in a similar way to how real intelligence works (learning from trial and error).

So if you want to make an "open information" game hard for a computer? Have a very large amount of possible moves to make, nearly all of which could be a good move for the player.

\$\endgroup\$
3
\$\begingroup\$

When designing arbitrary turn-based game you have few options to make harder for AI, focusing on different aspects of AI:

  1. Abstraction (e.g. task "draw something beautiful")
  2. Feature extraction (e.g. from non gaming: captcha)
  3. Decision making: unfeasible bruteforce solutions (huge state space, e.g.the go)

Your best bet is on abstraction - you should aim to create too complicated abstraction to be approximated by a mathematical model.
You can also further annoy "cracking" the game with AI by giving it inputs that are harder to extract features from: an image or speech. Even if fed with input extracted with 99% accuracy, there is a chance for AI to receive wrong inputs, if it receives wrong inputs it is probably(depending on AI type) much more likely do make a wrong decision.
Or by using combinatorial explosion (go used this) in rule set. For example, if a turn was to play 1 card from 10 cards hand, there are 10 possibilities how to play the turn. If you were to choose 5 cards for that hand there are "n choose k" options, giving total 252 possibilities on that turn alone(!). Note: there are many other ways how to introduce something similar in a rule set.
None of above alone will make it impossible (the go is good example of that) but with careful design you could make it at least infeasible for a few years/decades.

A very, very simple game for illustration purposes using said suggestions:

Players takes turns, each one saying a single sentence. The goal is to tell a short story.

I think we can agree the quality of the story playing this game with average human players will be much better than any AI just as well as the fun for human players playing the game(this is ultimately the goal of games isn't it?). This game is probably even older game than go.
just a note: noticed how this game above incorporates all of the suggestions? The feature extraction from speech alone is not trivial task, paired with abstract goal of the game with insanely huge state space (natural language is infinite) makes it nearly impossible for AI to crack(=play better).


Edit: (for downvoters) please, look up definition of game(moreover the game above is just for illustration purposes): a physical or mental activity or contest that has rules and that people do for pleasure or

an activity that one engages in for amusement


Lets not limit games to something like Call of Duty.


Edit 2: In fact, it is really good question:

"But how would you rate the story generated by a storytelling game?"

This illustrates the arguments why games with at least some abstract rules are hard - this is exactly what AI would try to ask: how do I measure it, how do I describe it with an equation? AI is not capable to think out of the box or make complex abstractions (such as having fun). The correct answer is:

You dont. And that is exactly what makes it hard for AI.

\$\endgroup\$
  • 4
    \$\begingroup\$ But how would you rate the story generated by a storytelling game and decide who is the winner? \$\endgroup\$ – Philipp Mar 16 '16 at 19:52
  • \$\begingroup\$ You did not said anything about winning but a game difficult to play. Anyhow, I also provided ways of designing games difficult for AI. \$\endgroup\$ – wondra Mar 17 '16 at 8:09
  • 4
    \$\begingroup\$ sorry, won't take that flamebait. \$\endgroup\$ – Philipp Mar 17 '16 at 8:46
  • \$\begingroup\$ It makes me rather sad, that saying that titles like Witness and Stanley Parable are games baits you to flame against. \$\endgroup\$ – wondra Mar 17 '16 at 9:22
  • 1
    \$\begingroup\$ Comments aren't ideal for long discussion so I won't pursue this further here - feel free to message me on chat/Twitter if you'd like to talk more. I think we should avoid assuming disagreement means they haven't read or understood. As I outlined in my first comment, Philipp raised a valid concern that measurable/comparable success is a core element of some approaches to games, which is in tension with some of your suggestions. This isn't wrong or unrelated, and it's not motivated by ignorance or a failure to read. You can decline to address that tension, but it is still valid to comment on. \$\endgroup\$ – DMGregory Mar 23 '16 at 19:02
2
\$\begingroup\$

Short answer: Increase the number of variables.

Why? Chess was "easy" for a computer to beat because there are only a certain number of pieces and possible moves. Go was "harder" because there were more possible moves. A game that is even harder for a computer will have even more possible moves.

Example: Strategy games. I have yet to play an RTS* where the computer can win against an experienced human without cheating. Why? The number of variables. Resources, the effects of resources over time (do you use them to get more resources, do research, or produce units?), how scouting and intelligence is handled, and how the plethora of available units are managed. You could probably tell a computer how to "kite" long range units, but telling it when to kite, for how long, when to make those units, etc. etc. with the combination of every other unit and its possible uses would be nearly impossible.

Asking a computer to simulate every possible move in chess and the response that is guaranteed to win against that move is trivial with today's computers. Asking a computer to simulate every possible click in an RTS with resources, research trees, and complex unit types is likely impossible. Yet even inexperienced humans can master the basic elements of these games with relative ease compared to the computer programming necessary.

*I know I am using RTSs as an example but any RTS can theoretically be made into a very similar turn-based strategy game.


Another thought: you could also pick a task that humans already find easy but that is actually very complex, like folding laundry, and make that into a turn-based game. Players could take turns folding a piece of clothing -- every turn is one piece of clothing -- and the player who has taken the least amount of time to complete 5 turns wins.

We find this simple because we have a conception of what words like "up" and "inside-out" mean -- take a shirt, make sure it's "right side in," lay it "flat on the table" so the "collar" is "away from you," take the "sleeve..." etc. etc. As a human, you know what all the phrases/words in quotes mean; essentially, you have simplified a basically infinite number of variables into instructions that take only a few words. Explaining that to a computer is more or less impossible. And even if you explain it for one shirt, will the computer know every shirt? Long sleeve? Short sleeve? Button up? What if the collar is popped? etc.

\$\endgroup\$
  • \$\begingroup\$ Actually, you are only partially correct: on one hand it is true that bruteforce method would fail due to the number of possibilities but it is not the only way of solving it. RTS AI are usually made with decision trees - if you built one analyzing billions of games played by pros and casuals alike and fed the data to deep ANN, it would probably outperform proffesional players(look at SCII meta - players are measure by actions per minute, and computers are usually *pretty good *at doing many quick consecutive actions). \$\endgroup\$ – wondra Mar 23 '16 at 18:21
  • \$\begingroup\$ The trouble with cracking RTS I think is that there is usually no API and thus feature extraction would be very problematic (see my answer ), second there is usually no demands for it(nobody wants to implement AI players cant beat in their game), third there is usually small training set available(too few games to analyse). \$\endgroup\$ – wondra Mar 23 '16 at 18:24
-1
\$\begingroup\$

The reason that Go was so hard for computers was because it took a lot of intuition to play it well. Computers do not possess intuition but they possess an immense amount of processing power and memory which can be used to find patterns, really what a computer does when analysing data.

Your question is hard to answer because if a computer can find patterns it can develop strategies based on that data. Computers can only make perfect choices given the data at the time (which we will some times look at as mistakes but really it's because the data was missing, incomplete or misleading).

So I think the answer you are looking for is: Make games that require a lot of intuition, like Go.

\$\endgroup\$
  • 1
    \$\begingroup\$ But what does "Intuition" even mean and how do problems "requiring intuition" differ from simple pattern recognition problems? \$\endgroup\$ – Philipp Mar 16 '16 at 13:07
  • 1
    \$\begingroup\$ It's basically like, acquiring knowledge without the use of reasoning. The word itself stems from the latin word "Intueri" which translates to "Consider" or "To contemplate". The reasoning for us experiencing intuition is (to my knowledge) largely unknown and is not the same as rational thinking. But really it's a philosophy discussion at this point, what Intuition is and what causes it. \$\endgroup\$ – OmniOwl Mar 16 '16 at 13:09
  • 2
    \$\begingroup\$ You are asking a somewhat philosophical question so you can't expect an exact answer. \$\endgroup\$ – OmniOwl Mar 16 '16 at 13:56
  • 1
    \$\begingroup\$ @Philipp, as I see it, you're being unreasonably critical, and downvoting this answer was unnecessary. He's right: That is a deeply philosophical question. Why don't you explain intuition? Criticising / discussing other people's views in order to learn from them is one thing, but taking points from new users to drop their answer below zero is just ugly, and unnecessary. We want positive outcomes on this site, not negative ones. I hope you'll remember that these are the same people who put you and I in the top 10 or 20 of this site. So be kind. \$\endgroup\$ – Engineer Mar 16 '16 at 21:00
  • 1
    \$\begingroup\$ @ArcaneEngineer Thanks man :) It's okay I'll still frequent the page :D \$\endgroup\$ – OmniOwl Mar 16 '16 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.