AI's Game Playing Challenge - Computerphile
ฝัง
- เผยแพร่เมื่อ 13 พ.ค. 2024
- AlphaGo is beating humans at Go - What's the big deal? Rob Miles explains what AI has to do to play a game.
What on Earth is Recursion?: • What on Earth is Recur...
Object Oriented Programming: • Pong & Object Oriented...
Mixed Reality Continuum: • Mixed Reality Continuu...
AI Playlist: AI Playlist: • Artificial Intelligenc...
Many thanks to Nottingham Hackspace for providing the location and being downright awesome
Easter Egg: • Game Playing AI Easter...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
Camera Guy: 'I just wan't to make sure people understand what we're talking about'
Scientist guy: 'Yeah yeah, right right. So you draw your octothorp'
Camera Guy: [sighs internally]
Hahahaha exactly!
HammerspaceCreature: 'I just wan't to [...]'
Linguists: [sighing internally]
@@irrelevant_noob Non-linguist here: what's the issue with "just want to"?
Avraham Ish Shalom care to look again at what i actually quoted? :-B
Octothorpe*
At 10:08 you can see Rob deciding that he will turn the whole universe into a paper factory, but having his decision overran by his safety algorithm, on the argument that turning the universe into factories would lower his utility function of learning from, and sharing ideas with, different beings.
Underrated comment.
he somehow got to the big red button
*Looks at board in dismay* "All I do is win"
Would you like to play a game against me?
Si nu am mai avut timp să ne mai mai multe detalii 99 bun și
Suffering from success
Like Ultima?
I really like this guy. He's interesting and clear and even funny. He's cool
He seems like he has more knowledge than someone his age should have, I'm always impressed with how he explains things.
hypersapien age doesn't matter, after 15, someone could get HUUUGE amounts of knowledge.
Procrastinator cabbagehair no doubt. That doesn't make it any less impressive to be ahead of the curve, though.
Danni jensen haha
I do like his sense of humor. Easy person to listen to. Great video!
"we are gonna need more paper..and a significant larger universe to put that paper in"
Dammit. This episode ends when it starts getting interesting.
I know!! I hope they do a follow up
This guy is the best person on Computerphile. He should have a channel of his own.
+Lordious No way
+glitchsmasher Rob Miles for PM.
Tom Scott is better. But I like this guy too.
+glitchsmasher This guy and Professor Brailsford.
+glitchsmasher totally agree
I just noticed that at the beginning of the video ti says and at the end it says that is awesome.
+Ben Karcher I believe it used to just use at both ends, until someone they interviewed a while back pointed it out in a video.
+cur33 recognized
nsa monitoring you.
YOU
@@rmm2000 you
Haircut lookin sharp
Keeping important things in mind.
I'm so happy he called it an octothorpe
2:00 The chessboard is set up wrong
+Amir Kerberos Damn those public domain pictures! >Sean (spent so long making sure my CGI board was right I missed this, sorry!)
***** Oh my god, you replied! Hehe, what a lovely surprise. As someone who really likes chess this hurt me plenty
+Computerphile I forgive you :D Loved the video
+Amir Kerberos It's not the first time, and will certainly not be the last time it happens...unfortunately. Ugh! :D
+ChessNetwork you watch computerphile too? that's so cool!
9:14 "what can I do? All I do is win"
That will be on my grave stone
"This margin is too narrow to contain" I see what you did there!
Fermat! :D
He can't help himself :D
Rob Miles is my favorite person on Computerphile (and maybe on youtube as a whole)
me too!
Be great to see more videos with Rob in
Tom Scott
+Hans Schülein or Professor Brailsford
+demonstructie Hmmmm I think im quite the opposite, when watching Computerphile videos I often find myself thinking "I'd love to punch Rob Miles in the mush"... I could never punch Dr Steve Bagley in the mush! Or anywhere else for that matter :P
there are only 3 starting moves in noughts and crosses (corner, side, centre)
Clever
+Mormeemo_ Good point, You could reduce the tree by not counting mirrored states . Similarly there are only 3 types of pieces in a Rubik's cube (corner, side,and center).
It's also much more impotant who starts in Tic tac toe.
+ויאמר סבבה! naw its always a tie no matter who starts
+Jane Black This would be the basis for a numberphile video ;)
Love how clear is this guy's explanation..
17:20 "This margin is too narrow to contain" haha
Fermat's Last Theorem
@@adi-sngh I paused the video when he said that and immediately scrolled down into the comments to see who had mentioned it! ^_^
Always love a Pierre de Fermat reference.
Please do a follow up on this about the Monte Carlo algorithm that became popular for GO AI (and is a lot like the minimax algorithm) before you go into how alphago uses it together with other algorithms.
I very much enjoy the videos with Rob Miles. He's great at explaining.
17:15 you gotta plug a Fermat reference in there!
+Sam J I noticed that too! Funniest thing I've heard today, haha
Love Rob Mile's videos!
Nice to see that the videos about complex stuff are given enough time lately. Thanks.
Shougi (Japanese chess ) was also a hard one for them to computer apparently, but was imbetween chess and go XD Can still put values on the pieces, but many more possible branches because one of your options is to take a captured piece and return it to the board as your own. Also almost all of the pieces can promote, but you have the option of whether you want to promote or not in most cases. So many options added XD
The other issue too I guess is that in chess the computer usually has a database -- the "Opening Book" -- That guides it through the first ten or so moves without having to construct game trees from the get-go. And I'm no expert, but I would guess that it also has a database to search for patterns/combinations in middle and endgame positions, since this is what hardcore human chessmasters do. But I can see how that would be impossible with Go -- It's simplicity paradoxically makes it so much harder to program.
I am so glad I found this channel. currently coding a connect four AI in java and I'm trying to figure out how to apply minimax to it. It's very ironic I found this video the same day I started working on it.
"This margin is too narrow to contain". Legendary quote!! Respect!!
Best part of the video. Such elegance.
Always a delight to watch these discussions!
Ahh I remember doing min max algorithm + alpha/beta pruning in my AI 101 class. Good stuff, brings back memories!
"I just want people to know what you're talking about" ... "So you just draw your octothorpe" lol
I love the way this guy talks I don't know why. I feel smart whenever he says something without explaining it and I understand him.
I like this Rob Miles guy; he's not only a computer scientist, but also a philosopher.
17:20 "this margin is too narrow to contain" - love it
Love these videos!
+MagmaMusen thanks! >Sean
MagmaMusen hey magma! Didn't expect to see you here! Keep up the great work buddy!
hi
addictive channel!
"The problem of recursion is the problem of recursion" ;)
Reference this statement for the answer to the "problem of recursion".
I really like Rob Miles! Keep making videos with him!
Very clear, easy to follow, with great examples, as always.
These are the best damn videos about AI on TH-cam, and having subscribed to this channel back in 2012, I expected no less from it.
This was so helpful! Thank you for posting this.
Absolutely love this guy! Thanks, brilliantly explained (I'm a programmer so particularly appreciated the overview / concept) :)
This video is brilliant. Thanks for the upload~
Noughts and crosses is actually a tad bit simpler than it's made out to be here. Due to symmetry, you can collapse the first move into three branches, and the second moves into five branches (or two, for the first move of taking the middle). That still leaves us in the same ballpark of possible moves (~75 000 instead of ~363 000), though.
I'd like a vid about Microsofts Twitter AI. :-3
I love the people like you xD
4:36 That's an *awesome* window manager you've got there. ;)
Also, cool FSF sticker.
Great explanations. Really like this series on AI
Noughts and crosses! Liking the terminology and strategy for optimal initial moves! Minimax. Thanks for sharing
As someone who's done quite a bit of game theory, I'm happy that Numberphile has finally brought up subgame perfect Nash equilibria/rollback analysis.
Clear and illuminating, great video!
17:19
"This margin is too narrow to contain..."
I love this guy
#octothorpe
+TheJoshinils #hashtag #pound #lb
Three player noughts and crosses:
4x4 board, try to get rows of three, player three draws double crosses
"this margin is too narrow to contain" haha I love this guy
There are two classes of recursion: 1. Where each step is the same function at its own position or level, e.g. factorial, possibly multidimensional and indices may reverse their sense of direction, e.g. the partition array, and, 2. Where each step expands by inserted related function between sub-ranges, e.g. folding-and-90°-unfolding a strip of paper...
loved the video. will there be a part 2 with more details about the new A.I.? like what is the alternative process that it uses
This margin is to narrow to contain...
I like this guy :D
very interesting. I like that someone is explaining AI in a manor where its specific enough to be useful but not so confusing one gets completely lost.
Well explained Rob. As a newbie to AI I found it very interesting. May more of the same
Someone has already done the diagram for you ;)
on xkcd 832
yes I too love playing noughts and crosses on my octothorp xD
great video
with tic-tac-toe, the symmetry of the board helps, essentially making it only 3 possible choices turn 1
"I just want to make sure people understand what we're talking about."
*2.5 seconds later*
"You draw your octothorpe..."
Its difficult to implement brute force search from exchanges of moves between players alone to win a go game because it cannot find territorial pattern on the board. Instead, we can use search algorithm to find a "potential" territory that can be developed by both players and provide strategy to build your own while destroying the other at the same time. Now based on this principles, the search algorithm will nominate moves that best fits the strategy.
Great video. I recommend Head & Shoulders in the future
Fantastic video! MinMax was a very fun algorithm to implement :)
So are you going to do a video on how did google do it?
"This is why having a computer that could play chess was such a mile stone..."
And now computers everyone own can probably outplay you in chess.
Rob lookin sharp af
You ended just where I was hoping you would start! Genetic programming of neural networks next, please!
interesting and entertaining, but not much is talked about the subject itself
It's actually easy to do the full min-max tic-tac-toe tree if you account for symmetry, 'forced' moves, and 'transpositions'(the same moves are done in a different sequence).
There are only 3 possible first moves: the center, a middle edge, or a corner.
1. x: center
2. o: middle edge
3: x can 'force a win' by going in a corner next to the 'o'.
4: o: opposite corner of last play.
5: x: in square touching both x's
6: o: blocks one run, but the other is open, so x wins.
2. o: corner
3. x: opposite corner
4. o: any middle edge lets x force the win.
4. o: any corner is a draw.
1. x: corner
2. o: middle edge
3. x: center, x forces a win with same strategy as above.
2. o: corner
3. x: any corner is winning for x.
2. o: center
3. your best shot is playing the opposite corner, then you win if o plays a corner, draw otherwise.
1. x: middle edge (most, if not all ways for x to force a win will just be a transposition of the game plays from the first two strategies), but mostly this is a lot of draws.
While this summarizes a lot, it gives you the basic idea. With symmetries, links to transpositions, and truncating forced moves, you could fit the tic tac toe min-max tree on a single page of legibly hand written boards,
A real mathematician would never cut his hair that short.
+ElagabalusRex What about a computer scientist
A real mathematician would happily cut his computer scientist that short.
We need an emergency Computerphile video from Rob on Microsoft's Tay
You know you're talking to a mathematician when he just casually drops the word "octothorpe" while talking about noughts and crosses XD
Love these vids! btw there are not 9 options to start noughts and crosses with, just 3 when you take into account symmetries.
Excellent reference!!!! "This margin is too narrow to contain..."
Knots & Crosses is played on a symmetric board. Most options are equivalent and this simplifies the evaluation.
For instance, the number of possible starting conditions is not 9 but rather 3, since the board can be mirrored and rotated in any direction to match other options. The second choice is often 5 and otherwise 3 but not 8.
Sorry for necroreplying, but *naughts :p
The interesting thing about minimax is that even the strongest computer might in a practical sense play worse than a human weak player. In the case theoretically of someone with a losing position - humans will play for traps. They will play moves knowing that they are not the best but might swindle the opponent via a neat tactical idea. A computer on the other hand will not try for such swindles or traps and instead always try and play objectively the best move. The 'minimax' is always rational like Mr Spock - assuming the best possible moves for both sides. But this doesn't help if one is already in a losing position. Humans basically know when to take a gamble. Nice video though - clarified quite a bit about minimax and how values are taken back up the tree if possible and the role of heuristics. Many thanks, K
+kingscrusher Minimax isn't rational, because if you know you will win not win by playing it safe, not taking a risk is irrational.
kingscrusher
You are aware that programs are more than capable of that already? Which is why they utterly dominate humans at chess and have been doing so for over a decade?
And if you watch things like the match of AlphaGo against Lee Sedol, the program was better at looking at the wider context, while the human commentators and Lee Sedol were more limited in their perception.
+Tsuyara That (AlphaGo) is "real AI" as opposed to fake AI. Demis Hassabis and his company were modelling real brain neurones - not mucking around with brute force algorithms. That's why his company was bought by Google for a huge amount of money. The implications as far as I can see go beyond gaming. Fake AI has been the obsession of computer scientists for many many years. Cute little recursive algorithms etc. That is "AI" in the really "Artificial" sense - trying to create a mathematical model for creating move choices based on those models.
kingscrusher
But you are aware that they only had to resort to that because the computation time for a 'perfect' solution was far too high and it had nothing to do with the program not seeing the wider context (at which AI is generally better, as they are not limited by human nature).
+kingscrusher BTW returning to the core of the video - "Minimax" - in chess terms, on a human to human level, quite often I believe that the stronger the opponent one is playing, the more one should really believe the opponent will "Min-max" you - i.e. minimise your maximum. But say in blitz chess or bullet chess and especially against lower rated players, you can often just be really ambitious and ignore a lot of the time the "Mini-max" aspect. This might be at the heart of the concept of playing "solidly" - i.e. in such a way that it doesn't matter if the opponent is much stronger, you are trying to play the best possible moves and really expect a "Min-maxisation" of your chances from the opponent.
Tic-Tac-Toe (Naughts & Crosses) is easier when you factor in symmetry. There are really only three moves for the first player: Center, Corner, Middle-Edge.
The second player only has TWO options for a first player Center move, four options for a first player Corner move, and five options for a first player Mid-Edge move.
Still a solved game, just slightly faster.
+andrewxc1335 "...four options for a first player Corner move..." Are you quite sure about that?
Are there not four corners on a Tic-Tac-Toe board...? Did I miscount out of the nine squares...?
You're right in that if the first player makes a center move, the second player has to choose either one of the 4 sides or one of the 4 corners. However, if the first player chooses to occupy a corner, the second player can choose from "Center, Opposite Corner, Adjacent Corner, Adjacent Side, or Opposite side" I believe that makes 5 possible moves, factoring in diagonal symmetry.
ideallyyours
Yep. 5 choices for a corner-move.
I recant.
17:25 "this margin is too narrow to contain..." good reference Rob :)
To this day, it still amazes me that it was possible to program a chess game for the Atari 2600! A machine that has only 128 BYTES of RAM, and only 4 Kilobytes of program space in the cartridge(which was later expanded to 8K). It's because of this that I am surprised that it took this long to write a program to play Go. Guess that shows how much more complicated it is than chess!
+SirReptitious I think the main reason for that is that everyone and their mother was doing chess AI in the 80s. There was a total craze about them and lots of prizes to be won, and that just didn't happen with Go. I do think that Go is quite a bit harder to do computationally but if people had put in the same amount of effort that they put into chess we would have probably gotten decent Go AIs a lot earlier.
It's not as complicated if you play on a 9x9 Go board. Chess can be expanded in the same way, for example Tamarlane's chess.
+SirReptitious He gave the answer in the video: You can effectively judge a boardstate of chess. Number of pieces, pieces are more valueable than others, states where you can attack 2 pieces at once. This enables you to make educated guesses on the best move by just looking ahead only a few turns and thus you don't need much memory to keep states in. With go this situation is completely different. Not only have you much more possible moves, but you also cannot judge a boardstate efficiently. There are other factors too: The board of go is bigger - more time to evaluate the state, more memory needed.
To cut this short: The classic min-max strategy is not working for GO and complex learning neural networks are a kinda new thing.
Florian H.
Yes, I watched the entire video and I understood what they said. I don't know if you have ever programed before, but to program a chess game in only 4KB of space(I don't think it used an 8KB cartridge, but not 100% sure), that ran on a *1.19 MEGAHERTZ* CPU that had only 128 BYTES of ram, is an incredible feat of programming..
It was only a matter of time before the hardware and software was enough to make Go. It's still a noteworthy milestone, just as Deep Blue and Watson are for IBM. But I am still more impressed with chess on the 2600. ;-D
A Sinclair zx81 (Timex 1000) with a total of 1K (1024 bytes) RAM (the Timex version may have had 2k, but an unexpanded Sinclair ZX81 original only had 1K of static ram) had a chess program written for it; that 1K RAM held:
Screen output (memory mapped),
System variables (probably very few),
The actual chess program,
Any data the chess program required, including processor stack.
There was no 4k for just program - that should amaze you.
- "Come on, lets draw it!"
(Two minutes later)
- "You know what, life is too short."
Will there be an episode on Microsofts 24 hours to NeoNazi twitter-bot and what happened to it and why?
CatnamedMittens "The notorious hacker known as "Four Chan" must have gotten into their code."
TheMan83554 Doesn't it learn from talking with humans? I don't think you really need hacking if that's the case.
CatnamedMittens During the fappening a news anchor misspoke and attributed the leak to "A hacker known as 4chan" The internet ran with it and 4chan almost certainly had a hand in screwing with the AI. Therefore, the hacker known as 4chan messed with their AI.
TheMan83554 Brilliant.
***** Well, aren't you a barrel of fun...
The tic tac toe tree can be simplified. There are not 9 opening moves but only 3. The edge, the corner and the middle.
No it also come to which side left or right or up or down and which corner top left, top right, bottom left or bottom right.
@@bestproductable you didn't get it dude lol
no that wouldn't work, because the following moves do depend on where the first move was, so the tree would actually get more complicated with more moves, not simpler.
@@user-zb8tq5pr4x no, you could just rotate the board to make all the corner moves and all the outer middle moves look the same... Kind of
Great video! Do you guys have more videos about alpha go?
Redeemed from previous video. Good going.
An avatar 1-dan could beat me spectacularly in game of go at 9-stone handicap. I really admire complexity of human mind and appreciate how computer can solve complex problem that humanity had been working on it for thousands of years
awesome video
Man, I learned this stuff so bad at college and now I see why being smart enough to understand them is important.
6:42 As the maximizing player, the minimum best score you can get is a 5. You can guarantee a 5, no matter what the minimizing player does. If the minimizing player makes a mistake you can do even better (in your tree, and often do better but at worse do the same in any tree). That’s the power of minimax. The guarantee is the power.
In a game like chess where it cannot are to the end of the game the horizon problem steps in. But that’s another story.
And if we win, the board in this state we can call it a "One", 'cause we've "Won", right ?
Brilliant
This video inspired me to make my very own AI ! Thanks ! Great Video !
Black Rainbow Don't do this ! Do this! Why does everyone put spaces infront of their exclamation points?
I don't really understand that either . Why ever would anybody do that ? It's ridiculous !
Really enjoying Rob Miles' insights into AI.
Just to be pedantic though, (0:35) "X's and O's" is no less descriptive than "naughts and crosses" as a name for that game, it just depends on your culture's vernacular; they are both using words to explicitly describe the symbols used.
I was comparing to 'tic-tac-toe'
Great video
Robert Miles... GENIUS!!! Squeezing a 'Fermat' in here too!... wonderful. 'Go'-get-'em Robert.
5:22: "The problem with recursion is [...] recursion."
Nice.
Actually for the first move there are only 3 possible branches, Center, Corner, and Side Center, because the only difference is the orientation of the board which is irrelevant. After that you actually have slightly more options as the second move is relative to the first move. Moving in the center first (which is actually suboptimal), would yield only two branches, corner, and side center, and so on.
in the first turn in knots and crosses you actually have 3 choices because of symmetry: you can choose a corner or a side or the centre.
I had never heard of Go before. will have to google it.
Rob neglected to dig into another incredibly important factor in chess stemming from the branching factor besides simple mathematical tractability: the assumption of perfect play. Most humans can perfectly play naughts and crosses effortlessly, but no humans perfectly play chess or go
one thing that always aggravates me with Chess is that for over a decade. I could not find two opponents who could agree on the rule-set. They would all have confused their own house rules with whatever rule-set they proclaim was the standard one. So In the end I gave up on the game completely. Found Go. Found that there really are no house rules. And the only rule-change over the millenia it's been played... was essentially a bug fix to avoid endless loops in the gameplay.
So it does surprise me a bit that programmers focused on Chess when in my experience, there have been no other game where I have seen so much rampant moving of goalposts that doing anything worthwhile should be essentially impossible.
"This margin is too narrow to contain..." from Fermat's Last Theroem
+Artur Czekalski Apparently, from many of his theories; some Numberphile video mentioned that he did this all the time!
I love his voice