Reply
 
Thread Tools Display Modes
  #51  
Old 03-01-2014, 01:08 PM
Jonathan Chance is offline
Domo Arigato Mister Moderato
Moderator
 
Join Date: Apr 2000
Location: On the run with Kilroy
Posts: 22,571
Quote:
Originally Posted by RTFirefly View Post
Diplomacy. When the world Dip champ is a computer, I'll acknowledge that the goal of 'true AI' has been achieved, or at least close enough as to make no difference.

I'm surprised that a pair of computers haven't already been able to outplay the best humans.

Even with their wifi turned off.
Hmm. I should host a Dip game, RT. Maybe Facebook based.

You in?
  #52  
Old 03-03-2014, 08:08 PM
RTFirefly is offline
Charter Member
 
Join Date: Apr 1999
Location: Maryland
Posts: 38,528
Quote:
Originally Posted by Jonathan Chance View Post
Hmm. I should host a Dip game, RT. Maybe Facebook based.

You in?
Alas, no. I just don't have the time for it these days. But thanks for asking!
  #53  
Old 03-03-2014, 08:36 PM
septimus's Avatar
septimus is online now
Guest
 
Join Date: Dec 2009
Location: The Land of Smiles
Posts: 19,125
One factor to consider is play against opponent weaknesses. Play may be considered "perfect" when any winnable game is won, and any drawable game is drawn, but a good player must also know how to induce opponent errors. For example, an excellent poker program might have a positive expectation against any individual player, but not be the fastest money winner at a table.

Quote:
Originally Posted by Aeschines View Post
BTW, chess and go definitely cannot be "solved" in the conventional sense with a digital computer. The solution tree would require all the atoms in the universe to store in any conceivable material format.
Nitpick: The number of chess positions is less than 1047. The number of distinct possible games may be more than the universe's atoms, but there would be no need to store them all -- a few bits per possible position would suffice to prepare or depict the complete solution.
  #54  
Old 03-03-2014, 09:42 PM
Chronos's Avatar
Chronos is offline
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 82,728
Quote:
Quoth Aeschines:

It may be possible, however, in the future for a quantum computer to solve chess for any particular position and play perfectly.
I thought that for a long time, too, but it turns out that smarter minds than I have already calculated some limits on the sorts of problems quantum computers can solve, and chess is provably outside of that space.

That said, though, it's still conceivable that someone will someday find some very clever trick to solve chess without brute force, similarly (in principle) to how Nim is solved without brute force. It's also conceivable (a lot more so) that, even without provably solving chess, computers will get so good at it that they'll either always win with white or always draw with black, making the game, in practice, solved.
  #55  
Old 03-03-2014, 10:19 PM
Chessic Sense is offline
Guest
 
Join Date: Apr 2007
Posts: 6,698
Quote:
Originally Posted by Aeschines View Post
I'm curious about the state of chess AIs vs. humans at this point. I would break my question down like this:

1. Will the best chess AI always beat *any* human in a tournament?

2. Will the best chess AI always beat any human in a single game? (I know this was not true in the second series of Deep Blue vs. Kasparov. IIRC, DB won 2, K won 1, and there were three draws.)

3. If the computer will not necessarily win, can a human reliably play for a draw? IOW, could it be possible that human chess playing ability will remain high enough to draw against any AI for the foreseeable future?

BTW, chess and go definitely cannot be "solved" in the conventional sense with a digital computer. The solution tree would require all the atoms in the universe to store in any conceivable material format. It may be possible, however, in the future for a quantum computer to solve chess for any particular position and play perfectly.
1. It depends on the time control. The shorter the time control, the more favorable for the computer. Humans think slow by comparison, so it's not so much a computer advantage as it is a human disadvantage. At standard time control (40 moves, 120 minutes+60minutes sudden death), I can say that the human will likely never, ever win. He can draw, though.

2. Not at all. Chess itself has a problem with draws. There are many positions where a side can have a better position but not be able to convert it. So a Grandmaster has a little bit of room for error. By the way, Deep Blue is the equivalent of a car phone...completely obsolete and outclassed in every way. Today's top engine is Houdini 3, though Houdini 4 was just released. Runners-up are Rybka, Komodo and Stockfish. Honorable mention to Deep Fritz.

