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.
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]
+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).
+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
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.
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.
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.
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 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.
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.
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.
+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.
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.
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.
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...
Getting a computer to accurately evaluate a chess position isn't exactly trivial either. Matter of fact, Neural Networks are the only machine entities that aren't fooled several times in 100 games or so. The NN correlates as many discrete values it can with winning, losing, and drawn positions, which turns out to be far more accurate than any human or human derived heuristic. The problem with Go is the branching factor is so much larger than chess.
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,
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
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.
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.
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.
Tic-Tac-Toe is a 3 x 3 x 3 special version of Height, Width and row Lenght. I did AI in the early 80's, where recursion and brute force were prohibitive. I found "TicTacToe" is the very same game than "Five-in-a-row" for true AI. You START knowing you cannot go in deep, then you focus on the field.
I like the comment "if a computer was able to play chess, it would really have to be thinking right?" what's funny is that when we play chess, we use similar ideas as the computers: which moves can I make, which moves makes me capture the most pieces, which move gets me closest to the king or some other valuable peice. these are all easily calculated numbers and fitness scores. it's as if we don't have any better ways of winning chess as chess computers do.
Years a go I programmed tic-tac-toe on a 32k 3.5Mhz computer (in basic). The branching principle Rob explains is nearly impossible with such restrictions. I made the A.I. hard but not unbeatable by setting up some simple rules and give sets 'weight' and added RNG. That way the better moves had a higher chance to be played, but less optimal moves were played as well. SInce the movie War Games (1983) everyone knows the game is no fun against a perfect A.I.
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
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.
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.
"Octothorp"--I learned, in a rather abstruse book on typography, that it was originally a sign used in the Doomsday Book for eight adjoining farms. Who knew that the term was still in living use. It's much fancier than "pound sign," I must say. I don't know why the game is called "tic-tac-toe" over here, but "noughts and crosses" is much more evocative. I'm glad to see that not all British linguistic variations have been plowed--to say nothing of ploughed--under by American popular culture.
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.
I made a tic tac toe bot that is pretty simple where first it tests to see if you have 2 in a row and if you do it blocks it and if you don't then it just chooses a random square and it is actually better then most people who have not spent time learning tic tac toe strategies.
For those who see this in the future. A team of mostly non-Go players and a few novices BEAT THE GO AI by writing many mini AI to use every technique they could think of to try to probe the blackbox that is the go AI. They found that a "sandwich technique" was able to confuse the AI and one of the researchers was able to beat the AI 14 to 1!
Just FYI, this does not have any implications in the broader field. It is extremely well known that these systems are susceptible to that exact kind of adversarial network attack. All that implies is that This System Is Not Optimal at it's task, which is exactly what we expect for a configuration space as large as Chess or Go. Our models are not big enough to minimax the whole thing, therefore they are not perfect players, therefore they still *can* be beaten, therefore a system whose job is to try every combination of moves until it finds one that works *will* find *some* ways to beat it
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.
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
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*
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!
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
*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?
Dammit. This episode ends when it starts getting interesting.
I know!! I hope they do a follow up
"we are gonna need more paper..and a significant larger universe to put that paper in"
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
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 ;)
I'm so happy he called it an octothorpe
Love how clear is this guy's explanation..
Haircut lookin sharp
Keeping important things in mind.
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
9:14 "what can I do? All I do is win"
That will be on my grave stone
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!
17:20 "This margin is too narrow to contain" haha
Fermat's Last Theorem
@@1_adityasingh 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.
"This margin is too narrow to contain" I see what you did there!
Fermat! :D
He can't help himself :D
I very much enjoy the videos with Rob Miles. He's great at explaining.
Love Rob Mile's videos!
17:15 you gotta plug a Fermat reference in there!
+Sam J I noticed that too! Funniest thing I've heard today, haha
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 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.
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
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 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.
Ahh I remember doing min max algorithm + alpha/beta pruning in my AI 101 class. Good stuff, brings back memories!
I like this Rob Miles guy; he's not only a computer scientist, but also a philosopher.
"This margin is too narrow to contain". Legendary quote!! Respect!!
Best part of the video. Such elegance.
"I just want people to know what you're talking about" ... "So you just draw your octothorpe" lol
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.
"The problem of recursion is the problem of recursion" ;)
Reference this statement for the answer to the "problem of recursion".
I'd like a vid about Microsofts Twitter AI. :-3
I love the people like you xD
These are the best damn videos about AI on UA-cam, and having subscribed to this channel back in 2012, I expected no less from it.
Nice to see that the videos about complex stuff are given enough time lately. Thanks.
#octothorpe
+TheJoshinils #hashtag #pound #lb
Three player noughts and crosses:
4x4 board, try to get rows of three, player three draws double crosses
interesting and entertaining, but not much is talked about the subject itself
I really like Rob Miles! Keep making videos with him!
17:20 "this margin is too narrow to contain" - love it
Someone has already done the diagram for you ;)
on xkcd 832
4:36 That's an *awesome* window manager you've got there. ;)
Also, cool FSF sticker.
5:22: "The problem with recursion is [...] recursion."
Nice.
Always a delight to watch these discussions!
This margin is to narrow to contain...
I like this guy :D
17:19
"This margin is too narrow to contain..."
I love this guy
Very clear, easy to follow, with great examples, as always.
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.
with tic-tac-toe, the symmetry of the board helps, essentially making it only 3 possible choices turn 1
"this margin is too narrow to contain" haha I love this guy
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.
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
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.
Haha the margin is too narrow to contain
+minshwan tang Did not really expect 7 likes that got that quote so early in. Very nice surprise.
minshwan tang yes
Fermat's Last Theorem
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.
"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.
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.
17:25 "this margin is too narrow to contain..." good reference Rob :)
"I just want to make sure people understand what we're talking about."
*2.5 seconds later*
"You draw your octothorpe..."
Redeemed from previous video. Good going.
You know you're talking to a mathematician when he just casually drops the word "octothorpe" while talking about noughts and crosses XD
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...
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.
Getting a computer to accurately evaluate a chess position isn't exactly trivial either. Matter of fact, Neural Networks are the only machine entities that aren't fooled several times in 100 games or so. The NN correlates as many discrete values it can with winning, losing, and drawn positions, which turns out to be far more accurate than any human or human derived heuristic.
The problem with Go is the branching factor is so much larger than chess.
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,
And if we win, the board in this state we can call it a "One", 'cause we've "Won", right ?
Brilliant
"I just want people to understand what you're talking about"
"...so yo draw an octothorpe"
That was so unintentionally funny
- "Come on, lets draw it!"
(Two minutes later)
- "You know what, life is too short."
"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!
So are you going to do a video on how did google do it?
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
Excellent reference!!!! "This margin is too narrow to contain..."
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.
Noughts and crosses! Liking the terminology and strategy for optimal initial moves! Minimax. Thanks for sharing
We need an emergency Computerphile video from Rob on Microsoft's Tay
This video is brilliant. Thanks for the upload~
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.
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.
7:20 "this is a game you can play with your friends" : D
Tic-Tac-Toe
is a 3 x 3 x 3 special version of Height, Width and row Lenght.
I did AI in the early 80's, where recursion and brute force were prohibitive.
I found "TicTacToe" is the very same game than "Five-in-a-row" for true AI.
You START knowing you cannot go in deep, then you focus on the field.
Sorry, it wasn't "Real" AI, I did learning nets 20 years later, with more power.
I like the comment "if a computer was able to play chess, it would really have to be thinking right?" what's funny is that when we play chess, we use similar ideas as the computers: which moves can I make, which moves makes me capture the most pieces, which move gets me closest to the king or some other valuable peice. these are all easily calculated numbers and fitness scores. it's as if we don't have any better ways of winning chess as chess computers do.
Rob lookin sharp af
Years a go I programmed tic-tac-toe on a 32k 3.5Mhz computer (in basic). The branching principle Rob explains is nearly impossible with such restrictions. I made the A.I. hard but not unbeatable by setting up some simple rules and give sets 'weight' and added RNG. That way the better moves had a higher chance to be played, but less optimal moves were played as well. SInce the movie War Games (1983) everyone knows the game is no fun against a perfect A.I.
Game
Robert Miles... GENIUS!!! Squeezing a 'Fermat' in here too!... wonderful. 'Go'-get-'em Robert.
English logician: "I like noughts and crosses, it's descriptive". The Dutch: "butter , cheese and eggs? Yes please!"
You ended just where I was hoping you would start! Genetic programming of neural networks next, please!
What the * +Computerphile ? I thought you would explain how they computers finally beat GO!
Man, I learned this stuff so bad at college and now I see why being smart enough to understand them is important.
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
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'
For tic tac toe's nodes and branches wouldnt it be 9 options, 4 options, 7, 6, 5 , 4, 3, 2?
Since at the second move you can flip the board.
This was so helpful! Thank you for posting this.
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.
"Octothorp"--I learned, in a rather abstruse book on typography, that it was originally a sign used in the Doomsday Book for eight adjoining farms. Who knew that the term was still in living use. It's much fancier than "pound sign," I must say. I don't know why the game is called "tic-tac-toe" over here, but "noughts and crosses" is much more evocative. I'm glad to see that not all British linguistic variations have been plowed--to say nothing of ploughed--under by American popular culture.
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.
Clear and illuminating, great video!
5:21 "The problem with recursion is the problem with recursion" Ø
I made a tic tac toe bot that is pretty simple where first it tests to see if you have 2 in a row and if you do it blocks it and if you don't then it just chooses a random square and it is actually better then most people who have not spent time learning tic tac toe strategies.
For those who see this in the future. A team of mostly non-Go players and a few novices BEAT THE GO AI by writing many mini AI to use every technique they could think of to try to probe the blackbox that is the go AI. They found that a "sandwich technique" was able to confuse the AI and one of the researchers was able to beat the AI 14 to 1!
Just FYI, this does not have any implications in the broader field. It is extremely well known that these systems are susceptible to that exact kind of adversarial network attack. All that implies is that This System Is Not Optimal at it's task, which is exactly what we expect for a configuration space as large as Chess or Go. Our models are not big enough to minimax the whole thing, therefore they are not perfect players, therefore they still *can* be beaten, therefore a system whose job is to try every combination of moves until it finds one that works *will* find *some* ways to beat it
I'm going to call tick tac toe noughts and crosses forever now
That Fermat reference though. :)
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