Hacker News Reader

Comment by mrob | Hacker News Reader

Deep Blue did not use brute force search. Like all successful chess engines, it used heuristics to estimate the value of board positions, and focused its search on the positions that looked most promising. A truly "indiscriminate" search would waste so much time on losing positions that even I could beat it.

View on HN

Yes. The challenge now is to come up with a game for which heuristics don't work :)

Considering heuristics is the only tool humans have, such a game is inherently unplayable.

Heuristics are also what make games fun and learnable. "I am thinking of a number between 1 and 10e256" has no learnable heuristics, for example.

17?

Darn it! You got me :-)

What's most interesting to me is that if the human is picking the random number, there are heuristics you could use to guess it. A birthday, for example. A favorite number perhaps. But perfect play is easy and requires brute force search.

One of my favorite numbers is 355/113 but it's still hard to guess.

Sure it has. For example, 42 is more likely than 48884566544542789. People play rock-paper-scissors competitively and good players win more often than a pure chance would imply.

Snakes and ladders? https://xkcd.com/1002/

Some games were designed to be difficult for computers, primarily by having a large branching factor. Aarimaa [1] seems to be holding up so far. Octi [2] is perhaps too obscure to get much attention and Havannah [3] has been defeated in the years since the author invited computer challengers to try.

[1] https://en.wikipedia.org/wiki/Arimaa#World_Computer_Champion...

[2] https://boardgamegeek.com/boardgame/450/octi

[3] https://en.wikipedia.org/wiki/Havannah#Computer_Havannah

> Aarimaa seems to be holding up so far.

Not anymore it looks like:

In 2015, the challenge was won decisively by the computer (Sharp by David Wu), with top players agreeing that computers had become better at the game than humans.

Yeah, but when is a computer going to beat someone in Melee? Not in a long time. There's too many possible moves. It's not boxed-in and easy to mathematically calculate like Chess. Sure some games like Chess might be able to unlock the potential of super-computers to destroy us, but I have doubt about other gaming AI.

    s/melee/go/g

If we now need to resort to games neither me nor my dictionary have heard of before, AI research must be doing something right.

So you are the barometer

I think that in this context, "melee" refers to Super Smash Brothers Melee: https://en.wikipedia.org/wiki/Super_Smash_Bros._Melee

Didn't this already happen?

https://arxiv.org/abs/1702.06230

The player wasn't the world's best IIRC. So its kind of a click-bait article. I'm sure the AI does well, but when I saw the match it was very mechanical. I feel like if a human played against it enough, maybe a flaw would be found.

AIs have significant advantages in reaction speed however, so I bet that a properly-programmed AI will beat any human. If an AI is reading from memory (while the human reads from the screen), a decently programmed AI will almost certainly win.

The question of whether or not an AI would beat a human with similar lag delays is an open question however. That paper didn't seem to have any lag delays programmed into the AI however, and was just reading from memory IIRC. I don't see a fair way of doing this however: human reaction times are based on mood, emotion, and current state of mind.

Machines will have a consistent reaction speed, and therefore a huge advantage in any twitch-based game.

Did they even play against a human player? I didn't see results from person vs bot matches.

https://www.youtube.com/watch?v=dXJUlqBsZtE&t=300s

I've seen the discussion elsewhere. The CPU player is certainly good, far better than I'd expect from an AI. But there are significantly questionable moves: like random F-Smashes and other such attacks that just don't seem optimal to me.

Not that I'm an expert or anything. But its clear to me that the bot has superhuman reflexes and precision (a bunch of perfect blocks that really shouldn't happen... the huge length of the dash-dances... the fact that the AI basically always "Sweetspots" the F-Air Knee). And that's its primary edge. Its strategic planning is kind of awful, and its quite evident from the match.

For example, this is extremely unhuman and basically impossible to precisely execute with a normal controller: https://www.youtube.com/watch?v=dXJUlqBsZtE&t=104s

The AI also seems unable to punish the low-recovery of the Humans: so the Humans always recover low safely. (If you recover high on the other hand: the AI is damn perfect at edge guarding so its a death sentence)

To me it always seemed like fighting games AIs could easily beat a human if we let them run at full speed.

If the bot only does frame perfect combos the human won't stand a chance, do they?

Reply on news.ycombinator.com