This is a great advancement, and will be even more so if you can beat Lee Sedol.
There are two interesting areas in computer game playing that I have not seem much research on. I'm curious if your group or anyone you know have looked into either of these.
1. How to play well at a level below full strength. In chess, for instance, it is no fun for most humans to play Stockfish or Komodo (the two strongest chess programs), because those programs will completely stomp them. It is most fun for a human to play someone around their own level. Most chess programs intended for playing (as opposed to just for analysis) let you set what level you want to play, but the results feel unnatural.
What I mean by unnatural is that when a human who is around, say, a 1800 USCF rating asks a program to play at such a level, what typically happens is that the program plays most moves as if it were a super-GM, with a few terrible moves tossed in. A real 1800 will be more steady. He won't make any super-GM moves, but also won't make a lot of terrible moves.
2. How to explain to humans why a move is good. When I have Stockfish analyze a chess game, it can tell me that one move is better than another, but I often cannot figure out why. For instance, suppose it says that I should trade a knight for an enemy bishop. A human GM who tells me that is the right move would be able to tell me that it is because that leaves me with the two bishops, and tell me that because of the pawn structure we have in this specific game they will be very strong, and knights not so much. The GM could put it all in terms of various strategic considerations and goals, and from him I could learn things that let me figure out in the future such moves on my own.
All Stockfish tells me is that it looked freaking far into the future and it makes any other move the opponent can force it into lines that won't come out as well. That gives me no insight into why that is better. With a lot of experimenting, trying out alternative lines and ideas against Stockfish, you can sometimes tease out what the strategic considerations and features of the position are that make it so that is the right move.
For your second question, of course, a grandmaster can only tell you why they think they made the move. It may be a postrationalization for the fact that they feel, based on deep learning they have acquired over years of practice, that that move is the right one to make.
It doesn't seem too difficult to have an AI let you know which other strong moves it rejected, and to dig into its forecasts for how those moves play out compared to the chosen move to tell you why it makes particular scenarios more likely. But that would just be postrationalization too...
I think this is wrong. This idea comes from when humans first tried to program computers to do what we wanted them to do. We failed, and it turned out to be really hard. A grand master couldn't explain the algorithm he used exactly. But that doesn't mean he couldn't give any useful information at all.
Think of it like describing a tiger. I have no idea how to describe complicated edge detection algorithms and exact shapes. But I can say something like "an animal with orange stripes", and that would be useful information to another human.
Likewise a grandmaster can explain that pawns are valuable in situations like this, or that point to a certain position and say don't do that, etc. To a computer that information is useless, but to a human that's extremely useful. We already have some pattern recognition and intelligence, we just need some pointers. Not an exact description of the algorithm.
"Likewise a grandmaster can explain that pawns are valuable in situations like this, or that point to a certain position and say don't do that, etc. To a computer that information is useless, but to a human that's extremely useful. "
I think that the only reason this is true is because, humans, shared the same low (or intermediate in this case) level features of their models of the world and a common language to share them.
Artificial neural networks understanding have evolved along other path, and they probable have another different organization between the different levels, but that doesn't make the fundamental mechanism different.
I play competitive chess, and I assure you most moves are made because of players proving in their minds that a move is objectively good.
The reasons for why the player may think the move is objectively good can vary, but they are almost always linked to rational considerations. E.g. that the move increases their piece count, their control of center squares, their attacking opportunities, or is tactically necessary due to the position.
My point being that when grandmaster players play chess, they are just as interested in finding objectively right moves as a computer is. Unless it's speed chess it's rarely a "I suspect this might be good" sort of thing.
(That said, many grandmasters do avoid lines of play they consider too dangerous. World Champion Magnus Carlsen's "nettlesomeness" - his willingness to force games into difficult positions - has been one explanation for why he beats other Grandmasters.)
If the move's objectively good, there would be no variation in moves between players. Since there is variation, I assume different players apply different heuristics for 'good'. And whether the move increases their piece count is a fine justification, but why are you privileging increasing your piece count at this point in this game against this opponent? At some point the answer becomes 'because I learned to'.
Well almost every computer playing chess algorithm uses piece counts to evaluate the quality of chess positions, because barring an amazing tactical combination (which can usually be computationally eliminated past 5 moves) or a crushing positional advantage, a loss of pieces will mean the victory of the person with more pieces.
I would argue you see far more pattern recognition at play in chess than you do of heuristics. Heuristics is more common at lower levels of play.
When Grandmaster's rely on pattern recognition, they are using their vast repertoire of remembered positions as a way to identify opportunities of play. It's not that they think the move looks right, it's that they played a lot of tactical puzzles, and because of this pattern recognition, they are now capable of identifying decisive attacks that can then be objectively calculated within the brain to be seen as leading to checkmate or a piece advantage.
They don't make the move because of the pattern or heuristic. They make the move because the pattern allowed them to see the objective advantage in making that move.
------
As for your point about a move being objectively good: Unless you completely solve the game of chess, there will never be always one move in every situation that's objectively the best. In many games (and you will see this in computer analysis), 2 or 3 moves will hold high promise, while others will hold less. From an objective standpoint all these three moves could be objectively better than all others, but it could be hard to justify that one is necessarily better than another.
The reason for this is partly because between two objectively 'equal' moves, there may be a rational reason for me to justify one over the other based on personal considerations (e.g. because I am familiar with the opening, because I played and analyzed many games similar to this line, because I can play this end game well, etc.) Decisions based on those considerations are not what I would call heuristics, because they are based on objective reasons even if heuristics may have contributed to their formation within the mind.
"Well almost every computer playing chess algorithm uses piece counts to evaluate the quality of chess positions"
This is quite wrong. They use a score that material is only one (although a major) factor of.
"because barring an amazing tactical combination (which can usually be computationally eliminated past 5 moves) or a crushing positional advantage, a loss of pieces will mean the victory of the person with more pieces."
Again, this simply isn't true. For one thing, talk of "piece counts" and even "increasing piece counts", rather than material, is very odd coming from a serious chessplayer. Aside from that, time, space, piece mobility and coordination, king safety, pawn structure, including passed pawns, how far pawns are advanced, and numerous other factors play a role. All of these can provide counterplay against a material advantage ... it need not be "crushing", merely adequate. And tactical combinations need not be "amazing", merely adequate. And whether these factors are adequate requires more than 5 moves of lookahead because chess playing programs are only able to do static analysis and have no "grasp" of positions. All of which adds up to the need for move tree scores to be made up of far more than "piece counts".
You're right that material is the correct term. I was trying to use language appropriate for someone thinking about programming a chess machine.
I perhaps resorted to hyperbole in my original description for the sack of emphasis. You are correct that at higher levels of play, positional considerations matter far more than material considerations. The advantage does not need to be amazing, but adequate. However, as material begins to accumulate the advantage one must have in position in order to justify the loss will increasingly require a position that moves into the realm of "amazing" and "crushing".
You are right that objectively calculating the positional strength of a position is very difficult to do without immense brute forcing, and likely needs more than 5 moves ahead of insight. When I said that I was really referring quite strictly to tactical combinations where the vast majority of tactical mistakes can be caught quickly.
> If the move's objectively good, there would be no variation in moves between players.
If we could solve chess, this most likely would be true, just as it's true for tic-tac-toe, which anyone can solve in mere minutes once they realize that symmetry allows for only 3 distinct opening moves (corner, middle and edge) and games should always end in a draw unless someone makes a silly mistake.
Granted, there are lots of paths to draw that one might take, but the objectively strongest move is to take a corner, then the opposite corner, which requires the opponent to either try to force a draw or lose, whereas it's not hard to use weak moves to hand either player a victory, even though the game of tic-tac-toe can always be forced into a draw with skilled play.
If I had to speculate at a high level why the Sicilian opening is so popular for black in professional play, it would be ultimately because the Sicilian allows black to obfuscate white's board symmetry, which creates opportunity for counterplay against white's fundamental advantage of having the initiative.
I will say though that as someone who devoted some serious time into trying to become a master, that opening theory completely changes as you get to the master level and beyond.
In tournaments I would play a solid but relatively obscure opening as black that worked very well as a safe opening to guard against highly tactical book play, but when I really analyzed the entire line going out past 12-15 moves with a grandmaster, I learned that with careful play there actually was a way to gain a slight edge for white with it -- enough to make the opening uninteresting to most grandmasters. It would play well against masters, but not against a top GM who would know how to play out the line correctly.
Very true. And even in long, professional play its not uncommon to see GM's play highly tactical, but unsound openings if they think the other player doesn't know how to beat it. E.g. I saw Nakamura play the Kings Gambit once against somebody sub-2000 in a professional tournament once (not blitz, full regular timed game).
It's clear that you don't play chess. Anyone who does understands from experience why "increasing your piece count" (which is a backwards and inaccurate way to put it) is the most important and reliable path to victory ... of course it's not always the right thing, but other things being equal, winning material is advantageous. Asking why gaining material advantage is "privileged" is like asking why a weightlifter "privileges" gaining strength, or why a general "privileges" winning battles or destroying supply lines. It's not "because they learned to", it's because "duh, that's obvious".
And the claim that there would be no variation in moves between players if moves were objectively good is absurd nonsense. Just because not everyone plays the best move, that doesn't mean it's not the best move. Of course different players apply different heuristics -- some players are better than others. But in the vast majority of positions, all grandmasters will, given enough time for analysis, agree on the best move or a small number of equally good best moves. When there are multiple best moves, different grandmasters will choose different ones depending on their style, familiarity, opponents, and objectives (tournament players play differently when all they need is a draw than when they need to win).
Your previous comments, about "postrationalization", are also nonsense. Certainly GMs play intuitively in blitz games, but when taking their time they can always say why a move is better -- and they do just that in postgame analyses, many of which can be seen online. The explanations are given in terms of the major strategic factors of time, space, and material, or other factors such as pawn structure and piece coordination, or in terms of tactical maneuvers that achieve advantages in those factors ... or that result in checkmate (which can be viewed as infinite material gain, and many chess playing programs model it as such).
But chessplaying programs aren't goal driven. They evaluate such factors when they statically analyze a position, but they evaluate millions of positions and compare the evaluations and bubble these evaluations up the game tree, resulting in a single score. That score does not and cannot indicate why the final choice is better than others. Thus
"It doesn't seem too difficult to have an AI let you know which other strong moves it rejected, and to dig into its forecasts for how those moves play out compared to the chosen move to tell you why it makes particular scenarios more likely."
is just facile nonsense grounded in ignorance ... of course it can let you know which other strong moves were rejected, but it cannot even begin to tell you why.
"But that would just be postrationalization too... "
You keep using that word, in completely wrong fashion. The computer's analysis is entirely done before it makes the move, so there's nothing "post" about it. And it makes moves for reasons, not "rationalizations". Perhaps some day there will be AIs that have some need to justify their behavior, but the notion does not apply to transparent, mechanistic decision making algorithms.
It's interesting that Lee's style is similar to Carlsen: Lee Sedol's dominating international performances were famous for shockingly aggressive risk-taking and fighting, contrary to the relatively risk-averse styles of most modern Go professionals.
I'm not sure they're that similar. The whole professional Go world had to change to a more aggressive fighting style in order to dethrone Lee Changho, whereas Carlsen in a sense had to do the opposite to consistently take on the best GMs -- he was very aggressive when he was younger, now he is "nettlesome" which isn't quite the same thing.
With me knowing nothing about this particular pocket f the world, how does one live as a "Go professional"? Who pays for this? I don't imagine this is very attractive for sponsors, or do I underestimate how popular this is in Asia?
They are viewed the same sports professionals in China/Japan/Korea. Go news would share sports frontpage, and players are paid well. In China the national Go association is managed under the sports council, with dorms and national squads under the association.
As it's a game more popular amongst older demographics, there tend to be a lot of wealthy patrons and supporters (individuals and companies) who sponsor tournaments and teams. One of the highest-paying competitions is the Ing Cup with a prize of $400,000. Japan has nearly 10 major year-long tournaments every year, totaling over $2mil in prizes, many are sponsored by major newspapers.[1] China has domestic year-long leagues, where city teams each have their own sponsors. All the games I mentioned here pay a match fee whether players win or lose.
So yes, it is a popular game in Asia, however less so for the younger demographic and is unfortunately in decline. Most people just don't have the attention span, interest or time these days. :(
But not as popular as Chinese chess (xiangqi) as a game people actually play, though. Go might be more popular than xiangqi as a spectator sport; I don't know.
I was responding to a comment specifically about China.
Actually Janggi, the Korean variant of Chinese chess (yes, there are some rule differences, but it's recognizably the same game - like Chess without castling and en passant) is very popular, though according to Wikipedia currently less so than Go.
People have learned to communicate heuristics which is very useful for beginning players. A grand master may not be able to communicate nuances of the game to low level players, but they do benefit from working in groups which suggests they can share reasons for a given move not just propose moves and have other independently evaluate them.
So, while people can't map out the networks of neurons that actually made a given choice, we can effectively communicate reasons for a given move.
Perhaps postrationalizaton is still useful? Could empathy and mirror neurons help transfer some of that deep learning? Two weeks later the student faces a similar situation, and they get the same gut feeling their teacher did, and that helps them play better than if their teacher didn't postrationalize?
Absolutely! My point is that human intelligence doesn't actually have any deep insight into how it makes decisions, so we shouldn't be that disappointed that an AI doesn't, either. Humans can postrationalize - explore how they think they make decisions - but they can't tell you how they actually decided. Doing the same for an AI is interesting, but I don't think it's a necessary component of making good decisions in the first place to be able to explain why you made it.
On the other hand, not all actions are decisions. There is plenty of actions we would classify as decisions which are application of rules instead. There is a clear rational path in application of rules. To clarify terminology, for me decisions are actions in response to intractable computationally challenges, e.g. will that couch fit in my living room (when I am in a store, where size calculations are hard in an unfamiliar context) etc. This could mean that your action is my decision if we are not equally capable of calculating based on rules.
Although, when looking at the Deep Dream images that come as a by product (more or less) of image recognition AI, I get the impression that there ARE ways of communicating things about what a computer is "thinking" when trying to solve problems in areas where humans are traditionally better.
Both points are excellent. I think the second one is more important immediately. If you look at the "expert systems" literature, specifically older expert systems based on logic programming, there usually was an "explanation component" in the general architecture.
However I think this area has been under-researched but is obviously important. It would enable very strong learning environments and man/computer hybrid systems. I think there's very direct relevance in safety/security critical systems and there's some literature in operators not understanding what is going on in complex systems and how that can be fatal (think power plants and the like)
For #2, is Stockfish implicitly discovering things that a human might explicitly recognize and articulate (e.g. that the pawn structure has an outsized impact on the value of certain pieces)?
If so, could it be just as easily programmed to answer those questions as it evaluates moves? That is, it seems the information is there to form those answers, but it's not the question the AI has been asked.
Historically there has been a back-and-forth with chess engines....
Early engines tried to really "smart", but consequently couldn't really analyze very deeply, as they spent a lot of time on each position. Newer engines mostly churn through really deep analysis, going many layers deep, but are making comparatively simplistic analyses.
"For instance, it wasn't asked to evaluate the pawn structure and provide that analysis as an output, but it certainly could be programmed to do so."
This quite misses the point. These programs do that as a matter of course, for individual positions. But choosing a move is the result of evaluating many millions of positions and comparing the scores through tree pruning. The program cannot tell you that it chose one move over another because the chosen move is generally better for the pawn structure than the move not chosen, because it doesn't have that information and cannot obtain it.
It should be possible. E.g. I've seen people train a neural network or similar to classify images and then "run it backwards" to get e.g. the image that the network thinks is most "panda".
"If so, could it be just as easily programmed to answer those questions as it evaluates moves?"
No. A chess playing program's move score is a value obtained from treewise comparisons of the static evaluations of millions and millions of positions.
This reminds me something I've read long time ago about the Heroes of Might and Magic game. At some point the AI was so good, it wasn't fun to play, and it had to be dumbed down.
This is a frequent pitfall in video game AI - people go into it thinking the AI's goal is to win, then learn the hard way that the AI's goal should be to lose in an interesting way.
Nobody says that the red koopa in Super Mario Bros. has bad AI.
I can't remember, but I do think it was an interview with Jon Van Caneghem... Either in a book of game design, or magazine. I have to find it.
Similarly long time ago, read about how AOE (Age of Empires) used a lot of computers to play against each other, then do statistic which units actually got used. The idea was to rebalance the units such that all are almost equally used (well in terms of computer-ai play).
I think these two articles were both in the same book, so I'll have to dig.
HOMM3 is also my favourite game, along with Disciples. I'm a big turn-based strategy fan :)
It just means analyzing more than one move at a time. Any engine supporting the UCI protocol should be able to do it. Like Stockfish, which is free.[1] So you don't need to create a new engine to implement this feature. It might be possible to implement it with a bash script. Certainly with JS.[2]
Stockfish does have a "skill level" setting, and it's not terrible at faking club-level play (if you have the Play Magnus mobile app, it's just Stockfish at different skill levels). However, as of 2013 the implementation is much more primitive than what I'm suggesting here.[3]
To be clear, even though it's incredibly obvious, I've never seen this idea anywhere else. It first occurred to me after reading the original Guid & Bratko paper on intrinsic ratings in 2006. Happy to continue this offlist if you want to work on it. My e-mail is in my profile.
I actually understood what you meant, I just think it's funny when we use "just" right before saying something that seems complex (even if it isn't actually all that complex).
Having said that, I only added the link to that comic because I didn't want to just write a comment saying "thanks for the links", and I'm only replying again, because I'm hoping it continues the pattern where you keep replying to my replies with super interesting links!
You can successfully make a computer program play at a 2000 FIDE level (say), in that its win/loss/draw results will be consistent with that of a 2000 FIDE human. IPR is a good way of doing this in a quantitative way.
The interesting problem is to make the computer play like a 2000-rated person, not just as well as a 2000-rated person. I'm a big fan of Regan's work, but I don't think IPR on its own is sufficient to make the computer play idiomatic suboptimal moves.
Shredder claimed to have human-like play at lower levels, so I gave that a try. It works surprisingly well at my level, making plausible mistakes in a fairly consistent manner. When I was playing against it I was in the 1200-1500 range, so I don't know how well it does at higher levels. Also, it had a setting where it would rate you and auto-adjust itself for the next game.
It made playing against a program a lot nicer than other chess programs I had tried.
> 1. How to play well at a level below full strength. In chess, for instance, it is no fun for most humans to play Stockfish or Komodo (the two strongest chess programs), because those programs will completely stomp them. It is most fun for a human to play someone around their own level. Most chess programs intended for playing (as opposed to just for analysis) let you set what level you want to play, but the results feel unnatural.
The astronauts in 2001 play chess with the computer, and it sometimes loses on purpose to make the game more interesting for them.
This is actually a problem I've given a decent amount of though on (although not necessarily reaching a good conclusion), but I think these problems are actually related and not impossible for this simple case. It comes to an issue of what parts of the analysis and at what depth did a best move come to vision? Was it bad when it was sorted for 8 ply but good at 16? Maybe that won't "tell" a person why a move was good, but it gives a lot of tools to help try to understand them (which can be exceedingly difficult right now if a line is not part of the principal variation, but ultimately affects the evaluation by an existing "refutation". But I think the other "difficulty" is that 1800 players play badly in lots of different ways, 2200s play badly in lots of different ways and even Grandmasters play badly in lots of different ways, but very strong chess engines play badly only in a few sometimes limited ways.
It's a bit of a game design problem too, since you may want to optimize for how "fun" the AI is to play against. There are patterns of behavior that can be equivalently challenging, but greatly varying in terms of how interesting or enjoyable they are to play against.
I.e. there are various chess bots that can be assigned personality dimensions like aggressiveness, novelty, etc.
A general AI will likely be LESS able to explain why a move is good, for exactly reason mentioned above (post-rationalization of a massive statistical computation)
No, a truly general AI would play the way we do ... based on goal seeking. Current chess playing programs give moves a single score based on comparing and tree pruning millions of position evaluations, so they cannot possibly articulate what went into that score.
For point #2, the current state of AI allows only for "because you're more likely to win with this move." Today's AI can't reason like a human mind does, it just simulates thousands of scenarios and analyzes which are more likely to be successful, with a very primitive understanding as to why.
When playing, they have a strategy, which they could explain to other go players. They don't just recognize patterns or do brute-force look-ahead. The same is true for good chess players.
There's typically an extra layer (or more) with humans. "Because this puts your Bishop in wasabi which makes it harder for your opponent to extract his Kinglet, making it more likely to win."
Wouldn't it be possible to compare the "top" move with the "runner up" move, compare outcome percentages, and declare whether there is a small or large deviation? Or comparing the "top" move with any other possible move? Or is that too much calculation?
Well, you can make chess engines give you a numeric evaluation for several possible moves. These are typically tuned so that the value of a pawn is around 1 point. A grandmaster 1 or 2 points ahead can routinely convert to a won game, assuming he doesn't blunder.
So if the best move has an evaluation of +0.05 and the second best has -0.02 , the difference is probably a very subtle positional improvement (and the first move may not in fact be better; chess programs aren't perfect). If the best is +3.12 and the second is -0.02, and you can't see why, there's a concrete material tactic you're missing (or, less likely, a major, obvious positional devastation).
But, it can't tell you what you're missing, just the magnitude of the difference.
Seems like a pretty thin line between these conceptions of "understanding". If the AI is programmed to "understand" the rules and ojectives of the game, and it uses that information to assess the best moves for various scenarios, then how does that materially differ from human understanding?
It's strange that almost no one commenting on this has the faintest idea how chess programs work. Chess programs score moves by scoring and comparing, recursively, many millions of positions.
Actually, I wrote one as a senior project years ago. It worked exactly that way, with the exception that the number of positions was less, owed to the available computing power.
Concept was the same as you describe. No rocket science. I purposely read nothing beforehand, because I wanted to devise an approach and this seemed the most obvious.
Of course, nowadays that is not the only technique in use.
In any case, I'm not sure why you think it impossible to add any additional analysis to the program as it repeatedly scores millions of positions.
There are two interesting areas in computer game playing that I have not seem much research on. I'm curious if your group or anyone you know have looked into either of these.
1. How to play well at a level below full strength. In chess, for instance, it is no fun for most humans to play Stockfish or Komodo (the two strongest chess programs), because those programs will completely stomp them. It is most fun for a human to play someone around their own level. Most chess programs intended for playing (as opposed to just for analysis) let you set what level you want to play, but the results feel unnatural.
What I mean by unnatural is that when a human who is around, say, a 1800 USCF rating asks a program to play at such a level, what typically happens is that the program plays most moves as if it were a super-GM, with a few terrible moves tossed in. A real 1800 will be more steady. He won't make any super-GM moves, but also won't make a lot of terrible moves.
2. How to explain to humans why a move is good. When I have Stockfish analyze a chess game, it can tell me that one move is better than another, but I often cannot figure out why. For instance, suppose it says that I should trade a knight for an enemy bishop. A human GM who tells me that is the right move would be able to tell me that it is because that leaves me with the two bishops, and tell me that because of the pawn structure we have in this specific game they will be very strong, and knights not so much. The GM could put it all in terms of various strategic considerations and goals, and from him I could learn things that let me figure out in the future such moves on my own.
All Stockfish tells me is that it looked freaking far into the future and it makes any other move the opponent can force it into lines that won't come out as well. That gives me no insight into why that is better. With a lot of experimenting, trying out alternative lines and ideas against Stockfish, you can sometimes tease out what the strategic considerations and features of the position are that make it so that is the right move.