General Question

PhiNotPi's avatar

What are some board games that are difficult for a computer to play?

Asked by PhiNotPi (12677points) May 22nd, 2012

I am looking for a board game with extremely simple rules but which is extremely difficult for a computer to play. To be specific, I am looking for an abstract strategy game.

In many of our most popular board games (Chess, Checkers/Draughts) an advanced game engine can defeat even the most skilled human player.

With chess, while it is very hard for a person to make a really good move, it is relatively easy to make a relatively good move. This is because humans are very good at setting goals and sub-goals, and deciding a move that can accomplish this goal. We do not consider every possible chess move when deciding to use a pawn to capture the opponent’s queen.

Computers, however, like to brute-force solutions. This allows them to take into account so many possibilities that no human could possibly think that far ahead. This works fine in chess and checkers, but when there is a very large number of legal moves, then the computer can no longer look very far ahead.

I am on a quest to find a game such that no current computer can beat a skilled human. The game should have extremely simple rules, such that an ordinary person could easily memorize them.

So far, I have looked into Arimaa. Even though it does appear to be very hard for a computer to win, with a claimed 17,000 legal moves each turn, the rules are complicated. There are trapdoor spaces, pulling and pushing enemy pieces, and a complicated hierarchy of pieces.

I have also read about Go, which has a relatively large number of legal moves, but has more complex scoring rules, and an additional game phase in which players identify dead and alive stones before scoring.

Observing members: 0 Composing members: 0

19 Answers

Nullo's avatar

The trouble is that the computer is all about rules; you’d have to program in a handicap

PhiNotPi's avatar

@Nullo I am looking for a game such that simply brute-forcing the solution (for looking a few moves ahead) will take an extreme amount of time (longer than a time limit would allow). This provides a built-in handicap to a program that is not capable of human-like reasoning and planning.

lillycoyote's avatar

I was able to find this article about computers being unable to be humans at the game Go.. The article is 5 years old and I don’t know if computers have made any progress beating humans at Go since then. If you can think of other games that require the same skills, thought processes and strategies the keeps computers from beating humans at Go, you might be able to narrow your search down. And it’s the brute force thing that really makes the difference; that’s pretty much the advantage that computers have as you and the article point out.

Other than that, I’d suggest a game like Operation. It would be pretty hard for a computer to beat a human at that one.:-)

ragingloli's avatar

Probably one that is based on randomness, like Mensch-ärgere-dich-nicht

PhiNotPi's avatar

@ragingloli Although randomness will definitely add some difficulty for the computer, I believe that it makes it harder to measure a person’s skill level, and what percent of skill is just luck. That is why I limited it to abstract strategy games, so that the outcome of the game depends only upon the player’s skill. It’s just personal preference, if anything.

jerv's avatar

Go is still a pretty hard one to beat a human at. Part of it is that the size of the board precludes effective brute-force techniques. But as for those with simple rules….

The rules for Go are really not that complex, at least not compared to Chess; I place them about equal in complexity.

talljasperman's avatar

Twister and other games of dexterity… Also I have problems with team games where one needs to depend on a computer for support based on value judgments…Like Dungeons and Dragons in which you need to make decisions on the best course of action… Example will the computer know when to break the rules and when to follow them… throw a fireball into a group with both sides in close combat or not sacrifice oneself or another member or the party… to be selfish or not.

gambitking's avatar

Game-playing computers like chess computers, such as Deep Fritz, use a tree system to determine the best possible move (or the one with the least consequence). They literally check every possible path, one after the other to determine which move to make. At the start of a chess game, there’s twenty possible moves, pretty easy. But as it advances, it gets more complex but the parameters and goal really don’t change. The trees get bigger, and though there is a finite number of combinations possible for a given game of chess, the number is nearly infinite, more than the number of atoms in the universe.

So the complexity is a variable within the game and it’s because of the human opponent, also contributing to that variable. I love the episode of futurama where two robots are playing chess and the one playing white doesn’t even move a piece, he just says “mate in 246”, and the one playing black says “Awww, I have mate in 247, you win AGAIN”.

That said, you can consider chess pretty complex, and give computers like Deep Fritz plenty of credit. Games with more parameters, multiple goals or win conditions and additional pieces or basic fundamentals could fit the criteria of being overly complex for computers to handle but still simple for humans. But bear in mind the true test is interaction with the variable of the human opponent

Paradox25's avatar

There is a problem here, computers use computational logic. There are only two possible scenerios (for games) that I can think of which would give a computer a difficult time beating a person at: one would be a game similar to ‘Go’. Go is currently difficult for computers to beat a skilled person at because of the move possibilities, not because of the lack of ability to reason and actually think.

