So they say, if you look at the history of AI, there was great success with games like an early game that was played seriously by, Humans, had human championships, was Othello game Reversi. It was a game in which there was discs on I think an eight by eight board, so you could have 64 squares. It was a placement game in which pieces or rows got captured and was highly combinatorial. And I don't know exactly what time the Reversi, I think some time in the early 80s, the Reversi or Othello games got better than human play. And I think at a little later time, they actually got the play perfectly on those sized boards. Chess, we start to have master play in the mid to late 80s, we start having grandmaster play in the 90s, we have World Championship play by the end of the 90s and by now play is beyond human ability. We have perfect American checkers, we had reasonable expert play, one of the great early AI programs by Art Samuel of IBM where he used this to test machines on the floor that IBM was producing. It was just a test program for him, but he still developed in the classic style of AI with the learning components, so he was very famous for, quote, learning. Something that could play high quality American checkers and later groups were able to develop checkers both mathematically and combinatorially and computationally to the point where they could play perfectly as well. So the one serious game out in the world, and by the way, there are very high quality games with a probabilistic component. So there are Backgammon games that are probably, I think, considered better than ordinary human play at this point, and very high quality poker playing bots as well. University of Alberta is very well known for many of these developments. But Go was resistant and the classic AI methodology was being used in Go. And those programs, including a program developed at the University of California Santa Cruz by a colleague, Charlie McDowell would play in local computer tournaments. And at the time, that program was called SLUGGO, around 2005 it occasionally won one of these tournaments. So it was among the classical methodology, it was among the best playing programs of its era. But those were barely better than novice serious players than players who were what you may call club players, more than beginners. They knew some of the game. But when playing a serious club player or a low-ranked professional, they had absolutely no chance. That was the level of play and the way they were developing the you might call the improvement curve, was very, very slow. I mean, computers were getting faster, they could do more evaluation, they could do multi-threaded evaluation, take advantage of parallels. The SLUGGO computer I think was a rack of 64 processors, if I'm recalling it right. So they had much bigger computational advantage but unlike chess, unlike these Othello, the standard methods would some improve the evaluation with a lot of improved computation, did not get the same improvement in the quality of play. So something else was going on. A game was just too difficult and the criteria that professionals use were not that combinatorial, there was deep judgment based on patterns and it was very hard to replicate. So around 2006, in Europe, one team decided to try this combinatorial approach and voila, it made an order of magnitude improvement over all the classical programs. And immediately it was identifiably by far the best computer Go playing program. And in short order, it could play roughly at average, Club playing strength in a Go club. So the play by 2010 was of enough quality that with a reasonable handicapped, Go players have these rankings, and low level professionals will give a medium club player so many stones. So they'll allow you to make four or five moves on the board of a certain kind. So you start with that much additional space in your hand and that's considered a handicap that equalizes between players. And until then there was no sort of handicap, a reasonable handicap, that a Go master needed to give a computer program and still win. A Go master would just win with any kind of reasonable handicap which might be 10 or 15 stones. Now all of a sudden, this Monte Carlo based thing allowed for interesting matches. So Hex, very similar character to Go, played on a Go board is played with, essentially, black and white stones. It's essentially static in that, it's not the combinatorial characteristic of Othello, or chess, or checkers, with captures and the pieces make changes in positions. And then this method we've just explained, evaluating at random to the end, gives some deep insight into which position is better, as it did in the Go board. So in this homework which in your class is the last homework, the last major programming assignment. One, I expect you to be able to write your C++ code so that your move selection should be roughly on the order of one or two minutes. I don't want people playing the game to have to sit there longer than that. So you have to try and be highly efficient. And you should be able to get 1,000 or more simulations per position, for each legal move. If it's too few, the character, the estimates, won't be that good. So you'll discover, if you're making too few evaluations, somebody with a good sense of how to play Hex will beat these programs. But if you're on a small enough board and you have a high enough number of evaluations, it'll start being very hard for a human player to be beating the program. Okay, so one of the things you may want to think about especially, and while I won't be showing you how to do this in the classes, a little bit beyond the background that most students might have in the course. But I know some of you are quite sophisticated and some of you want to try new ideas, is there are ways now in C++ to use the new standard and do parallel computing. So what if you had two computers available for you who are independently using the Monte Carlo method for estimating probability of winning? Would those two computers benefit you by combining their results? That's your little quiz question. The answer is yes, provided there's no secret dependence. By that I mean, let's say you were running exactly the same program and you started in the same place of a random number generator on the sequence. Then both programs would produce an identical result and combining those results would not add to the confidence interval. You would just get two replications of exactly the same. It's like running two weather models but you actually ran exactly the same thing. So one suggesting rain is 60% and the other one will absolutely suggest rain is 60%. They're the same exact calculation. So in order for the two to be combinable, the two pseudorandom number generating sequences have to be distinct. And then if they're distinct then you have more trials that can be combined and then the estimate indeed improved. So if you do your independent threaded model or you have two computers available, you have two processors, or you have now what's very common in your personal computer a quad processor, and you can get it threaded properly, the trials can be quite independent. The critical thing is to make sure that you're using different random number sequences or generators even. It would probably even better to use separate random number generators because you're going to be doing lots of trials and then you're going to get your estimate will be far better or it can be done in a shorter amount of time. Monte Carlo does indeed lend itself, very much so to parallel processing. So that's again why this has shown up. So the Go people started having a lot of big racks of computers. So the way they could get large amounts of additional computation was that everything could be done independently and would still contribute to making a decent evaluation. That would not be that helpful in a contingent sequential evaluation, or examination, that might be required by minimax. Now, minimax can be parallelized, so there is benefit to also having minimax parallelizable but there are still more distinct sequence points and you can't be utterly independent. So again you can use C++ 11 and a thread package and you can attempt to work with a multi-core computer and see if you can improve on a single-threaded version of this program. But that will not be within the parameters of what we're teaching or expecting. Okay, another little quiz question here. I think you remember when we were first describing Hex. We know from the original inventor of Hex, Nash, that he also proved that player number one always won Hex if they played perfectly. Even though we didn't know how they could win, they just knew from an argument that player number one had an advantage that meant that if he played perfectly with. So people introduced what was called the pie rule. Recall the pie rule, It means the second player, after seeing the first player's move, can say, wow, I love that move, I'll be the first player. So it then becomes the obligation of the first player to make a junky move. Now if the first player can make such a bad move that the second player says, I'll take that junky move. And then, the first player gets to make a very good move. Now the first player gets the advantage again. But the danger is, the first player doesn't make a very junky move. So he has to make a move that is part of the game for too sophisticated players is to make a move that gives each one roughly the same ability to win. But my theoretical question is with the pie rule, is it always a win for one player? Does Nash's proof still hold up? And if it is a win, is it now the second player that's guaranteed to win? So think about that a second. It's not a computational question, a little bit about the logic of the game. Well the game is still guaranteed to be a win. I mean that's just, there is no way to avoid winning or losing Hex. There's no drawing positions, so that doesn't change. The Hex board cannot have a drawing position. If people alternate, one side has to be able to win, the other side has to lose. So the game is still a guaranteed win. But it is now the second player who always wins. Why does the second player always win? If the first player has made a move that objectively by playing perfectly, the first player is now going to win. Well, the smart second player says, aha, the first player has made a move that leads to a win, I'll become the first player So the first player has to make a move that doesn't lead to a win. And if such a move exists, unclear, but let's say such a move exists, the second player will recognize, the first player has now made a move that leads to a loss. I'll leave them the first player. So if both players could play perfectly, and the pie rule is in effect, the second player has the clear advantage, okay.