3. Depends on if you let the human research the engine first. Carlsen might be able to prepare a drawing line against a known opponent. I certainly have found a few against Houdini 4, but I'm not skilled enough to hold the draw once I've reached it. All you have to do is find closed positions and memorize how to keep them closed. Not that hard.



This is all assuming you're using the top performance platform for the engine. If you install it on a phone and turn off Ponder (i.e. "think on human's time"), yeah, you could beat it. Here's a famous game where America's #1 beats Rybka in 2008.
  #56  
Old 03-10-2014, 07:37 PM
shijinn is offline
Guest
 
Join Date: Feb 2003
Location: waist deep in ink
Posts: 4,197
who will win in a game of Ping Pong? answer in about 3 hours. probably later if the site crashes.

website - http://www.kuka-timoboll.com/en/home/
youtube trailer - https://www.youtube.com/watch?v=_mbdtupCbc4
  #57  
Old 03-10-2014, 11:35 PM
shijinn is offline
Guest
 
Join Date: Feb 2003
Location: waist deep in ink
Posts: 4,197
wow that was lame. i was expecting a real match and got a lousy, shaky cam commercial instead.

Last edited by shijinn; 03-10-2014 at 11:36 PM.
  #58  
Old 05-10-2019, 08:37 PM
Jophiel's Avatar
Jophiel is offline
Guest
 
Join Date: Mar 1999
Location: Chicago suburbia
Posts: 19,016
Quote:
Originally Posted by Jophiel View Post
Yeah, I'd suspect that you could program an AI to do well with a single tight deck, especially if you're limiting the deck choices for the opponent. I'd consider that a pretty narrow definition of "playing Magic" though and wouldn't be especially impressed by it. Unlike board games like chess or even games like poker, too much of Magic involves the ability to build something from a vast assortment of (potentially randomly assigned) cards and I can't imagine the AI holding up under a draft tournament situation, for example. Even if you're not talking draft, if the AI is having a human-constructed deck handed to it with specific instructions how to play it, it's not really the AI doing 75% of the job (deck construction).
Years later and science has determined that computers can't learn how to play Magic: the Gathering in a "perfect" way. That link leads to the actual research paper about it (which is a somewhat amusing read to see M:tG cards get tossed about in a research paper) but I'll steal a few quotes from Kotaku to give you the gist of it:
Quote:
Human players might not be alone in feeling overwhelmed: A new research paper argues that the game is so complex that there are even cases where a computer theoretically wouldn’t be able to figure out how to win.

A group of researchers argues that Magic: The Gathering is so complex there are cases in which it would be impossible for a computer to figure out a fool-proof way to win. “This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” they write.
[...]
What they ended up finding was that Magic: The Gathering isn’t just more complex than most other games, it’s actually noncomputable in some cases. It’s yet unclear just how many of those cases there are, but there are currently conceivable matches where there’s no way an algorithm can figure out the optimal path to victory.

Last edited by Jophiel; 05-10-2019 at 08:38 PM.
  #59  
Old 05-10-2019, 09:20 PM
Kobal2's Avatar
Kobal2 is offline
Guest
 
Join Date: Mar 2008
Location: Paris, France
Posts: 17,758
Quote:
Originally Posted by Jophiel View Post
Years later and science has determined that computers can't learn how to play Magic: the Gathering in a "perfect" way. That link leads to the actual research paper about it (which is a somewhat amusing read to see M:tG cards get tossed about in a research paper) but I'll steal a few quotes from Kotaku to give you the gist of it:
I mean, that's a given - MTG is as much about bluffing and knowing your opponent's likely deck composition as it is about using your own cards and abusing the byzantine rules.
__________________
--- ---
I'm not sure how to respond to this, but that's never stopped me before.
  #60  
Old 05-10-2019, 10:03 PM
Arrogance Ex Machina's Avatar
Arrogance Ex Machina is online now
Guest
 
Join Date: Jul 2010
Location: Lappeenranta, Finland
Posts: 1,561
It's amusing to see that the two first replies in this 5 years old thread are both obsolete by now.
  #61  
Old 05-11-2019, 07:28 AM
Chronos's Avatar
Chronos is offline
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 82,728
I expect that what they found was something analogous to the Halting Problem. I don't think the rules of M:tG are quite Turing-complete, but they may well be complex enough to make something like that an issue, anyway.

Of course, that'll only come up in extremely contrived corner cases that are unlikely to come up in any real game.
  #62  