Computers didn’t always do well in chess until computers with more information processing ability became developed. Go and Chess are similar in that both games require tactical planning, allow for a wide array of potential moves (each move allowing for various potential outcomes) and simple rules. The problem at this time for programmers is that Go has many more move possibilities than even chess. Eventually a computer program will be developed that can whoop even the best Go player’s butt. Some programs can already play reasonably well (not great) on Go boards with lesser squares on them.

There is only one other scenerio that I can think of besides limited information processing ability that would give a computer a difficult time with a game beating a person at, a game that would rely upon non-computational logic to play well, maybe like charades or something similar (though not considered actual board games). As Penrose explains why consciousness works using non-computational logic, unlike artificial intelligence, he describes how non-computational logic is not about randomness, but the ability to understand a higher system of order like Godem’s Theorem describes. I’m sorry that I couldn’t actually give you a boardgame example, but maybe these links will help you find a potential answer by a greater understanding of how computational and non-computational logic works.

PhiNotPi's avatar

I think this question is starting to head into the wrong direction… Time for some course correction.

What I am looking for is a strategy game (a board game based completely on logic with no random component other than the opponent) that has very simple rules but that has a very large number of legal moves each turn.

This would make it very difficult for a computer to brute force a solution and trace every possible move, due to the large size of the game tree.

jerv's avatar

There was a point in time, back when Colossus was the most powerful computer ever, where even Tic-tac-toe would have qualified.

There was a time when solving the Enigma cipher took the entirety of Bletchley Park considerable time on the largest computer in the world, but nowasays you can do it on your phone. Breaking encryption is often a brute-force affair (assuming the algorithm is known) but modern computers have a lot more brute force. Things that would take my i3–530 desktop a few seconds would take my old 3.4 GHz Northwood P4 many minutes, my previous 200Mhz Pentium many hours, and my Vic-20 would probably require years.

With that in mind, when you saw, “very large number”, you have to bear in mind that it is relative to the ever-increasing number of calculations/second that computers are capable of.

RocketGuy's avatar

How about games that require bullshitting? Wouldn’t a computer get confused if you told it that you always lie?

jerv's avatar

@RocketGuy Why do you think Data sucks at Poker? For that matter, how do you think I often beat one of my Russian friends at Chess even though he could beat most other players? Thing is, that requires a bit of psychology , and modern computers are too logical to have that weakness; they have no feelings to cloud their judgement like my friend, and Data was susceptible to bullshitting merely because humans are random compared to a computer (or a Vulcan for that matter).

RocketGuy's avatar

@jerv – Logical!

lillycoyote's avatar

@jerv Yes, that’s kind of an interesting aspect of gameplay and computer-human interaction. I am trying to think of any games where the rules essentially allow “lying” as part of gameplay. Poker is one; bluffing is a form of lying in that you are pretending and trying to make your opponents think you have a better hand than you actually do. The only other one I can think of, off-hand, is baseball, which would be a difficult game for a computer to play, where the “surprise bunt” is, in a way, a form of “lying,” the way bluffing is in poker: the batter stance, his actions lead the opposing team to believe that he is going to take a real hit at the ball and then bunts.

Though, in each of these games, all games, humans are creatures of habit. Poker players have “tells” and have quirks, and personal strategies and a computer might be able ascertain probabilities as to the behavior of anyone player, given enough data. It might be possible for a AI computer to be programmed to, or learn to account for all those things. And baseball is a game of statistics in many ways, and whether a particular batter might be more or less likely to bunt, or be coached to bunt, under particular circumstances, might be something that a computer could be programmed to account for, if, at some point, a computer could be constructed that was capable of playing baseball.

What other games permit “lying” under their rules? Can you think of others? I think there are but I am drawing a blank now.

jerv's avatar

@lillycoyote I can think of none that are simple, but it is almost my bedtime.

lillycoyote's avatar

@jerv That’s O.K. Your brain needs rest as much, if not more, than anyone’s. You have to keep it rested and healthy so it is there for us when we need it. :-)

LostInParadise's avatar

@jerv mentioned poker. Does that count as a simple game of strategy? An individual hand will depend on chance, but in the long haul chances even out and success will depend on the skill of the player. Are there any poker playing computers?

What about the card game bridge? In duplicate bridge tournaments, the luck factor is reduced by giving every group of four the same cards. Are there any bridge playing computers?

Baloo72's avatar

As others have pointed out, Go is a pretty good option right now. TIL numerical estimates show that there are more possible games of go to be played out than atoms in the universe.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther