Exploring new forms of chess using artificial intelligence
wired.com
wired.com
My ability to play chess declined precipitously after I learned how to program, because while thinking of my next move I'd always digress into how to design a program to do the work for me.
I originally wrote the Empire game because it was unbearably tedious to play manually, but the computer took care of the tedium and what was left was the fun.
Considering the power of most portable devices these days have you considered revisiting Empire for an IOS or Android version?
I'll announce it here:
It'll likely need some minor work to work with the latest D compiler, attend to that in a bit.
I loved the game, and made several attempts and coding my own version. Naturally, I went on to love Civilization as well, which has similar game play.
Having turned 50, I feel the same way about many strategy games I play now... it becomes less about the fun and more about the optimization, and how to optimize via program or AI. But I've always been that way... had pages of formulas for optimal planet management in MegaWars III for example.
In return, you were able to find a new interest through this irk: programming. And I think being passionate about something is what's required to become really good at something, so the fact that your chess playing started to make you think more and deeper about programming was certainly beneficially for the latter.
Oh, absolutely. It was far beyond my abilities when I started, so I learned how to program with it. It also got me interested in compilers, as the compilers of the day didn't generate good code, Empire was slow, and I naturally assumed I could do much better :-)
This is also the premise behind Factorio.
There's a three-way battle developing between AlphaZero (as described in the article, courtesy of DeepMind), LCZero[5] (derived from LeelaZero[1] -- an open source interpretation of the same principles as AZ), and Stockfish[2] (a long-standing open source chess engine that has recently begun including neural network support).
The 'Top Chess Engine Championship'[3] seems to be a good way to follow the latest news; they also stream matches live on their website[4] (it is quite an information-dense site).
You can play against an up-to-date implementation of Stockfish in your browser -- no registration or signup required -- at https://lichess.org
[1] - https://zero.sjeng.org/
[2] - https://stockfishchess.org/
[3] - https://en.wikipedia.org/wiki/Top_Chess_Engine_Championship
[4] - https://tcec-chess.com/
[5] - https://www.lczero.org/
Edit: correct LeelaZero -> LCZero
AlphaZero is not involved in any battle with LC0 or Stockfish, as no one outside of Deepmind has accessed to it. The battle for chess supreme is between LC0 and Stockfish, with both trading blows pretty much every update :-)
It even beats out lc0 running on an RTX 2080 while itself running in single-threaded mode (it scales well in strength up to at least 32 threads, beginning to taper off from there)
- No castling
- Allowing self capture
- Pawns can move sideways
- Pawns can move 2 squares at a time
https://youtu.be/i-oDOJlWBTw?t=1849
"That's castling sweetheart... It's an advanced level manoeuvre, they added it in the last patch."
The best attempt I've seen is Fisher random chess which attempts to create so many unique starting positions that memorizing openings becomes impossible. It ends up leading to really unique situations, and in some cases even a first move advantage for black.
For example, chess players used to practice (or invent) novel openings to surprise their opponents. Now that AI has explored such a huge range of the game space it can simply show you the optimal moves for each opening. So for humans there's less exploration and more memorization. You're simply trying to follow a path that AI has paved rather than find a new path.
It's kind of like how tic tac toe is fun as a kid until you discover how you can tie everytime. Even with these new rules AI would rapidly find optimal strategies that humans would then race to replicate.
I remember reading somewhere that languages like Finnish and Hungarian are difficult for computers to parse, [1] due to their agglutinative grammatical structure. Not sure if that is actually true, but it seems an interesting starting point.
[1] Discussion sort of about this: https://news.ycombinator.com/item?id=21572261
Genres that would be difficult: - any game based on recognizing images (the first example that pops in my mind is codenames)
- social deduction like werewolf
Pictionary might be harder.
Sounds counter intuitive, but despite doing fast laps when on the circuit alone, even the best AI racers have difficulty surviving a race distance in close pack racing without crashing.
Roborace, the autonomous racing league in development has barely managed to put two cars on track and doing an overtake safely. A lot of money and state of the art research has gone into this.
I expect that AI will be able to beat humans on the (simulated) race track in a decade or two but we aren't there yet.
I, mid-tier sim racer, have no chance against good AI in hotlapping on track in some popular sims, but all of them either yield or cause a crash that would take them to the stewards (or grave) when racing for position on the same piece of track.
Pro racing team have excellent sims these days but they don't have AI opponents.
Forgive this comparison, but the ai drivers in mario kart games also cheat, but aren't particularly representative of current state ML tech. There's likely no ML involved in them at all. There's not much in the way of actual attempts to do this with ML either so it's not proof either way (especially on new untrained courses).
The ones that cheat are in racing games. The hardcore sims that have AI bots don't usually cheat, and they are the ones that are fast by themselves but hopeless and/or dangerous in a pack.
Roborace is the only place where this kind of research has been done, and after many years and millions of dollars they're past their first baby steps, but still learning to walk before they can run.
E.g. "I'm sorry I haven't a Clue"[1] or something like Cards Against Humanity.
Though I imagine someone is trying to apply GPT-3 to these sorts of games already.
Beyond that, any sort of narrative based RPG or exploration game (e.g. legend of Zelda) would be hard to do 'properly', i.e. without scripting a bot.
[1] https://en.m.wikipedia.org/wiki/I%27m_Sorry_I_Haven%27t_a_Cl...
Dixit is a bunch of very different pictures and the goal is to say something about the card you've picked such that some of the other players will know which one it was but not all of them, your opponents are listening to your description and can pick from their own hands of cards. You get points for: Identifying the correct card based on the description when it isn't your turn; Playing a card which people mistook for the correct card when it isn't your turn; Some but not all other players guessing your card when it was your turn.
So that ends up being about shared experiences and culture, because if you share culture with someone you can allude to some element of the picture in a way that's completely opaque to everybody who doesn't share that culture, allowing the "in group" to identify your card while everybody else can't do better than luck.
For an AI there are two interesting challenges. Firstly, in "understanding" the pictures shown on the cards. It's not enough to be like "That's a cat" "That's a book" "That's a tree" you need somehow to compete with a human that thinks "Hmm, that's kinda like the Rapunzel story except it's a bird instead of a princess?" and "The dragon looks happy"
But then the AI also needs cultural context like a human player so it can try to judge good descriptions: "Happy Dragon" is obviously this card, "Cat" might be any of half a dozen cards, how about "I am your father" as a reference to the Cloud City scene that looks a bit like this picture - and so it can try to pick cards that match human descriptions to steal points that way.
At this point, I'd say that AI can't really play collaborative games well, like Diplomacy. They also struggle in continuous games.
[1] https://www.sciencedirect.com/science/article/pii/S000437021...
My assumption would be games or activities that are NOT heavily based in pattern finding, maths, statistics, categorising, memory etc.
I think it is more useful perhaps to consider the motivation for game playing which is completely different (at present) for humans/animals compared to computers.
We play because it is fun, or to bond, or to improve social status, make money, whatever.
Computers play because that is what they are told to do.
Of course you could argue that it is a difficult game for humans to understand as well =) So it might not fit exactly what you prompted for.
If AI teammates were allowed to have a pre-developed, shared model between them for communication so the other automatically "knows" what the others moves mean then it would be closer to fair grounds but that's considered cheating even though human teammates do the same thing.
On the other hand, I worked at a US Team Trials championship game, and the two tables were in separate rooms, with a diagonal partition across the table and completely silent bidding. Presumably they wouldn't go through such gymnastics if cheating weren't a concern. Perhaps the stakes are too low at the regional level (or those who are good enough to get away with it quickly progress to a higher level?).
Sort of, except you have to tell your opponents what your algorithm is. Like you can invent a system where an opening bid of "one heart" means "I have exactly three aces" (as opposed to the conventional meaning of "I have a reasonably strong hand with hearts as my longest suit"), but you can't keep that meaning secret.
The state of the art for Poker goes like this:
Heads Up Limit Texas Hold 'Em is effectively solved.
Not just "There's an AI which is very good at it" there is literally a fixed strategy I can reveal in advance and that strategy will statistically break even against an equally efficient strategy or else gradually take all your chips if you don't have a similar perfect strategy. Even though you know exactly what the strategy is, you can't beat it anyway.
At No Limit the clear champion is AI. Pluribus, Libratus and Deepstack all play clearly better poker, it's not practical to conceive a "solved" or even "near solved" like Cepheus strategy for No Limit, but the AI is tireless and it's disheartening for humans to just find every strategy countered so I expect them to get worse not better.
I don't expect any further exhibition type matches for AI versus professionals at poker because of this success.
Now, full ring is different, but largely because of the social dynamics. If you're at a table with six humans and one AI, obviously all of the humans will co-operate to force out the AI since the alternative is the AI wins. So that's not a very interesting problem.
I suspect games that will give ai the most trouble: games with super sparse signals or ambiguous directions (others mention RPGs, and that tracks)
Games that are hard to simulate will be hard from a training perspective (I think both starcraft and dota2 needed patches to give the AIs reasonable tools to understand the game)
At one point, before go was solved, it seemed like maybe adding significant depth or randomness to a game might make it "hard", but now I'm more convinced that difficulty simulating & exploring tends to be a bigger factor
[1] https://openai.com/blog/learning-montezumas-revenge-from-a-s... It gets it but hard to make a general ai that understands it and the other atari games
Short story writing competitions featuring specific prompts/themes.
SAT test taking.
Short story writing might be more subjective, but the other two are much more objective in nature, and can be easily gamified. AFAIK, AI has a long way to go before it can engage in anything that requires thinking critically.
>I remember reading somewhere that languages like Finnish and Hungarian are difficult for computers to parse
I wonder how much of that is due to AI researchers being speakers of Indo-European languages and not being able to wrap their mind around languages outside that family
If the AI needs to interpret the rules of a card based on it's text and figure out how to use them, it would indeed be a very difficult challenge.
If the AI can simply learn how to play the game with a predefined deck, it'll probably do just fine, outperforming humans but not all the time due to random chance.
I have no idea how they'd handle that. It's a great way to prevent the bot from learning a single dominant strategy and trying to just execute it perfectly.
Role playing games.
Random dice games, like Yahtzee, are trivial to write programs to play "prefectly" ... it's just stats and your program will avoid both wishful thinking and pattern matching traps humans fall into.
That comic is from 2012, and since then Arimaa, Go and Poker have moved solidly into the "Computers Can Beat Top Humans" category. Jeopardy would probably be there too if there was a consistent effort behind it. I think the Starcraft AI is pretty good these days, but people argue over things like APM restrictions.
The classical long for chess is basically dead. Its boring, with majority draws (close to solved game - de0incentivizing aggressive play). I am glad there is shift towards shorter time formats.
Shorter time control creates more urgency and allows to play subpar moves to throw off your opponent. Its much more interesting to observe.
Armagedon rules are being used now as tie breakers and there is a lot more discussion about changes/rules tweaks.
So who knows what next year will bring.
Top GMs currently will probably score 0/12 against Leela/Stockfish. We see innovations frequently in recent years as we learn from engines themselves, h4/h5 pushes as a simple example, but also in terms of style like favoring rapid development and attacking play.
Yes, draws are frequent but that doesn't mean there is no excitement in long games. Rapid/blitz is damn fun to watch and play but there's a certain, different kind of elegance in carefully considered moves as well.
I meant 90min +30mins classical format. It really is stale and boring to watch. And it seems like its mainly a memory game with some meta counter preparations pre-tournament. Where you develop and memorize lines to counter your opponent. That's what I meant by "close to solved game" - as both players are almost role playing for first 20-30 moves. With tiny variations throughout the tournament.
That results in quite uneventful games, usually same line being played in multiple games.
Anyhow that's just an opinion, if someone enjoys classical more power to them.
It's true that the highest levels of play include teams of researchers and computers that develop 30+ move preparation, but what we're also seeing as a result of that are games that are more precise, which IMO is a fundamental component of chess "beauty". Some notable games that were deemed "beautiful" in the past are now seen as less-beautiful as it became apparent that play was suboptimal. Chess beauty now is less about flashy combinations and more about qualities of a position and reverse engineering the "logic" behind certain AI moves, which is still great but admittedly requires more of an investment on learning the game than a spectator might care about.
That framing, though, leaves out the massive benefit that AI has had in training and improving new players. It used to be that you needed to hire a chess master to play against and learn from in order to improve. Now your phone can easily give you a challenge of master-level strength, as well as analyze your games over the board to look for improvements.
No it's the opposite. Since the advent of strong computer programs it has become clear that there are tactical intricacies in lots of positions that have long been overlooked by everyone, including top players. Gambits that everyone thought should not be accepted because it would give away a too strong positional advantage turned out to be winnable by clever defence moves. End games that were thought to be draws turned out to be winnable by although sometimes it would take more than 100 moves. The bottom line is that the tactical part of chess is deeper than most people thought.
But would you call someone who wins a supposedly drawn endgame after 100 moves a tactical player or positional player? No one I know would claim that what happened on the 100th move was a tactic. It was 90+ moves of jockeying for position.
A human can't normally predict out 100 moves of optimal play, so that's why it is jockeying instead of being part of an intricate plan.
I mean, it does bring the question, do you play a game for the experience or solely to win?
I play games for the experience, the world's best chess player probably gets a thrill from being the best and winning. Obviously both experiences are legitimate and in competitive chess, studying historical games to learn patterns has always been a thing, so who's to say that studying scenarios 'solved' by a computer is really any different? Possibly there's a little less romance because a human didn't do it on their own? It doesn't appeal to me personally, but neither did studying chess moves. It really looks like a question of scale of preparation to me.
https://www.chess.com/news/new-alphazero-paper-explores-ches...
All of these attempts failed, because of several reasons:
1) The aforementioned problem of memorizing openings and accumulating draws only occurs at a very, very high level. Even if you're a GM you won't prepare at the level Carlsen et al. do, memorizing entire 30-move games they had against each other twelve years ago.
2) Opening theory moves on and playstyles evolve. AlphaZero shifted the mood from conservative, materialistic, 'computer-like' play to a highly dynamic style that puts an emphasis on piece activity. Just like when we think we got most things figured out, new breakthroughs show we've only barely scratched the surface of what the game has to offer.
3) Most chess players don't see the abundance of draws as a problem. I think it is specifically an American sentiment - in a country where you're either a winner or a loser, the game's failure to rank its top players can be frustrating.
4) Most players see preparation against their opponent as part of competitive play. Think of it as a kind of metagaming. Changing the rules would completely reset that.
5) There's a good chance that any change of rules would aggravate White's marginal first-move advantage. It doesn't matter what the computer says, what matters is how humans play it and how it reflects in the winrates among humans.
That doesn't mean the variants are bad or useless though. Bughouse and suicide chess are crazy fun
And as I said, people rarely if ever prepare openings 'dozens of moves' deep at all but the absolute top level play.
At this point you have to choose if you want chess to cater to competitive chess players (who are mostly content with the rules as they are) or amateur spectators and organizes (who want to see blood).
Ad 3. This abundance of draws (like #1) only becomes a problem at elite levels, too.
Not to mention just because a game ends with a draw doesn't mean it's a dry and boring draw. A draw can be a fascinating back-and-forth struggle full of tricks and swindles.
Same as many decisive games can actually be yawn-inducing - think 70-moves long, even endgame that comes to a conclusion only because one of the exhausted players finally blunders.
I've been watching a lot of Hikaru's streams since PogChamps put him on my radar and he is a very entertaining player IMO.
Stalemates happen less in 960.
There is some interest, and tournaments are played now and again, sure. However, it's nowhere near the popularity of classic chess, which shows no signs of "going out of style".
To provide some perspective - on lichess.org (one of the most popular sites for online chess; the one where the high-profile tournament you mentioned took place) in June there have been 70,374,749 classic games played. Chess960 accounted for 285,788 games. That's ~250 times less popular.
"Stalemates happen less in 960" - seriously? Why? Do you have any source of that claim? I could believe that draws in general are more rare (lack of opening theory makes equalizing in middle game more difficult). But why would it affect the rate of stalemates specifically?
I don't have anything against classic, and as you say, I will probably be playing it forever myself, but from a spectators point of view its more fun if there are less stalemates. There's a lot more room for errors in 960, even among GMs.
That said, I'd like to see some of these variations get implemented on chess.com. A lot of the variations (aside from 960) are a bit silly feeling (e.g. a variation where when you take a piece, all pieces within a 1 square radius get blown to smithereens).
More information about the Arimaa game as well as a gameroom where you can play it available here: http://arimaa.com/
I and some friends attempted to play 3-space go, toroidal go, and go with other mathematical roadblocks a long time ago. It was fun for a few weeks, and we even discovered some interesting properties about where life can exist on a torus, but a computer could do much better. And I'd love to just see the answers.
Conceptually it's fine anyway though, territory is spaces reachable over cardinal directions via empty spaces or dead stones from only one person's living stones.
I would imagine the definition of surround would have to be modified accordingly.
Likewise in bughouse, you play with a partner (where you are opposite colors) against another team. You each play your own game against the opponent but each opponent piece you capture you can give to your partner to place on their board and vice versa. First person to win the game wins for their team. It requires good communication and a different strategies than traditional chess as you need to account for two games and the flow of pieces on both boards.
'doesn’t know it can take an opponent’s pieces' - really? How would the world be different if it did 'know'?
I know this is kind of a nitpick, but I'm tired of all the metaphors in tech journalism that hold no informational value. I think giving a sense of false understanding is worse than just saying nothing at all.
But it does have some way to determine a list of legal moves from any given state, and a way to determine whether a state is winning. To me, that's being 'given the game rules'.
> before any training it would evaluate a capture no differently than any other move.
That's a good way to say it!
No it doesn't. That's the Zero part.
On a different note I learned Xiangqi (Chinese chess) this past February and I found it quite interesting and exciting. Rules seem a bit more complicated than chess and I'm not sure how it compares to Shogi for example. Pretty sure Go is still more complex though :)
https://cse.buffalo.edu/~regan/chess/fidelity/Elista2006.htm...
Wonder if we could go one further and have tournaments where the rules changed to a different ordered variation after a set number of moves.
Now that would be mind bending.
AI had a real impact on how the game was played however. After the advent of computer evaluation, there was a broad consensus that the way to win was to play solid positions. In a way, professional chess became more about not losing than winning. Anish Giri who peaked at number 3 in the world a few years ago is nicknamed the artist because he keeps drawing. Some found that pretty boring.
Funnily, salvation might actually have come from AI. AlphaZero doesn't play boring games and reminded everyone that favoring activity and initiative is a viable strategy.
Still, all things considered, streaming had probably a much bigger impact on chess than AI in the last few years.
It's his story on what happened around Deep Blue.
As this article hinted, its understanding of piece value fluctuates based on the rules of the game but also as the game changes. Alpha Zero makes sacrifices human players wouldn't because they're too wedded to the idea that a queen is 9, a rook is 5 and a knight/bishop is 3.5. As flexible as a human mind gets is valuing a rook pair, bishop pair or knights if the position is closed.
This means that Alpha Go destroys the greedy Stockfish because Stockfish counts the numbers but Alpha Go counts the position of the entire board which is much more complicated.
Recently Stockfish introduced neural network evaluation.
https://blog.stockfishchess.org/post/625828091343896577/intr...
Also, knights and bishops are worth the same except they are not. Knights are good in closed play but you can't mate with two knights and a king. Bishops are definitely better when there is more space.
But, the value is just a simplification to help players assess situation. A piece which can't be played actively is worth nothing.