Old 05-11-2019, 03:01 PM
lisiate is online now
Guest
 
Join Date: Apr 2007
Posts: 3,640
Quote:
Originally Posted by Arrogance Ex Machina View Post
It's amusing to see that the two first replies in this 5 years old thread are both obsolete by now.
Yep. Boy did I underestimate the pace of AI development.
  #63  
Old 05-11-2019, 07:38 PM
Chronos's Avatar
Chronos is offline
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 82,728
Oh, it should also be mentioned that the computers' inability to conclusively solve M:tG does not imply that humans will always be better at it, because humans can't conclusively solve it, either. It would still be theoretically possible (though still a long ways away) to create a computer better at it than a human.

Note that by "better at it", I mean at all aspects of the game: I wouldn't be too surprised if you could take a simple deck like Relentless Rats or green zoo, and teach a computer to play it better than a human. But being able to construct a good deck, that's another story.
  #64  
Old 05-11-2019, 09:49 PM
Kent Clark's Avatar
Kent Clark is offline
You mean he's STILL here?
Charter Member
 
Join Date: Apr 1999
Posts: 25,732
Monopoly. A game with two roughly equally skilled players is already tedious. Against a computer it would be unbearable.
  #65  
Old 05-11-2019, 10:20 PM
Ike Witt's Avatar
Ike Witt is offline
Friend of Cecil
Charter Member
 
Join Date: Aug 1999
Location: Lost in the mists of time
Posts: 14,536
I assume no computer can win at Dance Dance Revolution.
  #66  
Old 05-11-2019, 11:31 PM
pool is offline
Guest
 
Join Date: Jul 2002
Location: Inside
Posts: 4,339
"Not all missions can be solved with chess Deep Blue, someday you'll understand that" - Al Gore
__________________
"You can do anything you set your mind to...But money helps"
  #67  
Old 05-11-2019, 11:59 PM
octopus's Avatar
octopus is offline
Guest
 
Join Date: Apr 2015
Posts: 8,243
Quote:
Originally Posted by Chronos View Post
I expect that what they found was something analogous to the Halting Problem. I don't think the rules of M:tG are quite Turing-complete, but they may well be complex enough to make something like that an issue, anyway.

Of course, that'll only come up in extremely contrived corner cases that are unlikely to come up in any real game.
You may find this article on Magic interesting. https://arxiv.org/pdf/1904.09828.pdf
  #68  
Old 05-12-2019, 12:36 AM
Jophiel's Avatar
Jophiel is offline
Guest
 
Join Date: Mar 1999
Location: Chicago suburbia
Posts: 19,016
Quote:
Originally Posted by Ike Witt View Post
I assume no computer can win at Dance Dance Revolution.
I'd like to see one of those Boston Dynamics robots try.
  #69  
Old 05-12-2019, 07:28 AM
Ike Witt's Avatar
Ike Witt is offline
Friend of Cecil
Charter Member
 
Join Date: Aug 1999
Location: Lost in the mists of time
Posts: 14,536
Quote:
Originally Posted by Jophiel View Post
I'd like to see one of those Boston Dynamics robots try.
Shit, I forgot about those backflipping bastards. Oh well. I for one, welcome our new robot overlords.
  #70  
Old 05-12-2019, 01:38 PM
Shoeless's Avatar
Shoeless is offline
Charter Member
 
Join Date: Jan 2003
Location: The Sunflower State
Posts: 6,552
I'd like to see three or four different AIs cooperatively play...and win...a game of "Pandemic".
  #71  
Old 05-12-2019, 05:00 PM
Chronos's Avatar
Chronos is offline
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 82,728
Yeah, octopus, that's the one Jophiel linked, and which I've since read through. It's exactly the halting problem: One of the official rules of Magic is that if the game ends up in an infinite loop, it's a draw... but the problem is, there's no general way to tell if a computer program is in an infinite loop, or if it'll end eventually, just not yet. And someone figured out a way to implement a computer, capable of running an arbitrary program, in a Magic game, set up in such a way that if the program eventually halts, then one player will win. Set up the game that way (which they found a way to do on the first turn, if you get just the right hand), and program it with something like the Goldbach conjecture whose truth we don't yet know, and the game is over, but we don't know if it's a draw or a win.
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 02:54 PM.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@straightdope.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Copyright 2018 STM Reader, LLC.

 
Copyright © 2017