How to design a turn-based game which is easy for humans but difficult for AI?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.