30 Weird Chess Algorithms: Elo World

chess chess is perhaps the best semi 3d on Rails platformer game since Crash Bandicoot 2 this is me Tom 7 I like to play chess but mostly bad chess it's just less stressful chess 'full but these days it's hard to find a good low stress game of bad chess for reasons like this my friends are either good at chess or refuse to believe that I'm bad at chess also I don't have any friends most children are bad at chess but seemed to hyperkinetic and afraid of me playing chess online feels like talking on the telephone to strangers except that in addition to not being able to see them you have to compete an intellectual combat with them and you can't even tell if they're laughing at you also I don't know what the internet even is so you can play against computers computers are of course disgustingly good at chess it's really annoying but people seem to be obsessed with making chess computers that are good and if you've been paying attention you know that that's not really my style to do good things or useful things or things that make sense so this video is a collection and comparison of many different lousy ways for computers to play chess checkmate you are bad now the main motivation for this is just that it's my idea of fun but I did come across it because of the following problem when humans want a handicap one another in chess one way to do it is by wearing a blindfold then you have to remember where the pieces are on the board but remembering where the pieces are is like super trivial for computers in fact it'd be more impressive if they can see a board and understand where the pieces are so is there any analog of blindfold chess for computers so the idea came to is this instead of letting the computer see the board the computer gets to see where the pieces are but not what the pieces are so it's not blindfold chess but rather color blind and piece blind chess now it's also important to prevent the computer from knowing the sequence of moves that were played because if you get to remember then it's trivial to know where the pieces are now so the computer is not allowed to see the game as it unfolds rather it's just given the set of bits there's 64 of them because there's 64 squares on a chessboard and I think that's part of what it tracted me to this idea it's very native representation for a computer it just gets the 64 bits and has asked to make a move it needs to figure out where the pieces are and even whose turn it is it would be hard for humans to play this game because you would need to administer some kind of memory loss agent to them so they literally couldn't remember what happened or else they could only play one move in a game and that's not very fun either but for a computer we can just enforce that it just doesn't get access to it so clearly it's not too easy to play chess this way I still think it's interesting I think a human could tell for example that this arrangement is three pawns and the king and rook having castled same up here just because that's a common thing to do and it's hard to get in this situation otherwise and I think really skilled players would have a good chance of figuring out this entire board given that this is a fairly straightforward idea in the Queen's Gambit opening which has been played dozens of times in tournaments care to try it yourself go ahead and pause the video and see if you can figure out what position this is I'll give you a few seconds for those of you that found it congratulations you are an excellent student of the ready opening and for those either just want to enjoy the show the position is of course this one which is reached after these 20 moves putting everything in its right place with white to move of course some positions are much harder especially late in the game because there aren't that many pieces and they can have gotten pretty much anywhere and so the computer is likely to get it wrong and very likely to make an illegal move in this position this turns out to be the white King and it's actually in check because this is a black knight and so if I try to move any other piece or a piece that's not even mine then that's an illegal move and the punishment for that typically is that you forfeit the game this is a little bit unfair to the computer I think on the other hand if we allowed the computer to check whether a move was legal if ask hey as this move legal or is this move legal and so on then it could learn a lot about the position just by trying out moves this seems counter to the spirit so the interface we actually have for the computer is we give it this one 64-bit number which represents the board and we ask it to rank all of the moves in order of its preference so it could say well first I'd like to try this and then if that's no good that I'd like to try this and if that's no good I'd like to try this and so on it actually needs to produce a ranking for all possible pairs of squares and the first one that is legal is the one that it will commit to so for example if the 14th move that it asked about was this then that's the move that it would play so I implemented a program that plays blind this way and we're gonna come back to how I did that I like playing against it because it's not very good but the natural question is how not very good is it if I pit it against off-the-shelf computer programs it gets destroyed every single time so what I want to do is build a number of other weak chess engines that are kind of easy to understand so that I can compare it to the performance of those let's start with a really elegant simple algorithm which is to just choose moves randomly in computer science we say that an idea is canonical when anyone that would have studied that same problem would have come up with that same exact idea even aliens if they had chess would have come up with this this way of playing at any given moment there's only some set of moves that are legal here they all are for black and it just randomly chooses one of those moves with the same probability for each one here it shows a pretty terrible response also very bad and as checkmate but aside from being really canonical what's lovely about this algorithm is that if it gets lucky it could play any sequence of moves it could choose the best possible response to what I'm doing better than even the best humans or computer programs have ability to do today a sort of Boltzmann brilliancy so in my mind this is one of the best benchmark points to compare to so to do that benchmarking I'm going to run a tournament between all the different players that I built here we just have one player so far so it's not much you can get out of this except that we can say that random move when it plays against itself it's usually a draw that's what the blue color means this diagram will make more sense as I come back to it and add more players now it's not too important that the players be good at chess but it's good if they do something they have some preference so here we'll have a player that likes to put the white pieces on the white squares and black pieces on black squares and that'll be called same color and of course we could do the same idea but the opposite idea we're just to put white pieces on black squares and vice versa that'll be called opposite color so this tends to produce nice aesthetic patterns which I find agreeable now same colors always trying to put a piece a white piece on a white square but it can't ever do that for example for this bishop which must always stay on a black square so if it can't make any move that puts a white piece on a white square it'll just make a random move for example here it'll move the bishop from a black square to a black square and this idea of breaking ties with random moves will be a theme among many of the players of course both of these players are bad at chess they have a preference but it doesn't really have to do with winning it turns out that both of them are trying to put their pieces on the white square so they do end up fighting it out for control of those squares but it's really only by luck that the white player ends up winning I see I really started with some interesting ones on average it seems that all of these players tie when they play against each other same color and opposite color both a little bit worse than random it turns out but note that same color and opposite color sort of do a different thing whether they're playing as white or black so in this table note that the rows are where that player is playing as white and the columns are where that player is playing as black and again this will get more interesting from more interesting players let's keep going so here we have two more players with a preference around where they put their pieces the player called huddle tries to move pieces such that they're close to its king and the player called swarm here playing as black tries to move its pieces such that they're close to the enemy King both of these strategies are somewhat reasonable of course attacking the enemy King is good for winning and of course blockading your own king has some advantages in terms of defense now you might notice that these pawns don't seem that close to the king but distance here is measured including diagonal moves because the king can move diagonally so we have one two three which is the same distance as one two three for example now I'm not gonna make you watch all these games all the way through but it is at least a little interesting what happens in this case white is able to get its own pieces closer to its own King sometimes by capturing the black pieces that are near it and then escorts its pawns to the back rank where they promote and accidentally checkmate black check weight over in the tournament we can finally see some of these players behaving differently swarm is in fact much better than random move huddle much worse and this kind of makes sense if you have a preference to attack the opponent you're gonna accidentally checkmate it sometimes the next strategy is almost canonical it's a way that children discovered to play chess which is to just copy their opponent's moves unfortunately this strategy is not completely described because after a little while you won't be able to copy your opponent's moves here I've captured this black rook with my rook and now black can't do that and I'm totally winning so instead of literally copying my moves this player is defined in a way where it tries to make the board symmetric along the y-axis now as you know this isn't the only kind of symmetry if you've studied mirrors for example you know that mirrors reflect things horizontally this is because they're horizontally polarized unlike Lakes which are vertically polarized these reflect things vertically there's a third kind which is a lens which flips things all the way around this results from circular polarization i implemented chess players for all three types of symmetry here's a nice horizontally symmetric board that it was able to create in the tournament well we still don't have any breakout strategies so let's just keep on going another silly preference we could have is to believe that the board is actually upside down and that the black pieces belong on the bottom and the white pieces belong on the top here it is playing against itself and partially succeeding that one doesn't do much better than random we could also consider strategies that care about chess things here the CCCP strategy has only the following priorities in order checkmate and if it can't do that check my king and if it can't do that capture a piece and if not push a piece deeper into my territory I'm not going to interfere with it too much so that we can kind of see what it likes to do you also notice that I've drawn the pieces some hats because I think it's fun to anthropomorphize them and we you know you spice it up I think there's actually a bug with this because it should be pushing its pieces other pieces not just that Bishop back and forth but you know they've got hats even with some bug this is our best overall strategy so far and we see our first instance of an X in the tournament so each one of these cells represents hundreds of games actually 700 something games the red here means that white lose is playing against itself and the X means that that always happens in every single game it was a loss and that's because this particular strategy is deterministic it always does the same thing in the same situation we'll see some more of that I must admit though I get a big kick out of the players that sort of don't even realize that they're playing chess here each of the pieces is represented by the standard letter that denotes that piece and that's because this player just plays alphabetically it looks at all the legal moves and puts them in standard notation and then plays the one that's alphabetically first it's actually gonna just move this Knight back and forth between these two squares note that capital n comes before lowercase a in ASCII and I'm using ASCII to quote unquote alphabetize these moves let me just capture that so we can get that over with now it's gonna just keep moving this Knight back and forth and now it's just gonna keep moving rook b8 rook a8 rook b8 so suffice to say alphabetical player is not very good there's also a variant of this that moves based on the coordinates rather than the sort of name of the move and that one's just called first move it moves lexicographically and lo and behold in the tournament these players are very bad alphabetical is actually the third to worst player although since there are no exes you can see that it doesn't always lose at least this column on the left gives an mirakl score to each player which is called the Eila rating daily rating is a somewhat standard calculation that you do of the tournament itself from the outcomes of the games and it gives the name to this tournament which is a low world you can read about that rating system itself on Wikipedia I'm not gonna describe it in this video now if you have to play chess to the death you're in trouble because like me you are probably not good at chess but what about the rarer problem of being a chess piece to the death what I mean by that is suppose your little soul has to inhabit one of the 32 chess pieces then some other people play the game and if your piece survives the game then you survive but if you're captured then you die here we're going to be concerned with the story of a specific piece not just any pawn but this pawn I can draw its path so that you can see what it does but it might be clear to just give each piece a name here the pawn called fixed sis makes its way up the board this is where grains are died the pawn promotes to a queen and there's where its story ends so I downloaded about 500 million games from the sightly chess and kept track of the stories of each of the pieces first I wanted to understand which is the piece that's most likely to survive and you can of course read the paper if you want but spoiler alert it's these extremal pawns on both sides that are most likely to survive the whole game but we can also talk about a specific piece of story what's most likely to happen to Geneva here or the White Queen where is it likely to end the game and is it likely to be alive or dead there for each of the pieces on the board and here I'm just showing White's pieces I computed exactly these things so here darker squares are where the piece is more likely to end up you can see that bishops for example can't get to half the squares because they can never leave their color and the number on each square tells us the probability that the piece lives if it ends up on that square at the end of the game so if you look at the F pawn here which starts in this square it makes perfect sense that it's mostly confined to this region because of the way that pawns move it can get back here it must do that by promoting to some other kind of piece that can move backwards and it's most likely to live if it ends up in this top corner for some reason interestingly of all of the possible fates for a piece the rarest one is actually for this f-pawn to die on this square that only happened 1200 times in all 500 million games getting here and surviving as much is more common usually you do that by promoting but note that since this is on the diagonal it's possible although very unlikely for the pawn to get there that way so unlikely that it's never actually happened in a game of chess as far as I can tell this might mean that there's a hidden achievement for doing it anyway from this study I ended up with all this data which gives for each piece a kind of map of where it should go if it wants to survive or die or do something that's common or uncommon so use that data to construct players for this tournament they're all pretty boring actually but I'll describe what they do safe seeks out spaces that are safe where the piece is likely to live popular seeks out spaces where the piece is likely to end up whether it lives or dies they're dangerous and rare are the opposites of these survivalist and fatalist look at the ratio of dying to living on a square survivalist of course preferring to survive and fatalist figuring what the heck we might as well get this over with weirdly it has the best winning chances of these strategies next up we have a group of wimps this first one pacifists does everything it can to avoid checkmating me checking my king or capturing any of my pieces here I'm able to move my pieces well into danger without any risk unless of course I've forced the computer to capture I tried to make this strategy even worse here generous tries to offer up pieces constantly for me to capture and no I insist attempts to force me to capture its pieces looking at the results all of these strategies do very badly but pacifist is actually the worst it's the second least capable strategy of all it turns out that offering up pieces and trying to force me to capture them usually ends up leading to a drawn game whereas pacifist leaves enough stuff on the board that it's kind of hard to draw and it's easier to mate it by accident I tried to come up with other simple terrible strategies here the one called suicide King just tries to move its king as close as possible to my king it's name of course is literal but also the name of this famous face card so you'll see that instead of that's I have drawn the pieces as carefully pixelated playing cards naturally everything came falling apart because these cards must be black of course they represent black pieces but the suicide King is formerly the King of Hearts a red card anyway this strategy is easy to beat as you might expect but it performs better than even playing randomly moving the King aggressively like this is enough to beat rather than draw against unambitious players now I know it looks like I'm never gonna finish this table but there are a few large batches of players coming up this next one is about traditional engines this is the standard way that people go about writing chess computers which computer scientists have been studying for decades the basic idea is this for any given board we want to be able to assign it a score that's called the evaluation a simple thing might be to count how many pieces I have left then I'm gonna do game tree search the game tree consists of taking the position that I'm trying to make a move for looking at all possible legal moves and the positions that result from that move now it's your turn so I look at all of the possible moves that you would have and all the positions that would result from those moves I do that for each of the boards now it's my turn again so I look at all the moves that I would have and so on now this tree gets really big really fast so of course we stop at some point so when I stop expanding the tree I can just give a score using the evaluation function to that to that position now the inside of this algorithm which is called minimax is that when it's my turn I'm gonna pick the move that gives me the highest resulting score so far on this board I would choose d4 because the score of that board where I stopped was 10 since it's my choice this overall node can be thought of as also having score 10 but conversely when it's your turn you're gonna pick the move that gives me the worst score so here with these scores you would pick this move maybe it's d5 which results in a score of 2 so I'm not gonna get to play this move that gives me 10 or 100 points because you're gonna avoid it so the red ones get min of the scores beneath them so min and Max give us minimax and there are many many many refinements this algorithm alpha beta pruning and killer move heuristic and all that now my chess players don't do any of this but that's because many people have already built chess players that do these kinds of well-known good algorithm with great evaluation functions so one such engine is stock fish stock fishes I think the best a freely available engine and its rating is so high that it implies it would beat every human player every time even running on your phone so it's pieces get this Cylon I okay no no need to watch this so looking at the results stock fish takes the top slot it's actually configurable with a number of different difficulty levels which are here 0 5 10 15 and 20 and 1m is where I allow it to search 1 million nodes 1 million of those states in that game tree it only takes about one second for it to search that I compared another engine that I found the internet called Topol given 10 thousand 1 million nodes respectively it is clearly a lot weaker than stock fish but but also all of these are way better than my silly strategies which is to be expected here we see a lot of X's the best stock fish configuration always beats the weak players whether it's playing as white or black I can also use the stock fish engine to play as badly as possible here I run the stock fish engine on each possible move but pick the one that it likes the least as very bad there's that's checkmate this is indeed very bad way to play but it could be worse looking back at the game tree effectively what I did is take the top level and instead of taking the maximum score over all of the moves I take the minimum score I prefer worse moves but the way that I decided how good a move is involves this back-and-forth minimax algorithm where I assume that later I'm gonna play the best move but of course when I get there I can play worst moves so I might actually get the wrong idea about what the overall worst move is such a change would be rather invasive to stock fish that's why I didn't do it but you know exercise for the reader looking at the results unsurprisingly this is the overall were strategy and it manages to lose to almost everybody in 1989 we shrank down Gandalf and trapped him inside a Nintendo game to play chess for the rest of eternity he's known as the chess master so this is a traditional chess engine but was written in 1989 for a system that's pretty underpowered than a Nintendo Entertainment System an 8-bit microprocessor but I like it because it's an earnest attempt to write a good chess engine just limited to the techniques and computing capabilities of the time I'd like to run this in my tournament and I don't want to do it manually if we peer inside the Nintendo's memory which is quite small we can actually see where it stores the board these two right here are the two pawns in the center you can see if I move one now it's here so in emulation this is a fairly straightforward thing to do to read off where the board is but I want to be able to feed it in arbitrary position and have it run its engine on that position to make a move it turns out if you just modify the board in memory it goes haywire because it actually stores some redundant information about the board and it gets confused if it gets out of sync but chess master does support this board set up mode in board setup mode it does seem to tolerate me editing the board so that's what I do I set the emulator up and fake a series of button presses in order to get it into the state modify the board then have it play a move and now I can play against it in my custom viewer maybe we should move gandalf out of the way here the emulator also provides a screenshot of what the nes sees which should be the same as long as i did it right which it did taking a look at the results chess master has two different difficulty settings and indeed difficulty two is better they're in the same category as the strong engines let's say but note that both versions produce draws against some pretty stupid strategies too here's a perversion not known to the ancient ones remember this game tree diagram well it's really pesky I have to consider both my moves and the opponent's moves so what if I just get rid of the opponent's moves with this strategy called single-player I do game tree search but as if I'm the only one playing I can't even do this in my viewer program because it won't let me make two moves in a row but here's an example of what I might do at the beginning of the game I only look for checkmate and I only look for moves deep which is often enough here at the beginning of the game scholars mate only takes four moves as an algorithm this is actually perfectly decent most of the time it's able to find a sequence of moves that can mate at least while it still has a lot of pieces on the board the desired sequence and the outcome is shown in this debugging view looking at the results this is a rather good strategy it's better than chess master level one it always wins against unambitious opponents but it can't quite compete with stockfish which knows that there's another player in the game now how do you think about the best chess player it's rational right and what's more rational than numbers this next weird idea which I'll use the Tom Academy background for is a way of turning a number into a game we've already seen how we can characterize the choices in a game as a tree here instead let's take the interval from zero to one and let's say we're looking at a position that has a choice of three different moves then we'll split it up into thirds each third representing one of those three moves for each one of these moves there's some set of moves that the opponent can make in response let's just look at one of those responses to e4 of course there are more than three actual moves in most positions and let's say there's two responses to e4 so we'll divide that space in half of course we do this for all of the moves but here I'm focusing on the case where I played efore similarly we can focus on the case where the opponent played e5 let's say there's two moves again and so on and so on so the idea now is if I take a line and I draw it through this space somewhere between 0 and 1 the boxes that it intersects are a sequence of legal moves that make up a game so every number between 0 and 1 corresponds to a specific game and in fact each game corresponds to a contiguous range of numbers so this means that we could look at a specific number say PI and actually since that's not between 0 and 1 we'll look at it's fractional part and that would be about here we just need some canonical way of ordering the legal moves in any position and I'll just use alphabetical by their standard move name so we can watch this game let's do it there's nothing particularly remarkable about this game except that it comes from one of the fundamental constants of the universe it eventually ends in a draw so what we just saw was kind of like pi versus pi pi playing against itself to turn this into an algorithm that can play other players the most straightforward way to do this is at each step whether it's my turn or not I'm gonna look at the box that my purple number fell within and I'm just gonna zoom in on it in order to give me a new number from 0 to 1 then I subdivide again based on the number of moves this time it won't even be my move but I'm still gonna do it find the interval within which my Purple Line lies call this 0 to 1 again then subdivide based on the number of moves let's say there's just 2 here I like how this zooming is basically a literal representation of a problem that I really end up having you'll see how it's making my lines really thick and my all of my error is getting really messy and in a computer numerically when I keep multiplying these inaccuracy does magnify so now if I have two moves in so the interval Falls here I don't actually know which interval this Purple Line is in it's kind of in both so to implement this I'm actually keeping a rational approximation of both a lower bound and upper bound of the number of interests a PI and I do exact computations on those and if I'm ever in a situation where I'm straddling two intervals that means I don't have enough precision and I need to actually kind of start over so I implemented this for the numbers PI and E and not surprisingly they're pretty similar to random by the way we can actually think of alphabetical which picks the first move alphabetically as being the same strategy applied to the number 0 it's equivalent also in this list our binary versions of en PI which is the binary expansion of those constants in order to select the move just another twist on the same kind of idea of all of these binary e actually performs the best and that's because it's preferred opening so to speak makes more sense than the others now two more nice strategies a kind of wish I had covered these earlier when we both had more patience left first minim ponent moves just makes moves that minimize the number of responses that as legal moves that the opponent has after making them this is a really simple strategy that encompasses some basic chess principles for example checkmate leaves your opponent with no moves so it's the best one capturing pieces tends to be good because then the captured piece doesn't get to move because it's like dead second the equalizer here pick a piece that's moved the fewest number of times the beginning this is any piece they've moved 0 times and move it to a square that's been visited the fewest times what's nice about this strategy as it tends to move all of the pieces away from the starting position and even though they move randomly this does quote-unquote develop them and puts pressure on the opponent these strategies are both much better than random minimum opponent moves really strikes a great balance between being simple to describe and I think anyone would discover that same strategy and actually performing rather well it's one of my favorites do you remember 10 million years ago when I told you about color blind and peace blind chess well now we can finally talk about my not very good solution to this problem it's actually really straightforward I break the problem to two pieces the first step is simply to predict what the actual board is from the 64 bit number which is all that this chess player gets to see that's kind of the hard part then from that board I'm going to predict a move I'm gonna use stockfish since it's a great engine for making moves if I was able to guess the board perfectly this would work great but there will be some complexity to that so how do I take this ambiguous representation of a board as 64 bits and guess the board the answer like the answer to all questions is machine learning specifically I'm going to use a neural network and the setup here is pretty standard for this kind of thing I gotta say neural networks are really cool they do work but it is so fiddly to set these things up right there's all these constants you need to set then if you don't get them just right the weights go cramming off into a sea of infinities and Nannes which is no good I of course made it harder on myself by building everything from scratch so here's a diagram of the set up each layer has a certain number of cells and each cell is a floating-point number nominally from 0 to 1 for the input there are 64 of these which correspond to those 64 bits a bit is set to 1.0 if there's some piece in that cell and 0 otherwise then there's a few hidden layers which first expand the input and then contract it finally the output is for each of the 64 squares 13 different values which predict whether each of the 13 different contents of that square is in that square independently so here for example it's saying there's a point 9 sort of prop ability that this is a black pawn I also predict whose turn it is and whether each side can castle in each of the four ways now the nice thing about this setup is that if I can just take a bunch of boards which I can get easily from the Lee chess database I can produce billions of training instances I just take a board that occurred in a real game I turn it into its 64-bit number and now I have a pair of an input in an output which can be used to train the network here's what it looks like when the neural network is training up here are the input bits then we can see the hidden layers and their activations this is the output which is annotated with mistakes if there are any hello and pause this no mistakes here but here on this one it predicted that there's a black pawn here but it's actually a black knight I'm also showing the error values and back propagation not much you can get out of that but it is kind of cool to watch the fireworks here are the results of evaluating this as a standalone problem almost twenty percent of the time it's able to predict the entire board correctly exactly correctly which I think is pretty good given that this has to have some mistakes since the representation is ambiguous and of course when it gets it wrong it often comes pretty close the average number of pieces wrong is 3.2 - we can also use this thing interactively here I can set a bit mask and ask it to predict it for really easy configurations it definitely gets this right for weirder configurations well who knows here it hasn't predicted any positions for the white King which is impossible and is going to be one of the complexities as I try to use this to make moves so let's play against it the debug interface is going to show the predicted board before the computer makes its move this of course lets me take advantage of it because I can see whether it has misconceptions but for the purpose of this video obviously you want to see as I play standard moves it's going to be able to guess exactly what's going on and it's going to make very strong responses but as it gets complicated it's it starts to make mistakes here are things that my queen is its bishop and if I make silly moves here I put the Queen in extremely unlikely situation offering it up for capture it thinks that that's still it's black pawn so now I can safely capture the rook now it thinks that's its rook and so on so I can really take advantage of this play I know how it works that said stock fish shows me as losing here after all I'm gonna lose this rook this version called blind Kings already has a little bit of logic beyond the neural network if the neural network predicts a board that's invalid because as too many or too few Kings then I fix it using the square with the highest probability for a king this is because although stockfish is a really good engine if you give it an invalid board it crashes faster than Bandicoot but to improve upon this problem where some of my pieces can disappear to the blind player we're gonna do a little trick called the spy check remember the rules of color and peace blind chess rather than just predict one move which is often gonna be illegal because it gets them the position of the board wrong it actually produces a ranking of all of the moves and the rules are the first move that's legal is the one that's played so I'm going to take advantage of this to do the spy check specifically I'm worried about the case that one of the opponent pieces has infiltrated my position here I'm black and that I'm now predicting that to be one of my own pieces the move that I actually want to play here is Knight to this square if it's in fact this board that'll be one of the moves that I output but ahead of that and the ranking I'm gonna manage to put a bunch of spy check moves and a spy check move is basically for every piece that I've predicted is my own and every other piece that I've predicted is my own I'm gonna try to move that one piece on top of the other so up here in this list I'm going to include try capturing this piece with that one try capturing this piece with that one try capturing like this try capturing like this and this will include this rook which is actually a bishop trying to capture this pawn which is actually the White Queen because it comes before this legal move that will be the one that's actually played this heuristic assumes that of course capturing when I'm confused about what the board state is is better and it doesn't really have a strong preference about which capture it does this turns out to help a lot though let's try playing against it I tried infiltrating the position again with my white Queen which it thinks is a black pawn but it was able to successfully do a spy check and eliminate it with its rook this successfully corrects for a huge weakness with the blind strategies now their main weakness is just that in the endgame they have no idea what's going on and it's pretty easy to open for them looking at the results all of these are substantially better than random and that's good so something good is happening here and spycheck helps a lot it comes in just shy of the cccp strategy which although it's simplistic it does have full knowledge of the board and what where the pieces are so it has a bit of an advantage a natural criticism of what I've done with the neural network is that I'm really just memorizing board States and that I haven't actually learned what chess boards look like and neural networks are in fact really good at memorizing things we can compare that strategy directly of just memorizing boards that have been seen before and the most popular move played in that position thus building a sort of gigantic opening book in the lis chess database of 500 million games there are about 21 billion positions reached if I wanted to store the move made in each of these positions one way to do that would be to store a hash of the board which would take about 64 bits and the move that's played which takes 12 bits then this would take about two hundred and four gigabytes this would be using the most efficient packed representation if I wanted a hash table there would be some overhead for that and even in my completely gratuitous desktop computer I have only 128 gigs of RAM and of course there would be ways to store this on disk or whatever but but there's also really diminishing value to storing these if I look at all of the positions that ever occur most of them only occur just one time that's like 76% of them are only seen once so these take up a lot of space and they're not very useful for playing because I'm very unlikely to ever see them again and of course since there are so many the distribution looks very regular here a log-log plot I really like this diagram this shows us two competing effects making this sort of Joker smile on the one hand most positions appear extremely rarely this is logarithmic so at 76 here there are a few positions that account for almost 1% of the database like the most common first move which is e for these patterns in the middle are just descritization error but they look pretty cool so to make this tractable I just store positions that occurred more than one time this is only 15 million distinct positions and I can store all of the moves that were played in that position over all of the games and this takes only 500 megabytes which I can easily expand into a hash table in memory so to turn this into a chess algorithm it's really simple I just look up the position that I'm faced with and see if it's been played before if it has I just take the most popular move in that position which tends to be a good move here it's able to follow along with the Queens gambit declined quite deep but as soon as I make a little bit of a weird move it just starts playing randomly and then it's very easy to beat this player performs significantly better than random due to its knowledge of openings but also significantly worse than the blinded players the neural network that's part of the blind strategy is only five megabytes in size so it also has a hundred X the efficiency of encoding these states and generalizing from them even if it is just memorizing them so that's pretty good result finally we're gonna fill in the remainder of the blanks with one type of strategy which is really a meta strategy for the katha allure ratings of all of the players we've seen so far there's actually a really large disparity between the best players especially stockfish in the rest of the field and given that this isn't a linear scale this can cause some problems for example let's look at a hypothetical tournament now let's say there's two classes of players here which is more or less what we see there's the lousy players and then there's the engines when plough Z plays lousy or engine plays engine it doesn't really matter what happens let's say it's a draw let's say that if engine plays lousy it always wins and if a lousy plays engine it always loses this is a problem for our tournament analysis because although it's clear that the engines are better than the lousy players which is what we'd expect it's hard to tell how much better if it's really the case that they always win or almost always win then imagine the engines are actually a hundred times better than they really are or a thousand times better than they really are you're still gonna see this same outcome making these engines better isn't gonna make them beat lousy any more often than always in practice we do see an occasional victory of a random strategy against an engine but ideally we'd be blurring these lines a little bit not just for aesthetic reasons but because it helps the ellow algorithm actually produce more accurate scores the way I want to do this is with interpolation following the methodology that's used to determine how spicy food is is called the Scoville scale we take the item that's to be tested some kind of spicy oil and we feed it to an official tasting genius who has a golden tongue we also ask this genes to taste some sugar water of course the genius can tell these apart so step one is done then we download the spicy oil 50% with sugar water and see if the tasting genius can tell it apart from sugar water of course they can so we passed that round but we keep doing this at the point where the genius can no longer tell the diluted solution from sugar water that's where our count stops and that's what defines the Scoville scale so let's do a similar kind of interpolation with our strongest engine which is stock fish the way we'll do this of course is it just flip a coin and with a certain probability either play a strong move using stock fish or play a random move using well another coin so I introduced a number of different players at different concentrations of stock fish so to speak and this does in fact smooth out the tournament a lot up here is what we're the graph we were just looking at without these players and you see a very large peak for the strongest stock fish here we see a smoother curve and this is because of stuff of players like 99% stock fish that play almost as well but every once in a while make a random move as we would expect the more stock fish you have the better you do even a 1.5% solution is substantially separated from random move and even 99.9 percent stock fish does a little bit worse than pure stock fish this makes a nice gradient between the strong engines and the lousy players which helps with the accuracy of the tournament another nice thing about this is that we can actually assess how good a player is now by comparing it directly to a specific die Lucian of stock fish this gives us one more pretty good way to say how not good my blind spot check algorithm is we can say that it's somewhere between a 6.2 percent and a 12.5% solution of stock fish mixed with random moves so there you have it a pretty picture 30-something lousy ways to play chess a pretty careful evaluation of my mediocre solution to an unimportant problem and 40 minutes of our lives down the drain condolences and congratulations if you made it through the whole thing if you have your own ideas about lousy ways for computers to play chess feel free to suggest that my might add them to this tournament for now it's on to the next project which is teaching this dog how to play chess it it's going it's going pretty well

Channel: suckerpinch

Views: 369,132

Rating: 4.945786 out of 5

Keywords: chess, machine learning, arithmetic encoding, blindfolds, chessmaster, stockfish, scoville scale, chess to the death, neural networks, symmetry

Id: DpXy041BIlA

Length: 42min 35sec (2555 seconds)

Published: Mon Jul 15 2019

Reddit Comments

[u/kuzux]

The chess playing robot in the video is labeled "Satranç Otomatı" - "Chess Automataton" in Turkish. Probably a play on the mechanical turk.

[u/generalpurposenothin]

Totally bullshitting on the lake/mirror/lens polarization there.

[u/mitchneutron]

Okay I need to subscribe to his videos on YouTube. Some of those algorithms were so cool

[u/gergoerdi]

Further details in the SIGBOVIK proceedings: http://sigbovik.org/2019/proceed2019.html

[u/twdrake]

Absolutely loved this - definitely giving his other videos a go.