Player of Games: All the games, one algorithm! (w/ author Martin Schmid)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper reinforcement learning ai for go ai go ai chess chess ai stockfish alphazero alpha zero muzero player of games pog deepmind deepmind games imperfect information games ai for poker perfect vs imperfect information public state scotland yard ai for scotland yard reinforcement learning poker ai no limit holdem counterfactual regret minimization tree search
#playerofgames #deepmind #alphazero

Special Guest: First author Martin Schmid (https://twitter.com/Lifrordi)
Games have been used throughout research as testbeds for AI algorithms, such as reinforcement learning agents. However, different types of games usually require different solution approaches, such as AlphaZero for Go or Chess, and Counterfactual Regret Minimization (CFR) for Poker. Player of Games bridges this gap between perfect and imperfect information games and delivers a single algorithm that uses tree search over public information states, and is trained via self-play. The resulting algorithm can play Go, Chess, Poker, Scotland Yard, and many more games, as well as non-game environments.

OUTLINE:
0:00 - Introduction
2:50 - What games can Player of Games be trained on?
4:00 - Tree search algorithms (AlphaZero)
8:00 - What is different in imperfect information games?
15:40 - Counterfactual Value- and Policy-Networks
18:50 - The Player of Games search procedure
28:30 - How to train the network?
34:40 - Experimental Results
47:20 - Discussion & Outlook

Paper: https://arxiv.org/abs/2112.03178

Abstract:
Games have a long history of serving as a benchmark for progress in artificial intelligence. Recently, approaches using search and learning have shown strong performance across a set of perfect information games, and approaches using game-theoretic reasoning and learning have shown strong performance for specific imperfect information poker variants. We introduce Player of Games, a general-purpose algorithm that unifies previous approaches, combining guided search, self-play learning, and game-theoretic reasoning. Player of Games is the first algorithm to achieve strong empirical performance in large perfect and imperfect information games -- an important step towards truly general algorithms for arbitrary environments. We prove that Player of Games is sound, converging to perfect play as available computation time and approximation capacity increases. Player of Games reaches strong performance in chess and Go, beats the strongest openly available agent in heads-up no-limit Texas hold'em poker (Slumbot), and defeats the state-of-the-art agent in Scotland Yard, an imperfect information game that illustrates the value of guided search, learning, and game-theoretic reasoning.

Authors: Martin Schmid, Matej Moravcik, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Marc Lanctot, Zach Holland, Elnaz Davoodi, Alden Christianson, Michael Bowling

Links:
TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
LinkedIn: https://www.linkedin.com/in/ykilcher
BiliBili: https://space.bilibili.com/2017636191

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hello everyone, today is a special day. I'm here, as you can see, not alone, not by myself as usual. I'm joined by Martin Schmidt, who is the first author of the paper called Player of Games. This is joint work with others by DeepMind and I have to say it's a very in-depth paper. It presents an algorithm called Player of Games that is sort of a unified algorithm to play all sorts of games. This starts at things like chess and go, which you might know from AlphaZero, but it goes beyond. It goes to things like poker and Scotland Yard, which I found really interesting that it appears here. But sort of the common denominator is that these new games, they have hidden information. So other than chess or go in Scotland Yard, you don't know where Mr. X is hiding. In poker, you have no clue what cards the other players hold. So you can't just look at the table and poker and decide what's the best thing to do because you don't know a lot of things. Same in Scotland Yard. There have been algorithms for poker, right? There have been algorithms for Scotland Yard, but they were always a bit tailored to sort of the specifics of the games. Player of Games combines a large set of techniques. And these techniques are things like, let's do search. So as we play the game, we do local search. We sort of invest some computation at inference time to tell us what the best possible move is. But we don't want to search throughout all the game because these game trees, they just get very big. So that's the part that comes in from AlphaZero a little bit. But then the other part with the unknown information that is coming in mostly from the from algorithms like counterfactual regret minimization, and so on. But yeah, the counterfactual regret minimization, if I understand these correctly, they were sort of solvers, like they either solved a complete game or they didn't, right? You'd have to like traverse the whole game. And then at the end, you knew, okay, in this situation, I need to do this and so on. And yeah, this, I was very excited when I saw this paper. And then I tried to read it. And it was, it was, it was, I have to say it was dense. And I'm very happy to have Martin here today, to guide us a little bit through the paper. So Martin, welcome. Thank you very much for being here. Hey, I'm happy to be here. Was it a sort of a good description of what I said so far about player of games? Oh, yes, very, very, very much so. If you could summarize sort of the main components of this algorithm. So this is a single algorithm that I can train on many, many games. What is the set of games I can train it on? So the currently we use, we use four games, the games that you mentioned, we have, we have chess, we have go, we have Scotlandia, which I find as a very cool and fun game. And we have, we have no limit poker. So that it's just to show the generality of it, because this is all about the generality. That's why we pick like two perfect and two imperfect information games. Yeah. So currently, it should be able to handle, handle most perfect and imperfect information games as it plans. So from scratch from self play, just like Alpha Alpha Zero does. There are some, some, some limitations for games that this can handle. And we can, it's, it's best to understand the limitations only after we understand a bit more about the algorithm itself. Yeah. So the algorithm itself is composed of many parts, but the, the central concepts here, I think are, and that's what people, I think people kind of know what Alpha Zero does, right? It, it uses self play and it searches, it searches a game tree to a certain depth, right? So, so it, in these games, we usually have like some sort of a state, right? And then we have various different actions that we could take in that state and every action leads to a next state and so on. And we have various different actions we could take right here and every action leads to a next state. And you can quickly see how this explodes, right? So what, what Alpha Zero and all these search algorithms do, they do this kind of limited depth search, right? They look maybe one or two moves ahead, but at some point they say, okay, no further. We can't afford to compute all of this tree. And that's why at a certain depth or after a certain time, they say, okay, here we cut off and we use like a neural network to tell us how good this node is. Even though we're not at the end of the game where we would either win or lose, we could still have a neural network that sort of predicts this node is, is very good for you or this node is very bad for you. And that's, that's essentially Alpha Alpha Zero in a nutshell, let's say uses self play, uses this tree search at a certain depth. It simply asks the neural network. Now what's the, what's the problem when you have imperfect information? How does, how does this change? Okay. I know that's, that's, that's the, that's the right question. Unfortunately, we probably spend quite some time to understand the intuition of it. Right. But even for Alpha Zero, it's, it's good to step back and see where it came from. It's not, it's not that Alpha Zero introduced search for say perfect information tips, right? Search has been here since 1950s, like first, first algorithm for, algorithms for chess did combination of search and some value functions. Alpha Zero is amazing in the sense that it learns those value functions that you just described for self play. And it's also really, really smart about how it's going to expand its search tree. It's not like it's going to always look two steps, steps ahead. It's very smart about building, building this tree that goes deep where they need to need it to go deep. But it still has those components, which these components are simply having some search tree that it ideally expands as it thinks about a policy in the search tree, and then using some value function at the, at the end of the search tree. Yeah, that is, that is one of the, one of the hallmarks of Alpha Zero. I think that, for example, in Go, you have so many actions, even at step one, right? If you were to consider only like even three steps ahead or so, this would just blow your computation budget. But as you can see, in Alpha Zero, it sort of, it sort of always starts from the root, and then it kind of goes down one of these branches that it has already explored a little bit. And in every new iteration, it re-decides which direction it should investigate. And that's a combination of sort of what the neural network says, but also how often it's been, it's explored something. So it says, you know, like this direction is very promising, but I've explored it a lot already, so now I'll go, I'll go a different branch or so. And then at the end, it always goes, gets to a leaf node that it hasn't expanded yet, right? And at that point, it asks the neural network, okay, you know, what's, what's my policy here? What's my value? And then it prepares sort of the next iteration that it could expand it even more. And so over time, it builds this very targeted plan. So the neural networks guide the tree search, as you say, that's very, very cool. And in imperfect information games, that is, yeah, that is different, right? Yeah, so it's somewhat different, but we still wanted to have exactly what we just described. This is like why Alpha Zero works so well, and we still wanted it. So on a high level, you can think of playoff games as combining, combining Alpha Zero and DeepStack, which if you were to Google DeepStack, it was the first AI to beat professional players in no limit poker. And it already introduced some of the ingredients that we will see in this paper, which is it introduced this notion of local search in poker and these value functions. And playoff games is really just putting together Alpha Zero in DeepStack into a single big unified algorithm. So let's maybe start with the component that you just talked about, which is value function. And the value function, if we get to a point where we understand value function in playoff games, say it's then you understand like 60 to 80% of the algorithm and complexity that imperfect information brings. So value function, if you think about how to use it, exactly as you said, rather than searching all the way to the end of the game, because it would be like way too long of a search, you just trumpet your search and use value function as a substitute for continued search. And that's how you use it. But what it really does, it maps some sub problem that you are thinking of to a game value of that sub problem or sub game. In chess or in Go, it's really easy to think about what it really is. You get to a new board, chess or Go board, and the value function ideally should tell you, hey, this is the value of this sub game. What it really means is what would be the outcome if two optimal players were to continue playing this game forward, right? So that's all the value functions do. And the same thing they do if you try to generalize them into imperfect information games, except that suddenly this notion of sub game and sub problem gets way more complicated. Yeah, so this basis on this notion of information states and sort of public beliefs about things. So on the left here, you've tried to show this in a diagram. And I think the notion is when I come to a poker table, I only see what's called the public state, right? I see and actually, if I come to a poker table and I observe a hand with all of its history, right? That is the public state. So I know, you know, who bet how much in which round and so on who acted how, but I don't see people's cards. So there could be many different cards that people hold. And some might be impossible just from the rules of the game, you know, maybe not in poker, but you know, in Scotland yard, you have this over here, there are certain locations, this Mr. X can be. And we want to assign probabilities to each one of them, right? If we knew if we knew where Mr. X was, the game would be easy, right? But since we don't know, we must estimate and I think that's also something you highlight in the paper, an interesting property of these games is that if I am Mr. X, or if I play poker, I have to not be deterministic, right? Otherwise, the game would be very easy for my opponents. If that's in poker, usually, you know, people they look at their cards, they go, and then they like bet everything they have. And you know, immediately know which hand they have if they don't also do the same thing with other other whole cards, or if they don't randomize a bit. So necessarily, other than, let's say in chess, the optimal strategy is kind of a distribution over actions. And you have to sort of randomize that in order to almost a bit hide your, your, your private state. So what we what we see are these public states, right? And what we can estimate is these things, which are called the ranges. So these are distributions over what private states the players could hold. And the thing the difficulty in this tree search comes from the fact that you can only go from a public state, yet you need to consider all the possibilities of the private states. So you can't just say this is the situation, you have to sort of consider all of them at the same time, right? Yes, exactly. That's, that's what you basically need in order to generalize those sub games or sub programs to improve information, right? It's not hard to hard to see that all perfect information games are just a special case where you have just a single single possible state for for for the player, right? Like a poker, you just talk about poker and public state states, and that's a that's a that's a perfect example, right? Like a sub program in poker, it's it makes little to no sense to say what's the value, what's the value of a sub game or sub program in a poker where I hold a pair of aces that's pretty much ill defined, ill defined sub game. What we what you need to do is given a given a public state, which is, as you say, I come to a table, I see everything that I could have observed as a public observer. So that's that's that's basically my state. But given this state, given this observation, there's a lot of possible individual individual states of the of the game that are consistent with this observation. And this simply correspond to all the different cards the players could be holding. And sub game is simply defined by by combination of this public state, which is the thing I get to observe as a public observer. And then I can see that observer and a distribution over all the possible private states that could be happening right now. And given this distribution on top, this simply defines a well defined sub game. And given this well defined sub game, I can suddenly ask questions of, well, what would what would be the values of this sub program given that they all the agents play the sub game optimally, just, just as you in chess or go? Yeah, I we used to we used to play poker a lot in like high school. And this was frequently you try to not try to guess what hands your opponent have, but you try to guess you know what their ranges right. So you consider like, okay, it's often going to be these cards, it's less often going to be these cards. I think that mirrors very much the reasoning that that people actually have in these things. And now given given this you at the one of the core things here is this neural network that is supposed to tell us what the values of the sub game is, right. And this, as you said, it gets us an input description of the public state. And it also gets as an input, your beliefs about what distribute like your beliefs about the ranges of the players, so what their private information could be and how often and if I remember correctly, these ranges, they're just a result of their strategies, right. If you know the strategies of the players, then you can calculate what their ranges are. Because if the strategy is I always bet high when I have aces, then if the player bet high, then aces are quite likely, you put all of this into a neural network, and the neural network gives you policies, which is understandable, it's how would a player act in a given situation. This is also what AlphaZero gives you. But then you have these counterfactual values. And this is a bit of a new term that only appears in, I think in imperfect information games, what is a counterfactual value? Right. So in this case, this value function very much is analogical to AlphaZero in the sense that you have values and policy or policy for a sub game. And we use them in very similar way. Except as we just described a sub game is, there's many possible states the game or the players could be in given a public state sub game or public sub game. And the value function given this sub game outputs not just a single value that says, hey, value of this sub game is five, it actually outputs a single value for all the possible player states that are possible given the sub game. So in poker, say I could be holding thousand different hand combinations in holding poker. So the network will tell me, hey, in this sub game, if you were to hold this particular pair of hands, this is the value and it will tell me such value for all the possible states I could be in. Yeah. Okay. And the neural network, how is it built to output? Does it have like one, let's say one output head? So does it output like a thousand dimensional vector one entry for each? Okay. So is it fair to say that your algorithm would struggle with games where the possible private states are huge? That's yeah, that's the this is brilliant. This is exactly why I said it will be nicer to understand the limitations once we get a bit deeper into the algorithm. And this is exactly the main limitation that we currently have because in some games, this just explodes. Yeah, I see. Okay. And you have this network and you train it in some way via via self play. And now we get to the part where you generalize this search procedure, right? And let me see. Oh, this is here. So this search procedure, as we said in in alpha, again, in alpha zero, you have something like you're at some state in the game, right? You've played until this state. And what you do is you do this search and you use an internal like simulator to do the search. This is at inference time. So what you do is you consider all your actions, you choose on one by given the neural networks output and the current search statistics. You go here, you ask the neural network, well, what's my value here, you expand that node. And then you start again. And then the next iteration, you start again from the root, you expand maybe the same or maybe another action, it depends. But let's say it's the same right here. If it's already expanded, you go further down the tree. And you would you would sort of you would make many iterations, let's say 50 iterations or something like this. In every iteration, you'd go down the tree, and you find a node that you haven't expanded yet. And you'd expand that node, right? In in in player of games, this is quite a bit more intricate, right? As as we also have many iterations, but within each iteration, we have to do a lot more work in order to actually in order to actually deal with with this uncertainty. So could you describe a little bit how your search algorithm works? Yes, happy to. So when we said at the beginning that player of games is a hybrid of deep stack and alpha zero, search algorithm is a perfect example of of this being a hybrid. So what deep stack already introduced is it, it had a fixed search tree. So you are poker players. So you what it really did is it search all the way through a single single betting ground. And it used value functions at the end of the round. And it ran this kind of actual regret minimization, which we might come back later to. But you can think of it simply as some some policy improvement algorithm given a fixed search. It would iterate and improve the policy and as it was walking up and down the tree and finding a good policy, it would use the value function at the end of the search tree, the very same value function that we just talked about. Now, player of games, it's this this smart idea of alpha zero, where it also tries to dynamically expand the search tree or didn't have enough fixed surgery. And the way it does we simply see intertwined two phases where we in one phase, given the sample given some surgery, we try to improve the policy within the surgery. And there's a second phase where it simply tries to expand just like alpha zero does using the same say PUCB PUCB formula, we try to expand the search tree where we think we need to expand it. And then we simply go back and forth with you like an expand the tree, improve the policy, expand the tree, improve the policy. Yeah, so this is built on an algorithm that is used that called counterfactual regret minimization. And this is an this is if you were to just apply a counterfactual regret minimization, this is a solver, like I give it a game description, and it just it will expand the entire game tree every state there is in the game. And it will just sort of go from node to node in this tree and improve the policy of both players, right. And it just does this for many, many iterations, it improves here, here, here, everywhere in the game tree, until the whole game tree is approximately optimal. And the biggest game that has been solved so far, if you describe this in the paper is limit, limit heads uphold them. Is that correct? Fixed? Yes, hold them. Yeah, that's, that's actually a solved game. Yes, it was done a few years ago by the by the computer research group at the University of Alberta, led by Michael Bowling, and it's still as far as I know, the largest game to be solved. And you use the word solver, which is a perfect, perfect name, really. And like the way I think about the solver is you give me some small or medium sized game that I can fit into like a big table on my computer. And by solving it means simply find a policy for all the possible states in a game. It's easy to see that it's like, I mean, people do know how to do it in say, tic tac toe or small, small games, right. And if you were to fit chess on your computer, then again, it's not hard to see that you could just solve it given the algorithms that people are familiar with. The thing is, even if you have a really, really small information game, you do have to use algorithms that that can handle imperfect information games. Often people just use algorithms that they like, say, I don't know, like policy gradient methods, Q learning or whatever. And if you just run it on imperfect information game, it just doesn't find a good policy. Yeah, I think the I mean, intuitively, it's a bit like if I start in some situation in chess, and I make some moves, I have I have still like that original state is still the same, right, I can I can look back, I come from there. But if I'm in poker, and I'm in some state, and I make some moves, that changes kind of the past, right? Because I look at, you know, maybe you're my opponent in poker, I look at what you do. And that changes my beliefs about what you what cards you had back in the past. Then I go back and I'm like, Oh, okay, you did this and this. So you can't you can't, I don't think you you will you're holding, you know, a king and an ace, given that you've done something in the future. And I think this, the fact that your future actions change the past, that's what, in my opinion, makes this so much more intriguing and complicated. So on the left side here, I think this is the this is you have a search a local search tree, right? You it's expanded until some depth at that depth, you asked the neural network for, you know, summarization of whatever happens below. And within that tree, you run now this counterfactual regret minimization or something akin to it, and you simply want to find the best policy within that tree, which is more complicated in alpha zero, I just visit every node once right, because the future doesn't change the past. Once I computed a node, I only expand things below it, that never changes that node. However, in imperfect information games, right, if I change something below, all of a sudden, the the past changes, so I need to sort of update and converge the whole tree. And then once you've done this for a number of steps, on the right side, then you add a new node by essentially doing what alpha zero does, you go to a leaf node, you choose some action, right in some information state that passes, and you perform that action, and that expands actually one more node. Is that you know, this is this is excellent. And the the property that you just described, like the future change in the past, that that is also something that makes search in particular, so much more complicated, right? Because there's you can figure with a two step process, if you were to just solve solve some game, you will just solve it, even that is more complicated, because of what we just described, but you could do it there. There's ways to solve solve imperfect information games. But we are doing search here. And the property that you talk about makes search so much more complicated. And the reason being is in imperfect information games, you cannot just glue together optimal policies, and hope that the resulting policy for the full game will be optimal. And that is something that many search algorithms just rely on. And it simply holds in perfect information games. So if you were to like, pick any optimal policy in any any any state and just put them together, this is an this is an optimal policy in imperfect information games. It does not hold because of exactly what we just described. But then how can you even do search at all if search is all about like local reason, right? You reason locally, you have to somehow need to make sure that the resulting policy for the full game is still optimal. Yeah, it's it's it's interesting. So essentially, for every step that Alpha Zero does, where it expands a new node, you also expand a new node, but then you have to like, get the entire tree in order again. So you expand the new node, and then you have to do the whole update of the whole tree for a bunch of iterations before you can expand another one, such that everything like stays consistent. Yeah, okay. That's, I mean, this this, it gives a bit of an impression of why this is much more, much more complex, right? Yes. So this is this is essentially at inference time, we do this search, right? We do the search. And now comes the time when we actually need to train this. So we have the ingredients. Now we have the search algorithm, we have the neural network. And now we need to train it. And you also have, you have a method, or various methods. And maybe you want to describe it yourself a little bit, because this is the part where I stumbled a little. So yeah, yeah, I will start to do it on very high level. So the idea is, again, we want it to take the self play style method from AlphaZero, so that you just throw the algorithm into a game, and it improves as the as the as it plays, and it gets better and better. And what it really means is you are improving your your value and policy, right? The network that we that we just discussed. And the on a high level, since you are using your value function in your search, you call basically call your neural network with some inputs, some states, public states, some beliefs. And this, this figure, this idea of queries is simply we call every single time we call a network, we call this a query, we are querying a network for some value over some game. So we store this we store this couple of public state and beliefs. And then we go through all this all those queries, and we simply try to basically improve the network on the states and the syringes that the network has been queried, because this is probably what's important because that's what occurred during the self play. So you collect the train is similar to AlphaZero, as you say, you collect the training set as you go. So the training set for the next iteration is whatever the network had to do during this iteration. So it's not just a random sample of states. And you train in the same manner as AlphaZero, you train to predict your own future outputs, is that approximate? So if let's let's distinguish if, like one or two or three steps in the future, you actually win or lose the game, you can train on your reward of the game. But AlphaZero also, if it doesn't win or lose the game in the next step or so, it tries to predict its own output. So it tries to improve that way using TD lambda. You here have TD one, right? So your targets, what do you target? What do you give the network as labels? So okay, so this is slightly more complicated here in the sense that each query basically defines you something, right? It's a public state and energies. And given a sub game, the ideal target for your neural network would be simply to solve the game, right? That's the ground truth that you want your neural network to learn or like then to work too. So rather than solving directly, because again, these sub games will still be way too big as they occur during the gameplay, we do like a small, small solver, where we also substitute the full solver with a small search. So rather than fully solving a game, we use the same method to basically do a search. And the outcome of the search, basically a small solver is what is the target. Okay, so you do the same thing as you do during inference when you actually want to make a move. So during that inference, you're going to make some queries to the network, you take these queries, and these I think here are the red dots, right? Exactly. So during maybe this has battery again. So during the inference, you make you do these queries, you store them in this in this buffer. And these now act as the root nodes for yet another search, which is exactly the same as the previous search, right? And so you you sort of rely on the fact that this search procedure can give you a better output than the neural network itself, right? Yes. Right. The query here, the neural network will output some value, like the value is eight, or one value for each for each information state. But you, I think the whole algorithm is, and that's of course, the reason we do search in the first place is that doing search gives you a better estimate than just using the neural network at the start. So doing search, and then asking the neural network further down the line gives you a better estimate. And yeah, it makes sense. You start at wherever you ask the neural network, you use local search to get a better value, doesn't need a perfect one, just a better one. And then you train the neural network to predict the result of the search. That's exactly one would hope though, that after a while, you know, if I do this again, and again, and again, at the end, I wouldn't even have to ask the neural network anymore. Sorry, I wouldn't even have to do search anymore during inference. Is that something you have you have you tried not even doing search just using the neural network that the policy output of the neural network during inference? Is that something that generally works? Because, you know, I train it to predict the output of the search. So technically, let's say it should it should kind of learn it, no? Yes, the same the same way you simply could just use the same policy network in AlphaZero and let it play chess, right? You can do it and people have have done it. It is still quite good chess, but it's far, far below the full strength of search. So yes, at the end of the day, even the policy network is quite good, but it's not as good. Okay. Yeah, I mean, it's just it shows a little bit that the search is in fact, in fact, really necessary, right? Yeah, so I think we're almost getting already to the sort of results. Wait, would you would you maybe summarize the results a little bit? I think if people are super interested, they may go into into the paper and into the tables. But maybe you can just summarize a little bit of the results you compared against AlphaZero in perfect information games, you compared against dedicated algorithms like like slombot in poker, and you even compared against like a dedicated AI for Scotland yard. What were generally the results for you? So yes, so so in general, the results are that the algorithm is all about generality, which is this is not as strong as AlphaZero in perfect information games where AlphaZero was designed to shine, right? So this this very much is trying to be a general rather than being the best chess or the best poker poker poker agent in the world. It's just trying to be really, really good in all of them at once. What is the diff? So if if a perfect information game is just a special case of an imperfect information game, right? What is then the difference between player of games and AlphaZero? Like, why couldn't it reach the same performance? So on paper, it could except that, for example, the policy improvement algorithm that we use, the counterfactual, we get minimization, right? It has to be also good able to handle imperfect information games. That's why it's not going to convert so nicely and quickly as as algorithm design design for perfect info. So the fact that you expect sometimes to see an imperfect information game, would it be fair? Would you estimate that if you just input more resources, input more computation time that it would actually reach the levels of AlphaZero? I don't think it's necessarily I mean, on paper, all of these would eventually converge. Right. Everything works on paper in in delimiter. In practice, AlphaZero and MCTS is probably always going to be ahead. But we don't really care. Right. Like, if I would be happy with a single algorithm for everything that's that's better in humans. I don't care if it's better by like a little bit or by a billion. Yeah. And then in in in poker here, you compared against Slumbot, which is you say that the best open source or best available poker bot to date. And this is no limit poker now. Right. This is this is way too big of a game to solve. And I think the other ones is you you simply compare to the numbers from their papers. Is that the do you mean for a slum bot or for Scotland that we're talking about poker? Oh, sorry. Yeah, let's let's talk about poker for a while. So the the player of games here gains what is this seven millibig blinds per per hand? Yeah, over slum bot. Yeah, again, like we we we could have beaten slum bot by by a lot more. Yeah, just like decided, oh, this is good enough to like to put into a paper, we can come back to it later. Like, as you know, it very much depends on how much time you spend tuning the network architecture and how for how long to train this is what this is just to show, hey, there's already an algorithm that can do all of these games and it still plays them really, really well. Yeah. And your neural network, just to say it's a bunch of like feed forward layers, correct? Like, it's not a complicated thing. So for poker, it for poker, it's just a feed forward network for chess and go. We do we try to mirror some of the older AlphaZero architectures. Yeah. Okay, so and here on the right side, you have Pym Bot, which is the Scotland Yard specific, but for people, maybe people don't. Does anyone not know what Scotland Yard is? Maybe you can describe 10 seconds what Scotland Yard even is as a game. It's somewhere. Yeah, there's a figure maybe, right? There is this figure, right? Right. Yeah, there's no point explaining the rules in detail, but on a high level, there's a graph, you are trying to chase down the chase down a stone that's called Mr. X, you have five detectives that are trying to chase the stone down. The trick is the stone, the Mr. X that you are trying to chase down is only partially observable. That's what makes it imperfect information. And you have to basically reason about states where he could be hiding and form some beliefs about his state and trying to chase him down. So yeah, and yeah, I guess that's all people need to know. You can spend like funny tickets on taxi rides and various methods of transport. And then every 10 turns or so Mr. X has to reveal their position. And that's how you sort of form a belief about where Mr. X could be given what actions Mr. X took. So this is quite a specific game. So it seems to me like a dedicated algorithm could do very, very well, again, in this game, because it could exploit various aspects of the game, you could hard code in various various things the AI could abuse. And here we see a graph of the win rate of player of games against what's on the x axis here, this is number of search iterations. So pinbot is a local search algorithm as well. Yes, it's a it's a it's a variant of MCTS. And this is to show regardless of how much time or search we give the MCTS, the hard code hand tune algorithm, even if it gets like a billion or something called search iterations, it's still behind alpha zero because it's using this general self play learning method. Yeah, so this is this will be I guess the final win rate is here like at 55% or something like this. And that is with a huge number of iterations for for pinbot. Yes, and we'll play our games is using only like 400 iterations on our site. So yeah, as you can see, as you can see, the regardless of the scale, we converge to a better policy. And you do you would attribute that to the use of self play to improve the strategies. It's the it's a combination of this and also the fact that player of games is built on some some on some methods like later in the appendix, if people are curious, they can open appendix, we show that on small games we were we can exactly measure how close to an optimal policy the our resulting search policy is we get closer and closer as the time goes. So basically, we are only limited by the by the power of neural networks. And we have some guarantees that we can get to an optimal policy. Other methods that are based on MCTS, they they are not guaranteed to converge even on small games. So there's there's there's there's also the limit of the of the fact that these methods are not sound. And just to get an idea of the scale of like we saw, you know, poker, Scotland yard, here we have the the chess and go and so on. Can you give us a number of just how many how many GP TP, whatever use do I need to run for how long to get anywhere close to what you did? I see. So I think the easiest for us was poker that like people probably can train on a few few GPUs. The by far the hardest is is go where we used a lot of a lot of GPUs. But that was simply because we we had them available. Yeah, I get okay. And you you did in the paper say that for comparison reasons you use sort of the same amount of compute as Alpha Zero did as well. That was that was tricky. I'd like it's like, because we do not want to claim that this is this is now state of the art chess agent and like there there we don't have to do all the proper and hard measurements, right? Then you have to use clock time. And suddenly if you use clock time, you have to argue that use the same hardware and everything gets gets more tricky. And he would just say, well, we use the we call the network as often as Alpha Zero did. So it should be roughly the same, but like we don't claim to be stronger. Okay, I mean, that's a I think community appreciates sort of fair comparison instead of every every paper having the new best state of the art, especially in RL, like it seems it seems clear just from the graphs here, like just from the lines, it seems clear, you can just invest more compute and get better. And that's what we also saw with Alpha Zero, like it used to be slightly superhuman. And now it's like, you know, no human not like not all humans together even will ever match Alpha Zero in in any of these games, which is crazy. Yeah, exactly. Do you have a bit of a demonstration ready? You told me of of of the player of games playing Scotland yard. So we can kind of see what's going on. Yeah, let me see if it's still still working. It was working this morning. It was we never plan to show it externally. We it was designed for our debugging purposes, but it would be a fun demo just so that people who are not familiar with Scotland yard maybe get some intuition about the game. Okay, so hopefully you can see this. Yeah. And the let me very quickly explain what is what is this about. I am now playing as Mr. X, which is this black color in here. And I can move all and all on on this graph basically walk walk in the edges. And as you were talking about those taxes and cubes, you can see that the edges have different colors. So all of these are yellow, but this this guy is blue. And they correspond to to different meaning of transportation that I get to use, say yellow stands for taxi taxi, I think, and blue stands for bus. Now, detectives do not get to see where I am, but they do get to see which color color details. So right now I'm in here and say I want to go through 49. And I want to use taxi together. So yeah, hopefully, like we have been talking for a while, so maybe maybe it's not alive anymore. But yeah, probably to it died. You have scaled to zero proper engineering. Nice. Yes. So yeah, it doesn't work right now. But at least people can get an idea of what would happen. Maybe. Yeah. So you'd need to you'd need to pretty quickly kind of reason. And the longer you don't see Mr. x, the more sort of fuzzy your idea gets of where Mr. x is, do you do you visualize sort of this distribution, the belief distribution of where Mr. x is or for debugging? Or we did it's I don't think it's it's turned on right now. But that's exactly what we tried to do at some at some point. Yeah. And did you see did you observe this that's the longer they didn't see Mr. x the more kind of spread out, the more unsure they become. Is that something you can clearly observe? Or is that something you just feel as a human? Oh, yes. And it was actually really, really fun to see. Yeah, crazy. And so the one improvement, let's say, or one follow up to Alpha zero was the muse zero algorithm, which, which the crucial difference is Alpha zero, you need sort of the simulator, you need to be able to simulate a lot of games. Internally, you need to know what happens when I do some action, what kind of state results from that. And muse zero alleviated this by sort of going to the latent space state and training everything in latent space. Is this something I could do with player of games? No, but that's, that's arguably the limitation number two, I think the biggest being the biggest thing is right now the the large, large beliefs, belief space. But the second one is we currently need the model of the environment. And muse zero doesn't even know you will need it. So we can think of player of games is running behind the Alpha zero Alpha zero lineage and trying to generalize things, but we are still looking behind in that regard. And maybe a more more conceptual question here in these in these entire game trees and so on, you know, for example, in Scotland yard, I don't know where Mr. x is, but Mr. x's movements are kind of deterministic, right? Mr. if Mr. x uses a taxi to get from 49 to 48. Mr. x is now at 48. However, in poker, for example, if I bet something, there will and my opponent calls the flop will reveal like random cards. How does this and this is different from me not knowing what my opponent's cards are, right? It's, it's sort of pure randomness within the game. Is that something that makes things very complicated? Or is the complicated part? Like how do you deal with stochasticity and with randomness in games, which is also something that doesn't exist in chess? That that part is actually quite easy. It's simply baked in into into a model. And that's, that's pretty much it. Okay, so you can you can sort of condition on previous information and the model will compute whatever expected value of of any future cards that could be drawn in like flop and turn and river. You can think of it as basically having you just draw the search tree at the beginning and simply one of those nodes you can think of as as some chance actor playing and you have simply a fixed policy in that node and a lot of lot of actions. That's it. So when you expand the search tree, do you need to expand once for every possible, let's say flop combination there is? Yes. Okay, that that is a lot of combinations, right? Or you can or you can substitute like if you are smart about it, you can again use a neural network. Yeah, okay. Do you do you think humans because in in Alpha zero, you can sort of think that you do the same internally, right? You kind of you kind of think ahead and until some depth and you say, okay, here, I guess, and a little bit. Do you think player of games or in general, these these algorithms with imperfect information is also a little bit like like humans do it. It seems vague that I go and I kind of go through all the different flop combinations there could be. Or do you do you think there is a fundamental difference between how humans tackle these problems and how these algorithms do? I would. So I would say we would both agree that in Scotland, they are you probably do the same, right? Yeah, like looking forward, like what if I go here? What if the opponent goes there? And then you do this like search forward as you are thinking about the beliefs of the opponent. Yeah. So in Scotland, I would say yes. In poker, it's simply complicated by the fact that suddenly the belief space is big. You like for humans, even 1000 is probably too much. And yeah, I did like probably humans use some like gender representation there already. I don't know. Cool. And what is next in this line? I mean, now you've, you know, you've built like a big unifying algorithm that can tackle any sort of game as long as it like has a simulator. What and you said it's probably not possible to go without a simulator. So what's next? Like, it seems like, you know, you've achieved kind of unification. Where do you go from here? I think the most natural path is to remove the constraints that we just discussed, right? This is going to fall apart if there's a big belief space. And it still needs a model. And I think this is something we probably want to play with play with next like, yeah, like, we like making algorithms that are truly general. I think is a big step in this direction. But it's not to say that we are finished. And is so do you think if this line of work continues, it would be an algorithm that at some point could be thrown at pretty much any problem, like Atari and like, but even beyond reinforcement learning, right? Question answering, visual classification, what not, or even robots, and so on. Or do you think that is kind of a very different line of work? I mean, I did use I did work on question answering and congeneration before. So yes, sorry, so on high level, this is certainly the dream, right? Like, not just of the team who work on this, but quite a few smart people in deep mind, like try to make something that's truly, truly general. You don't really care. Well, the algorithm doesn't really care what environment you throw it into, you just like throw it there and say, okay, learn. So that's, that's, that's the direction we are going if player games can walk all the way there, or if some of the ideas will be simply used in other approaches, we shall see. Cool. Excellent. Well, in this case, Martin Schmidt, thank you so much for being here. This this was way way I promise to everyone, this was way better if than if I had done this myself. So thanks a lot for for joining us. This was really awesome. Thank you for having me. This was fun. Thanks.
 Hello everyone, today is a special day. I'm here, as you can see, not alone, not by myself as usual.
 I'm joined by Martin Schmidt, who is the first author of the paper called Player of Games.
 This is joint work with others by DeepMind and I have to say it's a very in-depth paper.
 It presents an algorithm called Player of Games that is sort of a unified algorithm to play all
 sorts of games. This starts at things like chess and go, which you might know from AlphaZero,
 but it goes beyond. It goes to things like poker and Scotland Yard, which I found really interesting
 that it appears here. But sort of the common denominator is that these new games, they have
 hidden information. So other than chess or go in Scotland Yard, you don't know where Mr. X is
 hiding. In poker, you have no clue what cards the other players hold. So you can't just look
 at the table and poker and decide what's the best thing to do because you don't know a lot of things.
 Same in Scotland Yard. There have been algorithms for poker, right? There have been algorithms for
 Scotland Yard, but they were always a bit tailored to sort of the specifics of the games. Player of
 Games combines a large set of techniques. And these techniques are things like, let's do search. So
 as we play the game, we do local search. We sort of invest some computation at inference time to
 tell us what the best possible move is. But we don't want to search throughout all the game
 because these game trees, they just get very big. So that's the part that comes in from AlphaZero
 a little bit. But then the other part with the unknown information that is coming in mostly from
 the from algorithms like counterfactual regret minimization, and so on. But yeah, the counterfactual
 regret minimization, if I understand these correctly, they were sort of solvers, like they
 either solved a complete game or they didn't, right? You'd have to like traverse the whole game. And
 then at the end, you knew, okay, in this situation, I need to do this and so on. And yeah, this, I was
 very excited when I saw this paper. And then I tried to read it. And it was, it was, it was,
 I have to say it was dense. And I'm very happy to have Martin here today, to guide us a little bit
 through the paper. So Martin, welcome. Thank you very much for being here.
 Hey, I'm happy to be here. Was it a sort of a good description of what I said so far about player of
 games? Oh, yes, very, very, very much so. If you could summarize sort of the main components
 of this algorithm. So this is a single algorithm that I can train on many, many games. What is
 the set of games I can train it on? So the currently we use, we use four games, the games
 that you mentioned, we have, we have chess, we have go, we have Scotlandia, which I find
 as a very cool and fun game. And we have, we have no limit poker. So that it's just to show
 the generality of it, because this is all about the generality. That's why we pick like two perfect
 and two imperfect information games. Yeah. So currently, it should be able to handle, handle
 most perfect and imperfect information games as it plans. So from scratch from self play, just like
 Alpha Alpha Zero does. There are some, some, some limitations for games that this can handle. And
 we can, it's, it's best to understand the limitations only after we understand a bit more about the
 algorithm itself. Yeah. So the algorithm itself is composed of many parts, but the, the central
 concepts here, I think are, and that's what people, I think people kind of know what Alpha Zero does,
 right? It, it uses self play and it searches, it searches a game tree to a certain depth, right?
 So, so it, in these games, we usually have like some sort of a state, right? And then we have
 various different actions that we could take in that state and every action leads to a next state
 and so on. And we have various different actions we could take right here and every action leads
 to a next state. And you can quickly see how this explodes, right? So what, what Alpha Zero and all
 these search algorithms do, they do this kind of limited depth search, right? They look maybe one or
 two moves ahead, but at some point they say, okay, no further. We can't afford to compute all of this
 tree. And that's why at a certain depth or after a certain time, they say, okay, here we cut off
 and we use like a neural network to tell us how good this node is. Even though we're not at the
 end of the game where we would either win or lose, we could still have a neural network that sort of
 predicts this node is, is very good for you or this node is very bad for you. And that's, that's
 essentially Alpha Alpha Zero in a nutshell, let's say uses self play, uses this tree search at a
 certain depth. It simply asks the neural network. Now what's the, what's the problem when you have
 imperfect information? How does, how does this change? Okay. I know that's, that's, that's the,
 that's the right question. Unfortunately, we probably spend quite some time to understand
 the intuition of it. Right. But even for Alpha Zero, it's, it's good to step back and see where
 it came from. It's not, it's not that Alpha Zero introduced search for say perfect information
 tips, right? Search has been here since 1950s, like first, first algorithm for, algorithms for chess
 did combination of search and some value functions. Alpha Zero is amazing in the sense that it learns
 those value functions that you just described for self play. And it's also really, really smart about
 how it's going to expand its search tree. It's not like it's going to always look two steps,
 steps ahead. It's very smart about building, building this tree that goes deep where they need
 to need it to go deep. But it still has those components, which these components are simply
 having some search tree that it ideally expands as it thinks about a policy in the search tree,
 and then using some value function at the, at the end of the search tree.
 Yeah, that is, that is one of the, one of the hallmarks of Alpha Zero. I think that, for example,
 in Go, you have so many actions, even at step one, right? If you were to consider only like
 even three steps ahead or so, this would just blow your computation budget. But as you can see,
 in Alpha Zero, it sort of, it sort of always starts from the root, and then it kind of goes down
 one of these branches that it has already explored a little bit. And in every new iteration, it
 re-decides which direction it should investigate. And that's a combination of sort of what the
 neural network says, but also how often it's been, it's explored something. So it says, you know,
 like this direction is very promising, but I've explored it a lot already, so now I'll go,
 I'll go a different branch or so. And then at the end, it always goes, gets to a leaf node that it
 hasn't expanded yet, right? And at that point, it asks the neural network, okay, you know, what's,
 what's my policy here? What's my value? And then it prepares sort of the next iteration that it
 could expand it even more. And so over time, it builds this very targeted plan. So the neural
 networks guide the tree search, as you say, that's very, very cool. And in imperfect information
 games, that is, yeah, that is different, right? Yeah, so it's somewhat different, but we still
 wanted to have exactly what we just described. This is like why Alpha Zero works so well, and we
 still wanted it. So on a high level, you can think of playoff games as combining, combining Alpha Zero
 and DeepStack, which if you were to Google DeepStack, it was the first AI to beat professional
 players in no limit poker. And it already introduced some of the ingredients that we will see in this
 paper, which is it introduced this notion of local search in poker and these value functions.
 And playoff games is really just putting together Alpha Zero in DeepStack into a single big unified
 algorithm. So let's maybe start with the component that you just talked about, which is
 value function. And the value function, if we get to a point where we understand value function
 in playoff games, say it's then you understand like 60 to 80% of the algorithm and complexity
 that imperfect information brings. So value function, if you think about how to use it,
 exactly as you said, rather than searching all the way to the end of the game, because it would be
 like way too long of a search, you just trumpet your search and use value function as a substitute
 for continued search. And that's how you use it. But what it really does, it maps some sub
 problem that you are thinking of to a game value of that sub problem or sub game. In chess or in
 Go, it's really easy to think about what it really is. You get to a new board, chess or Go board,
 and the value function ideally should tell you, hey, this is the value of this sub game. What
 it really means is what would be the outcome if two optimal players were to continue playing this
 game forward, right? So that's all the value functions do. And the same thing they do if you
 try to generalize them into imperfect information games, except that suddenly this notion of sub
 game and sub problem gets way more complicated. Yeah, so this basis on this notion of information
 states and sort of public beliefs about things. So on the left here, you've tried to show this
 in a diagram. And I think the notion is when I come to a poker table, I only see what's called
 the public state, right? I see and actually, if I come to a poker table and I observe a hand with
 all of its history, right? That is the public state. So I know, you know, who bet how much in
 which round and so on who acted how, but I don't see people's cards. So there could be many
 different cards that people hold. And some might be impossible just from the rules of the game,
 you know, maybe not in poker, but you know, in Scotland yard, you have this over here,
 there are certain locations, this Mr. X can be. And we want to assign probabilities to each one
 of them, right? If we knew if we knew where Mr. X was, the game would be easy, right? But since we
 don't know, we must estimate and I think that's also something you highlight in the paper,
 an interesting property of these games is that if I am Mr. X, or if I play poker, I have to
 not be deterministic, right? Otherwise, the game would be very easy for my opponents. If that's in
 poker, usually, you know, people they look at their cards, they go, and then they like bet
 everything they have. And you know, immediately know which hand they have if they don't also do
 the same thing with other other whole cards, or if they don't randomize a bit. So necessarily,
 other than, let's say in chess, the optimal strategy is kind of a distribution over actions.
 And you have to sort of randomize that in order to almost a bit hide your, your, your private state.
 So what we what we see are these public states, right? And what we can estimate is these things,
 which are called the ranges. So these are distributions over what private states the
 players could hold. And the thing the difficulty in this tree search comes from the fact that
 you can only go from a public state, yet you need to consider all the possibilities of the
 private states. So you can't just say this is the situation, you have to sort of consider
 all of them at the same time, right?
 Yes, exactly. That's, that's what you basically need in order to generalize those sub games or
 sub programs to improve information, right? It's not hard to hard to see that all perfect
 information games are just a special case where you have just a single single possible state for
 for for the player, right? Like a poker, you just talk about poker and public state states,
 and that's a that's a that's a perfect example, right?
 Like a sub program in poker, it's it makes little to no sense to say what's the value,
 what's the value of a sub game or sub program in a poker where I hold a pair of aces that's
 pretty much ill defined, ill defined sub game. What we what you need to do is given a given a
 public state, which is, as you say, I come to a table, I see everything that I could have observed
 as a public observer. So that's that's that's basically my state. But given this state, given
 this observation, there's a lot of possible individual individual states of the of the game
 that are consistent with this observation. And this simply correspond to all the different cards
 the players could be holding. And sub game is simply defined by by combination of this public
 state, which is the thing I get to observe as a public observer. And then I can see that
 observer and a distribution over all the possible private states that could be happening right now.
 And given this distribution on top, this simply defines a well defined sub game. And given this
 well defined sub game, I can suddenly ask questions of, well, what would what would be the
 values of this sub program given that they all the agents play the sub game optimally, just,
 just as you in chess or go? Yeah, I we used to we used to play poker a lot in like high school.
 And this was frequently you try to not try to guess what hands your opponent have, but you try
 to guess you know what their ranges right. So you consider like, okay, it's often going to be these
 cards, it's less often going to be these cards. I think that mirrors very much the reasoning that
 that people actually have in these things. And now given given this you at the one of the core
 things here is this neural network that is supposed to tell us what the values of the sub game is,
 right. And this, as you said, it gets us an input description of the public state. And it also gets
 as an input, your beliefs about what distribute like your beliefs about the ranges of the players,
 so what their private information could be and how often and if I remember correctly,
 these ranges, they're just a result of their strategies, right. If you know the strategies
 of the players, then you can calculate what their ranges are. Because if the strategy is I always
 bet high when I have aces, then if the player bet high, then aces are quite likely, you put all of
 this into a neural network, and the neural network gives you policies, which is understandable, it's
 how would a player act in a given situation. This is also what AlphaZero gives you. But then you have
 these counterfactual values. And this is a bit of a new term that only appears in, I think in imperfect
 information games, what is a counterfactual value? Right. So in this case, this value function very
 much is analogical to AlphaZero in the sense that you have values and policy or policy for a sub game.
 And we use them in very similar way. Except as we just described a sub game is,
 there's many possible states the game or the players could be in given a public state
 sub game or public sub game. And the value function given this sub game outputs not just a single value
 that says, hey, value of this sub game is five, it actually outputs a single value for all the possible
 player states that are possible given the sub game. So in poker, say I could be holding
 thousand different hand combinations in holding poker. So the network will tell me, hey, in this
 sub game, if you were to hold this particular pair of hands, this is the value and it will tell me
 such value for all the possible states I could be in. Yeah. Okay. And the neural network,
 how is it built to output? Does it have like one, let's say one output head? So does it output like
 a thousand dimensional vector one entry for each? Okay. So is it fair to say that your algorithm
 would struggle with games where the possible private states are huge? That's yeah, that's the
 this is brilliant. This is exactly why I said it will be nicer to understand the limitations once
 we get a bit deeper into the algorithm. And this is exactly the main limitation that we currently
 have because in some games, this just explodes. Yeah, I see. Okay. And you have this network and
 you train it in some way via via self play. And now we get to the part where you generalize this
 search procedure, right? And let me see. Oh, this is here. So this search procedure, as we said in
 in alpha, again, in alpha zero, you have something like you're at some state in the game, right?
 You've played until this state. And what you do is you do this search and you use an internal like
 simulator to do the search. This is at inference time. So what you do is you consider all your
 actions, you choose on one by given the neural networks output and the current search statistics.
 You go here, you ask the neural network, well, what's my value here, you expand that node.
 And then you start again. And then the next iteration, you start again from the root,
 you expand maybe the same or maybe another action, it depends. But let's say it's the same right here.
 If it's already expanded, you go further down the tree. And you would you would sort of you would
 make many iterations, let's say 50 iterations or something like this. In every iteration,
 you'd go down the tree, and you find a node that you haven't expanded yet. And you'd expand that
 node, right? In in in player of games, this is quite a bit more intricate, right? As as we also
 have many iterations, but within each iteration, we have to do a lot more work in order to actually
 in order to actually deal with with this uncertainty. So could you describe a little
 bit how your search algorithm works? Yes, happy to. So when we said at the beginning that
 player of games is a hybrid of deep stack and alpha zero, search algorithm is a perfect example
 of of this being a hybrid. So what deep stack already introduced is it, it had a fixed search
 tree. So you are poker players. So you what it really did is it search all the way through a
 single single betting ground. And it used value functions at the end of the round. And it ran this
 kind of actual regret minimization, which we might come back later to. But you can think of it simply
 as some some policy improvement algorithm given a fixed search. It would iterate and improve the
 policy and as it was walking up and down the tree and finding a good policy, it would use the value
 function at the end of the search tree, the very same value function that we just talked about.
 Now, player of games, it's this this smart idea of alpha zero, where it also tries to dynamically
 expand the search tree or didn't have enough fixed surgery. And the way it does we simply see
 intertwined two phases where we in one phase, given the sample given some surgery, we try to
 improve the policy within the surgery. And there's a second phase where it simply tries to expand
 just like alpha zero does using the same say PUCB PUCB formula, we try to expand the search
 tree where we think we need to expand it. And then we simply go back and forth with you like an
 expand the tree, improve the policy, expand the tree, improve the policy.
 Yeah, so this is built on an algorithm that is used that called counterfactual regret minimization.
 And this is an this is if you were to just apply a counterfactual regret minimization,
 this is a solver, like I give it a game description, and it just it will expand the
 entire game tree every state there is in the game. And it will just sort of go from node to node
 in this tree and improve the policy of both players, right. And it just does this for many,
 many iterations, it improves here, here, here, everywhere in the game tree, until the whole
 game tree is approximately optimal. And the biggest game that has been solved so far,
 if you describe this in the paper is limit, limit heads uphold them. Is that correct? Fixed?
 Yes, hold them. Yeah, that's, that's actually a solved game.
 Yes, it was done a few years ago by the by the computer research group at the University of
 Alberta, led by Michael Bowling, and it's still as far as I know, the largest game to be solved.
 And you use the word solver, which is a perfect, perfect name, really. And like the way I think
 about the solver is you give me some small or medium sized game that I can fit into like a big
 table on my computer. And by solving it means simply find a policy for all the possible states
 in a game. It's easy to see that it's like, I mean, people do know how to do it in say,
 tic tac toe or small, small games, right. And if you were to fit chess on your computer, then again,
 it's not hard to see that you could just solve it given the algorithms that people are familiar with.
 The thing is, even if you have a really, really small information game, you do have to use
 algorithms that that can handle imperfect information games. Often people just use
 algorithms that they like, say, I don't know, like policy gradient methods, Q learning or whatever.
 And if you just run it on imperfect information game, it just doesn't find a good policy.
 Yeah, I think the I mean, intuitively, it's a bit like if I start in some situation in chess,
 and I make some moves, I have I have still like that original state is still the same, right,
 I can I can look back, I come from there. But if I'm in poker, and I'm in some state,
 and I make some moves, that changes kind of the past, right? Because I look at, you know, maybe
 you're my opponent in poker, I look at what you do. And that changes my beliefs about what you what
 cards you had back in the past. Then I go back and I'm like, Oh, okay, you did this and this. So you
 can't you can't, I don't think you you will you're holding, you know, a king and an ace, given that
 you've done something in the future. And I think this, the fact that your future actions change
 the past, that's what, in my opinion, makes this so much more intriguing and complicated.
 So on the left side here, I think this is the this is you have a search a local search tree,
 right? You it's expanded until some depth at that depth, you asked the neural network for,
 you know, summarization of whatever happens below. And within that tree, you run now this
 counterfactual regret minimization or something akin to it, and you simply want to find the best
 policy within that tree, which is more complicated in alpha zero, I just visit every node once right,
 because the future doesn't change the past. Once I computed a node, I only expand things below it,
 that never changes that node. However, in imperfect information games, right, if I change
 something below, all of a sudden, the the past changes, so I need to sort of update and converge
 the whole tree. And then once you've done this for a number of steps, on the right side, then you
 add a new node by essentially doing what alpha zero does, you go to a leaf node, you choose some
 action, right in some information state that passes, and you perform that action, and that expands
 actually one more node. Is that you know, this is this is excellent. And the the property that you
 just described, like the future change in the past, that that is also something that makes
 search in particular, so much more complicated, right? Because there's you can figure with a
 two step process, if you were to just solve solve some game, you will just solve it, even that is
 more complicated, because of what we just described, but you could do it there. There's ways to solve
 solve imperfect information games. But we are doing search here. And the property that you talk about
 makes search so much more complicated. And the reason being is in imperfect information games,
 you cannot just glue together optimal policies, and hope that the resulting policy for the full
 game will be optimal. And that is something that many search algorithms just rely on. And it
 simply holds in perfect information games. So if you were to like, pick any optimal policy in any
 any any state and just put them together, this is an this is an optimal policy in imperfect information
 games. It does not hold because of exactly what we just described. But then how can you even do
 search at all if search is all about like local reason, right? You reason locally, you have to
 somehow need to make sure that the resulting policy for the full game is still optimal.
 Yeah, it's it's it's interesting. So essentially, for every step that Alpha Zero does, where it
 expands a new node, you also expand a new node, but then you have to like, get the entire tree in
 order again. So you expand the new node, and then you have to do the whole update of the whole tree
 for a bunch of iterations before you can expand another one, such that everything like stays
 consistent. Yeah, okay. That's, I mean, this this, it gives a bit of an impression of why this is
 much more, much more complex, right? Yes. So this is this is essentially at inference time,
 we do this search, right? We do the search. And now comes the time when we actually need to train
 this. So we have the ingredients. Now we have the search algorithm, we have the neural network.
 And now we need to train it. And you also have, you have a method, or various methods. And maybe
 you want to describe it yourself a little bit, because this is the part where I stumbled a little.
 So yeah, yeah, I will start to do it on very high level. So the idea is, again, we want it to
 take the self play style method from AlphaZero, so that you just throw the algorithm into a game,
 and it improves as the as the as it plays, and it gets better and better. And what it really means
 is you are improving your your value and policy, right? The network that we that we just discussed.
 And the on a high level, since you are using your value function in your search, you call basically
 call your neural network with some inputs, some states, public states, some beliefs. And this,
 this figure, this idea of queries is simply we call every single time we call a network,
 we call this a query, we are querying a network for some value over some game. So we store this
 we store this couple of public state and beliefs. And then we go through all this all those queries,
 and we simply try to basically improve the network on the states and the syringes that
 the network has been queried, because this is probably what's important because that's what
 occurred during the self play. So you collect the train is similar to AlphaZero, as you say,
 you collect the training set as you go. So the training set for the next iteration is whatever
 the network had to do during this iteration. So it's not just a random sample of states.
 And you train in the same manner as AlphaZero, you train to predict your own future outputs,
 is that approximate? So if let's let's distinguish if, like one or two or three steps in the future,
 you actually win or lose the game, you can train on your reward of the game. But AlphaZero also,
 if it doesn't win or lose the game in the next step or so, it tries to predict its own output.
 So it tries to improve that way using TD lambda. You here have TD one, right? So your targets,
 what do you target? What do you give the network as labels? So okay, so this is slightly more
 complicated here in the sense that each query basically defines you something, right? It's a
 public state and energies. And given a sub game, the ideal target for your neural network would be
 simply to solve the game, right? That's the ground truth that you want your neural network to
 learn or like then to work too. So rather than solving directly, because again, these sub games
 will still be way too big as they occur during the gameplay, we do like a small, small solver,
 where we also substitute the full solver with a small search. So rather than fully solving a game,
 we use the same method to basically do a search. And the outcome of the search, basically a small
 solver is what is the target. Okay, so you do the same thing as you do during inference when
 you actually want to make a move. So during that inference, you're going to make some queries to
 the network, you take these queries, and these I think here are the red dots, right? Exactly.
 So during maybe this has battery again. So during the inference, you make you do these queries,
 you store them in this in this buffer. And these now act as the root nodes for yet another search,
 which is exactly the same as the previous search, right? And so you you sort of rely on the fact
 that this search procedure can give you a better output than the neural network itself, right?
 Yes. Right. The query here, the neural network will output some value, like the value is eight,
 or one value for each for each information state. But you, I think the whole algorithm is,
 and that's of course, the reason we do search in the first place is that doing search gives you a
 better estimate than just using the neural network at the start. So doing search, and then asking
 the neural network further down the line gives you a better estimate. And yeah, it makes sense. You
 start at wherever you ask the neural network, you use local search to get a better value,
 doesn't need a perfect one, just a better one. And then you train the neural network to predict
 the result of the search. That's exactly one would hope though, that after a while, you know,
 if I do this again, and again, and again, at the end, I wouldn't even have to ask the neural
 network anymore. Sorry, I wouldn't even have to do search anymore during inference. Is that something
 you have you have you tried not even doing search just using the neural network that the policy
 output of the neural network during inference? Is that something that generally works? Because,
 you know, I train it to predict the output of the search. So technically, let's say it should
 it should kind of learn it, no? Yes, the same the same way you simply could just use the same policy
 network in AlphaZero and let it play chess, right? You can do it and people have have done it. It
 is still quite good chess, but it's far, far below the full strength of search. So yes,
 at the end of the day, even the policy network is quite good, but it's not as good.
 Okay. Yeah, I mean, it's just it shows a little bit that the search is in fact,
 in fact, really necessary, right? Yeah, so I think we're almost getting
 already to the sort of results. Wait, would you would you maybe summarize the results a little
 bit? I think if people are super interested, they may go into into the paper and into the tables.
 But maybe you can just summarize a little bit of the results you compared against AlphaZero in
 perfect information games, you compared against dedicated algorithms like like slombot in poker,
 and you even compared against like a dedicated AI for Scotland yard. What were generally the results
 for you? So yes, so so in general, the results are that the algorithm is all about generality,
 which is this is not as strong as AlphaZero in perfect information games where AlphaZero was
 designed to shine, right? So this this very much is trying to be a general rather than being the
 best chess or the best poker poker poker agent in the world. It's just trying to be really,
 really good in all of them at once. What is the diff? So if if a perfect information game is just
 a special case of an imperfect information game, right? What is then the difference between
 player of games and AlphaZero? Like, why couldn't it reach the same performance?
 So on paper, it could except that, for example, the policy improvement algorithm that we use,
 the counterfactual, we get minimization, right? It has to be also good able to handle imperfect
 information games. That's why it's not going to convert so nicely and quickly as as algorithm
 design design for perfect info. So the fact that you expect sometimes to see an imperfect
 information game, would it be fair? Would you estimate that if you just input more resources,
 input more computation time that it would actually reach the levels of AlphaZero?
 I don't think it's necessarily I mean, on paper, all of these would eventually converge.
 Right. Everything works on paper in in delimiter. In practice, AlphaZero and MCTS is probably
 always going to be ahead. But we don't really care. Right. Like, if I would be happy with a
 single algorithm for everything that's that's better in humans. I don't care if it's better by
 like a little bit or by a billion. Yeah. And then in in in poker here, you compared against Slumbot,
 which is you say that the best open source or best available poker bot to date. And this is no limit
 poker now. Right. This is this is way too big of a game to solve. And I think the other ones
 is you you simply compare to the numbers from their papers. Is that
 the do you mean for a slum bot or for Scotland that we're talking about poker? Oh, sorry. Yeah,
 let's let's talk about poker for a while. So the the player of games here gains what is this seven
 millibig blinds per per hand? Yeah, over slum bot. Yeah, again, like we we we could have beaten
 slum bot by by a lot more. Yeah, just like decided, oh, this is good enough to like to put into a
 paper, we can come back to it later. Like, as you know, it very much depends on how much time you
 spend tuning the network architecture and how for how long to train this is what this is just to show,
 hey, there's already an algorithm that can do all of these games and it still plays them really,
 really well. Yeah. And your neural network, just to say it's a bunch of like feed forward layers,
 correct? Like, it's not a complicated thing. So for poker, it for poker, it's just a feed forward
 network for chess and go. We do we try to mirror some of the older AlphaZero architectures. Yeah.
 Okay, so and here on the right side, you have Pym Bot, which is the Scotland Yard specific,
 but for people, maybe people don't. Does anyone not know what Scotland Yard is? Maybe you can
 describe 10 seconds what Scotland Yard even is as a game. It's somewhere. Yeah, there's a
 figure maybe, right? There is this figure, right? Right. Yeah, there's no point explaining the rules
 in detail, but on a high level, there's a graph, you are trying to chase down the chase down a
 stone that's called Mr. X, you have five detectives that are trying to chase the stone down. The trick
 is the stone, the Mr. X that you are trying to chase down is only partially observable. That's
 what makes it imperfect information. And you have to basically reason about states where he could be
 hiding and form some beliefs about his state and trying to chase him down. So yeah, and yeah, I
 guess that's all people need to know. You can spend like funny tickets on taxi rides and
 various methods of transport. And then every 10 turns or so Mr. X has to reveal
 their position. And that's how you sort of form a belief about where Mr. X could be given what
 actions Mr. X took. So this is quite a specific game. So it seems to me like a dedicated algorithm
 could do very, very well, again, in this game, because it could exploit various aspects of the
 game, you could hard code in various various things the AI could abuse. And here we see a graph of
 the win rate of player of games against what's on the x axis here, this is number of search
 iterations. So pinbot is a local search algorithm as well. Yes, it's a it's a it's a variant of
 MCTS. And this is to show regardless of how much time or search we give the MCTS, the hard code
 hand tune algorithm, even if it gets like a billion or something called search iterations,
 it's still behind alpha zero because it's using this general self play learning method.
 Yeah, so this is this will be I guess the final win rate is here like at 55% or something like
 this. And that is with a huge number of iterations for for pinbot. Yes, and we'll play our games is
 using only like 400 iterations on our site. So yeah, as you can see, as you can see, the
 regardless of the scale, we converge to a better policy. And you do you would attribute that to
 the use of self play to improve the strategies. It's the it's a combination of this and also the
 fact that player of games is built on some some on some methods like later in the appendix, if
 people are curious, they can open appendix, we show that on small games we were we can exactly
 measure how close to an optimal policy the our resulting search policy is we get closer and
 closer as the time goes. So basically, we are only limited by the by the power of neural networks.
 And we have some guarantees that we can get to an optimal policy. Other methods that are based on
 MCTS, they they are not guaranteed to converge even on small games. So there's there's there's
 there's also the limit of the of the fact that these methods are not sound.
 And just to get an idea of the scale of like we saw, you know, poker, Scotland yard, here we have
 the the chess and go and so on. Can you give us a number of just how many how many GP TP, whatever
 use do I need to run for how long to get anywhere close to what you did? I see. So I think the
 easiest for us was poker that like people probably can train on a few few GPUs.
 The by far the hardest is is go where we used a lot of a lot of GPUs. But that was simply because
 we we had them available. Yeah, I get okay. And you you did in the paper say that for comparison
 reasons you use sort of the same amount of compute as Alpha Zero did as well. That was that was
 tricky. I'd like it's like, because we do not want to claim that this is this is now state of the art
 chess agent and like there there we don't have to do all the proper and hard measurements, right?
 Then you have to use clock time. And suddenly if you use clock time, you have to argue that use
 the same hardware and everything gets gets more tricky. And he would just say, well, we use the
 we call the network as often as Alpha Zero did. So it should be roughly the same, but like we don't
 claim to be stronger. Okay, I mean, that's a I think community appreciates sort of fair comparison
 instead of every every paper having the new best state of the art, especially in RL, like it seems
 it seems clear just from the graphs here, like just from the lines, it seems clear, you can just
 invest more compute and get better. And that's what we also saw with Alpha Zero, like it used to be
 slightly superhuman. And now it's like, you know, no human not like not all humans together even
 will ever match Alpha Zero in in any of these games, which is crazy. Yeah, exactly. Do you have
 a bit of a demonstration ready? You told me of of of the player of games playing Scotland yard.
 So we can kind of see what's going on. Yeah, let me see if it's still still working. It was
 working this morning. It was we never plan to show it externally. We it was designed for our
 debugging purposes, but it would be a fun demo just so that people who are not familiar with
 Scotland yard maybe get some intuition about the game. Okay, so hopefully you can see this.
 Yeah. And the let me very quickly explain what is what is this about. I am now playing as Mr. X,
 which is this black color in here. And I can move all and all on on this graph basically walk
 walk in the edges. And as you were talking about those taxes and cubes, you can see that the edges
 have different colors. So all of these are yellow, but this this guy is blue. And they correspond to
 to different meaning of transportation that I get to use, say yellow stands for taxi taxi, I think,
 and blue stands for bus. Now, detectives do not get to see where I am, but they do get to see
 which color color details. So right now I'm in here and say I want to go through 49.
 And I want to use taxi together. So yeah, hopefully, like we have been talking for a while,
 so maybe maybe it's not alive anymore. But yeah, probably to it died.
 You have scaled to zero proper engineering. Nice.
 Yes. So yeah, it doesn't work right now. But at least people can get an idea of what would happen.
 Maybe. Yeah. So you'd need to you'd need to pretty quickly kind of reason. And the longer you don't
 see Mr. x, the more sort of fuzzy your idea gets of where Mr. x is, do you do you visualize
 sort of this distribution, the belief distribution of where Mr. x is or for debugging?
 Or we did it's I don't think it's it's turned on right now. But that's exactly what we tried to do
 at some at some point. Yeah. And did you see did you observe this that's the longer they didn't see
 Mr. x the more kind of spread out, the more unsure they become. Is that something you can
 clearly observe? Or is that something you just feel as a human? Oh, yes. And it was actually
 really, really fun to see. Yeah, crazy. And so the one improvement, let's say, or one follow up to
 Alpha zero was the muse zero algorithm, which, which the crucial difference is Alpha zero,
 you need sort of the simulator, you need to be able to simulate a lot of games. Internally,
 you need to know what happens when I do some action, what kind of state results from that.
 And muse zero alleviated this by sort of going to the latent space state and training everything in
 latent space. Is this something I could do with player of games? No, but that's, that's arguably
 the limitation number two, I think the biggest being the biggest thing is right now the the
 large, large beliefs, belief space. But the second one is we currently need the model of the
 environment. And muse zero doesn't even know you will need it. So we can think of player of games
 is running behind the Alpha zero Alpha zero lineage and trying to generalize things, but
 we are still looking behind in that regard. And maybe a more more conceptual question here in
 these in these entire game trees and so on, you know, for example, in Scotland yard, I don't know
 where Mr. x is, but Mr. x's movements are kind of deterministic, right? Mr. if Mr. x uses a taxi to
 get from 49 to 48. Mr. x is now at 48. However, in poker, for example, if I bet something, there
 will and my opponent calls the flop will reveal like random cards. How does this and this is
 different from me not knowing what my opponent's cards are, right? It's, it's sort of pure
 randomness within the game. Is that something that makes things very complicated? Or is the
 complicated part? Like how do you deal with stochasticity and with randomness in games,
 which is also something that doesn't exist in chess? That that part is actually quite easy.
 It's simply baked in into into a model. And that's, that's pretty much it. Okay, so you can you can
 sort of condition on previous information and the model will compute whatever expected value
 of of any future cards that could be drawn in like flop and turn and river. You can think of it as
 basically having you just draw the search tree at the beginning and simply one of those nodes you
 can think of as as some chance actor playing and you have simply a fixed policy in that node and
 a lot of lot of actions. That's it. So when you expand the search tree, do you need to expand
 once for every possible, let's say flop combination there is? Yes. Okay, that that is a lot of
 combinations, right? Or you can or you can substitute like if you are smart about it,
 you can again use a neural network. Yeah, okay. Do you do you think humans because in in Alpha
 zero, you can sort of think that you do the same internally, right? You kind of you kind of think
 ahead and until some depth and you say, okay, here, I guess, and a little bit. Do you think
 player of games or in general, these these algorithms with imperfect information is also
 a little bit like like humans do it. It seems vague that I go and I kind of go through all the
 different flop combinations there could be. Or do you do you think there is a fundamental
 difference between how humans tackle these problems and how these algorithms do? I would.
 So I would say we would both agree that in Scotland, they are you probably do the same,
 right? Yeah, like looking forward, like what if I go here? What if the opponent goes there? And then
 you do this like search forward as you are thinking about the beliefs of the opponent.
 Yeah. So in Scotland, I would say yes. In poker, it's simply complicated by the fact that suddenly
 the belief space is big. You like for humans, even 1000 is probably too much. And yeah, I did
 like probably humans use some like gender representation there already. I don't know.
 Cool. And what is next in this line? I mean, now you've, you know, you've built like a big
 unifying algorithm that can tackle any sort of game as long as it like has a simulator.
 What and you said it's probably not possible to go without a simulator. So what's next?
 Like, it seems like, you know, you've achieved kind of unification. Where do you go from here?
 I think the most natural path is to remove the constraints that we just discussed, right? This
 is going to fall apart if there's a big belief space. And it still needs a model. And I think
 this is something we probably want to play with play with next like, yeah, like, we like making
 algorithms that are truly general. I think is a big step in this direction. But it's not to say
 that we are finished. And is so do you think if this line of work continues, it would be an
 algorithm that at some point could be thrown at pretty much any problem, like Atari and like, but
 even beyond reinforcement learning, right? Question answering, visual classification, what not, or
 even robots, and so on. Or do you think that is kind of a very different line of work?
 I mean, I did use I did work on question answering and congeneration before. So yes, sorry, so on
 high level, this is certainly the dream, right? Like, not just of the team who work on this, but
 quite a few smart people in deep mind, like try to make something that's truly, truly general.
 You don't really care. Well, the algorithm doesn't really care what environment you throw it into,
 you just like throw it there and say, okay, learn. So that's, that's, that's the direction we are
 going if player games can walk all the way there, or if some of the ideas will be simply used in
 other approaches, we shall see. Cool. Excellent. Well, in this case, Martin Schmidt, thank you so
 much for being here. This this was way way I promise to everyone, this was way better if than
 if I had done this myself. So thanks a lot for for joining us. This was really awesome.
 Thank you for having me. This was fun. Thanks.