Chess: Who will win in this riveting game of Math.random() vs. Math.random()? | Hacker News Reader

Chess: Who will win in this riveting game of Math.random() vs. Math.random()?

chessboardjs.com

316 pointsidiotclock126 comments

Because check mate is a very small subset of possible moves at the end game, I'm guessing the vast majority of games will end(?) with 2 kings moving around randomly for all of time.

This assumes most games will make it past the hump of mid game where its possible the king's motion will be limited and a checkmate can erroneously happen, I suspect this is a rare case as well.

On a side note I wonder what kind of useful information could be mined from a huge set of random-random games. Maybe the relative power of each piece in terms of the number of pieces it captures on average? Also with some heuristic tweeks you could probably start exploring the power of various openings. Of course then its no longer random-random.

If it's impossible to checkmate then it's a stalemate. So if one side has one king and the other side one king (or even one king and a pawn, bishop, knight or rook) then it's a stalemate and the game ends.

edit: forgot you can checkmate with just a king and a queen

Pawn wouldn't be stalemate because it can be promoted to a queen.

I think it's also possible to checkmate with a rook + king (if you corner the king and have your king cover the escape route from check).

Yup, you're right! The algorithm works like this: (each "move" is an implicit "continue" in the pseudocode)

    while no checkmate:
        If your rook is about to be taken, move it to the other end of the current rank.
        If the enemy king is on rank n and your rook is anywhere but rank n-1, move your rook to rank n-1 (unless it can then be taken, in which case move it to the end of its current rank.)
        If your king is anywhere but rank n-2, move towards there.
        If your kings are on the same file, advance the rook to rank n (unless it can be taken...)
        If |file of your king - file of opponents king| is odd, make a wasted move with the rook (keeping it on the same rank).
        If you've gotten this far, move your king towards the opponent's king (staying on the same rank n-2).

Rook + king is a simple checkmate (http://www.chesscorner.com/tutorial/basic/r_k_mate/r_k_mate....)

You can easily checkmate with a king and a rook, it just has to be along an edge of the board.

In rare circumstances you can checkmate with a king and a single bishop: http://www.chess.com/forum/view/more-puzzles/mate-with-one-b...

Any piece (well, except the king) can checkmate with cooperation from the opponent's pieces. The standard sets (queen, rook, two bishops, bishop and knight) are those with which you can force a checkmate against an opponent who just has a king.

Stalemate is a very specific term that means that the side to move has no legal moves. If checkmate is impossible this is generally called a "draw by insufficient material".

I saw one game quickly become a lone white king against six black pieces. The king eventually captured three of them, and then the game gave up after some number of fruitless moves.

Even with that advantage, black couldn't randomly stumble across checkmate.

Are you sure you didn't end with a stalemate?

That's what I got and I think once you get to the end, a stalemate with an imbalance of pieces on one side may be the most likely.

I just got a checkmate first go, rather quickly actually.

if anyone doesn't capture anything or move a pawn in 50 moves its an draw (better train on that bishop & knight endgame :)... if anyone claims it, so uh, not sure how that counts :) However if an checkmate is impossible with the remaining pieces it's automatic

edit: missing pawn from sentence

> if anyone doesn't capture or move anything in 50 moves its an draw

You didn't quite state that right--every move something moves, so it is not possible to go 50 moves without moving anything. :-)

The rule is 50 moves without a pawn moving or anything being captured.

Also, it can be a draw, but it does not have to be. When the last 50 moves have been without a pawn move or a capture, the player on the move can claim a draw if he wishes, but does not have to do so.

Recently, FIDE added a 75 move rule. It is similar to the 50 move rule, except that it is a draw even if both players wish to continue the game. (They also did a similar thing with the 3-fold repetition rule, which like the 50 move rule is only a draw if a player claims it. There is now a 5-fold repetition rule that draws even if neither player wants to claim a draw).

Also, the reason it is 50 moves <em>without a pawn move or capture</em> is because both pawn moves and captures are irreversible.

In fact, the only irreversible move that doesn't reset the 50 move rule is castling (or losing the right to castle), as having the ability to castle technically changes the position.

> I'm guessing the vast majority of games will end(?) with 2 kings moving around randomly for all of time.

Hah, that's what I got on my second run: http://i.imgur.com/joLf3BX.png

The game stopped right there, though.

Edit: Hah! Again! http://i.imgur.com/2ItU89S.png

Yes, its because no other piece can take a king but a king can take all other pieces. The case for taking a king is actually quite rare!

This is a drawn game according to the rules of chess, since checkmate is impossible.

Other draw conditions include:

* Stalemate (=The side to move has no legal moves)

* 50 moves in a row without any permanent changes happening ("permanent changes" means a pawn moving or a piece being captured)

* Exactly the same game state occurs for the third time ("game state" is whose turn it is + status of castling ability + status of en passant possiblity + which pieces are where)

* Agreed draw

Fun fact: In normal time controls (not blitz) at competitive levels, chess games virtually never end in one of the termination conditions. I don't have statistics on hand but I would expect resignations and agreed draws account for 98%+ of grandmaster-level games.

As I understand it, the threefold repetition rule does not mandate a draw, it just allows either player to claim a draw upon occurrence.

I believe 50 moves rules is the same. But in that case, one player is more interested in the draw than the other. In the case of repetition, both players are avoiding a move that gives the other the advantage. It's not so much a mandatory or not question, but if one of them is more willing to try a different move than to draw.

That's right, see article 5.2.d under the FIDE Laws of Chess:

http://www.fide.com/component/handbook/?id=171&view=article

It's not just random vs random. Two extremely weak players will take hours to finish a won game, because the player with the major material advantage does not know how to win!

When teaching kids, it's not uncommon to, after teaching them how to move all the pieces, spend time teaching them how to perform the most basic of mates: KQ vs K, KRR vs K, KR vs K. Only after those three are mastered we have a good opportunity of having beginner games ending in anything other than a stalemate.

I still don't know how to checkmate with two bishops. I mean, I've read how to do it, but if you stuck me in an endgame situation, I'd probably draw. Luckily, I have never actually had an endgame with a king and two bishops versus a king. Same thing with king, knight, and bishop.

You have to move the king into a corner and block his way out with your king.

Which is also a good recipe for a stalemate.

It's always about creating a "box" where the king cannot get out of, and make the box smaller as you force the king onto the edge or corner, where you can finally get the mate move.

More interesting is checkmate with two knights which is only possible if the other king makes a mistake. You cannot force it so if two good players end up in this situation, they mostly agree on a draw.

There's absolutely nothing interesting about a position which is game-theoretically a draw and actually needs a fairly big blunder to be winnable which is why no-one even bothers in practice.

More interesting is that the position is actually winnable if the losing side has an extra piece (a pawn that isn't too advanced up to board).

For those wondering about that: the pawn allows one to move through a position that otherwise would be a stalemate.

The general trick is to block the pawn with one knight, force the king into a corner with king and other knight, and then bring in the second knight for the checkmate so fast that the pawn cannot promote to a queen and then make another move (promotion to a queen is OK if the checkmate immediately follows)

I have a humble level and did checkmate both with two bishops and with bishop and knight... yes, I've found both finals. I had learned the mecanics years before, didn't remember exactly how, but it wasn't so difficult to find the path with enough time.

What I don't want to find is queen vs. rook. I played once queen and pawn vs. rook and won, but it was painful. It seems there are some masters that are specialists in drawing in this positions, even if it should always be a win. Computers with end tables have not this problem.

The mate King-Bishop-Night vs. King is a bit elaborate.

From a random position on the keyboard, you typically need around 20-25 moves to achieve it, and there is a rule that draws a game after 50 moves without any pawn moves.

I've seen an International Master offer draw to his opponent in KNB + K game because he didn't remember what the winning method was (I suposo that after 5+ hours playing your eroded mindset also plays a role.

I did remember the general strategy: take the opponent's king to a corner of the same colour as the bishop. There are a couple of moves that must be thought carefully. But the rest comes very naturally, provided you've practiced it a few times.

The principle is the same as king and rook - the two bishops can trap the enemy king just like a rook can, and you can position your king opposite him and then advance one and force him back. You can work that one out reasonably well from first principles.

Bishop and knight is nontrivial to do in the 50 moves you have, but almost never comes up.

This feels almost like a metaphor for teaching young people about anything... step 1:learn to play a game and the rules. Step 2: learn the implied rules for winning, and how to know when you are winning.

That's why game with victory points can be easier to teach.

It's a vague outline for anyone learning anything, really.

regarding the teaching thing, there's a book that wonderfully describes part of the process behind the "incremental learning", it's not a chess book btw. The book is "The Art of Learning" of Josh Waitzkin.

Really wonderful and insightful book. There's a small part about his vision in how to teach chess and in that part he also shares why he believes it's better to avoid the "learn all the rules than play" but instead to learn the rule incrementally by using actual pieces on the chess table in the most simple situations (2 or 3 pieces max). Then increase the complexity by adding pieces.

Obviously I'm going by memory so I might be a little incorrect into the explanation, but if you love the subject of learning and the subject of chess, the book is worth a look (in fact I'd advise to read the book to almost anyone).

I only watched one game, but it seems that:

1) Yes, most games will end in stalemate. 2) Most wins would occur when one side has enough passed paws such that they chance upon promoting to a few queens.

3) The random-promotion significantly lowers the chances for checkmate. Promotion to a queen is so common that many players who play online chess set paws to automatically promote to queens, so they don't waste the 2 or so seconds it takes to click the "Queen" button.

There are only a few circumstances where you would not promote to queen.

The first is if promoting to queen would cause stalemate. In that case, you would probably promote to bishop instead, because rook would cause the same problem as queen, and knight is harder to force mate with. In the rare case where a bishop would cause stalemate, you promote to rook instead.

The second is if promoting to knight would force checkmate faster or more surely than queen, which is so rare you practically need to play with the intent of making it happen.

Either one is trivial to determine in a chess-playing program.

Check 1: would a knight promotion cause immediate checkmate? If yes, then promote to knight.

Check 2: would a queen promotion cause immediate stalemate? If no, then promote to queen.

Check 3: would a rook promotion cause immediate stalemate? If no, then promote to rook.

Check 4: would a bishop promotion cause immediate stalemate? If no, then promote to bishop.

Check 5: would a knight promotion cause immediate stalemate? If no, then promote to knight.

Otherwise, promote to queen and take the stalemate.

Or you could simply make queen promotion the automatic default unless you advanced the pawn using a context menu to promote to a different piece.

This comment is as far from true as the decision is far from trivial. That is to say, very far.

By far the second most common piece to promote to is a knight, simply because a knight moves in a way a queen cannot. In my 10 years of playing chess, I have probably seen about 5-10 tournament games where promoting to a knight is the correct choice.

Here is a FEN of an example where the only saving move for Black is to play 1...e1=N+: "8/8/8/8/8/3K4/R3p3/3k4 b - - 0 1"

You are right in that the only reason to ever promote to a bishop or rook is to avoid stalemate, yet there is only one practical example of such, here: "8/2P5/8/8/3r4/8/2K5/k7 w - - 0 1".

White must promote to a rook, since if they promote to a queen Black will play 1...Rc4+, forcing 2...Qxc4, which is stalemate. I cannot even find a practical example of when promoting to a bishop would the best choice.

> what kind of useful information could be mined from a huge set of random-random games

Whether there is a real advantage to start with white instead of black ?

Does it matter if there is an advantage to playing white vs black if both players are playing completely randomly? It should only really matter if there is an advantage when both players are playing optimally.

if completely random, you may prove that there is an empirical advantage to starting the game without taking in account the level of any player, because two players playing randomly should be equivalent. I'm not entirely sure, though.

This is technically correct, but does not result in a very useful information, as P(A|B) can be a very different beast than P(A).

Imagine a really simple game where there are only 2 moves: saying 1 and saying 0. The player who first says 1 wins. So of course the player who has the first turn will in practice always win, but when both players move randomly it's 50/50.

Not true. Assuming both players move completely random (both choose either 1 or 0 with 50% probability each) and independently (past actions don't influence the current event) player 1 has a 2:1 advantage, i.e. he will win with probability 2/3. This is because player 1 can win after an even number of rounds (including 0) with 50% probability. So his total chance of winning is 1/2 * (1 + 1/4 + 1/16 + 1/64 + ...) = 1/2 * 4/3 = 2/3.

Yes you're right. Quite the embarrassing mistake I made there.

One of the biggest innovations in computer Go has been the idea that you can evaluate a position in "monte carlo" fashion, by just playing a few random games from that position and seeing who wins. I don't know whether the same idea extends to Chess.

Monte carlo chooses some possible moves at random, then evaluates which is most successful and has a bias towards the more successful ones.

This has the randomness but without any bias or evaluation of effectiveness.

But really, Monte Carlo in Go can basically be thought of as a lazy, intelligent brute-forcing method.

The program stops when nobody has enough pieces to force a checkmate. In three tries, I've seen that twice, and one rook/pawn checkmate. It's a nice Javascript demo.

Never thought this comment would end up on HN when I wrote it ;)

I remember writing this example and being mesmerized watching the games progress. I think I made an alternate version that speed up the time and opened a handful of browser tabs to watch the games. Most of them do end up in insufficient piece draws or the 50-move rule.

Glad to see others are enjoying it :)

Surprised nobody has responded to you. Good job, I really enjoyed seeing your work.

I think I made an alternate version that speed up the time and opened a handful of browser tabs to watch the games. Most of them do end up in insufficient piece draws or the 50-move rule.

I also made an alternate version which runs faster, and I added some code to count games. About an hour on Chrome got me to this point:

    44 white wins.
    415 ties.
    41 black wins.
    500 games played.

EDIT: Another hour, and the stats are now:

    74 white wins.
    847 ties.
    79 black wins.
    1000 games played.

4 hours later, how does it look now?

I would expect that white/black position would be very similar in results (for random games only, of course).

I stopped it running after 2 hours.

One thing that is on my (way too long) list of things to try is n-gram chess. 1-gram chess would, for every move from black, have a dictionary of (following move, win probability) pairs, and it would pick one that is legal using the win probabilities to generate a distribution (if there is a sure win, almost always pick it; if there is a move that always lost before, pick it very rarely)

You can start this of with empty dictionaries, and have the thing learn after each game (let two copies play for a few days to get let them teach each other how to play chess)

2-gram chess would improve on this by using (white move, black's reply) as the key in such a dictionary.

I think that would make for better chess than this. For some N, N-gram chess might even superficially look like the real thing at times.

I'm trying to figure out how you could store this without having massive dictionaries after a night of training games. I guess it's all just integers which helps.

You could probably just drop moves that are below a certain threshold after every k games.

Chess engines make use of similar Markov-chain-like techniques, such as killer [1] and history [2] heuristics. They also use win-loss-draw outcomes from millions of grandmaster games in a similar way to build an opening database, to guide them through the opening, the phase which they are weakest at.

[1] https://chessprogramming.wikispaces.com/Killer+Heuristic

[2] https://chessprogramming.wikispaces.com/History+Heuristic

How is this different from an opening tree?

It would be agnostic of how far the game has progressed (if 1. …c5 is a good reply to 1. e4, it also would be considered a good reply to 75. e4)

It would also be used in end games.

I found myself getting mad at Math.random() pretty quickly. "Argh, you just got to promote two pawns, and you made them both black bishops!?!? I oughta fire you and hire an LFSR!"

I had exactly the same reaction. I was thinking it was going to be hilarious to watch, but it turned out to be extremely aggravating. The random pawn promotion was particularly egregious.

I'm curious if other people had the same visceral reaction.

I was fairly disturbed by the repeated pointless sacrifices of major pieces (which typically aren't even accepted: black offers its queen in exchange for nothing, and white doesn't capture it!).

Yes. I found it really quite distressing to watch.

I did. White had two queens to black's none. It promoted a pawn and made it... a knight. And it was all by itself too. That part was hilarious, but...

In the endgame black had only a king and a pawn and the pawn was hung up on another pawn in the g column. Black's king was trapped in column a by two white rooks in the b column. White managed to create a stalemate with black king at a5 and white rooks at b4 and b6.

At least it's no longer allowed to promote to an opponent's piece. Otherwise, I imagine the computer would do that 50% of the time.

Yeah, now just plug a genetic algorithm to it, and let it evolve.

I once wrote a chess engine that played completely random moves and let it play on the Internet Chess Club against humans for a day. It played 1/0 games (1 minute for all moves). The final result was 46 wins, 22 draws, and 446 losses.

Here's a breakdown.

* 446 losses by checkmate

* 23 wins by time forfeit

* 18 wins by resignation

* 5 wins by disconnection forfeit

* 15 stalemates

* 5 draws by insufficient material

* 2 draws by repetition

Obviously it never won by checkmate. The rest basically came down to whether the human opponent figured out that it was playing against a bot.

Those 15 stalemates were probably other people running bots :)

I briefly wondered why the King felt smarter than the other pieces before realizing the rules prevent it from taking immediately risky moves or staying in a risky position.

Oh wow, I thought it was a joke at first, my game was only a half-dozen moves: http://i.imgur.com/kmKQ2Wi.png

That position is close to the fastest mate, black in 2. Not something, you'd stumble upon in actual play, but if novices ever move that f pawn early, you can usually destroy that side.

Ah the classic fool's mate

I forced white to always take a piece if it can. It initially tears black to shreds, but then the lone Black king battles back and slowly picks off the white pieces.

It's truly a spectacle to witness the elegant tactics of Math.random().

Seems like it always queens pawns; I'd hoped to see some exciting random promotions :/.

Just saw it promote to bishop :)

Two bishops here. It gets boring when there is a few pieces left.. there is hardly any chance random will actually win - it will keep moving around forever.

I just saw a promotion to a knight.

This is also a fascinating phenomenon. To some of the moves really didn't look random -- but of course there were.

We imprint our own flawed notions of randomness on everything.

In the game I watched, I saw two promotions to queens, a knight, and a rook.

Are you guys watching this? eats popcorn I've been watching for like 3 hours and nobody won yet.

It's impossible, I watched it for several minutes, then it stopped moving, not sure why.

This is strikingly similar to a web interface for chess that I just made, even down to the public domain icons. Really slick, but playing against randomized opponents is not very thrilling. There are also limitations to just optimizing for the best turn with one turn lookahead. Although I have to say the drag and drop is better on this version, I think the problem of trying to find the best move in a client-side web application is relatively tricky. The most naive attempt might use a brute-force method, but this could lock up the web browser. And using large data structures would be taxing, too.

link: http://greg.team-duck.com/chess/

I made something that did stats on this a few months ago

see it here

https://barronwasteland.wordpress.com/2014/08/04/random-move...

Those statistics are surprising.

Correct, hence part two was required. This went into some of the possible errors that came up

https://barronwasteland.wordpress.com/2014/12/13/infinite-mo...

It seems like draw by insufficient mating material needs to be separated out from draw by repetition, although if you only enforce draw by repetition, it will inevitably happen on a board with insufficient mating material.

ChessPeace says "Draws by insufficient mating material is not available because of insufficient theory dealing with the non-standard pieces".

"Play with many new pieces with new abilities not seen in standard chess"

It seems that if the board is currently limited to standard pieces, it should use the standard rules for draws by insufficient mating material. How hard is that? No pawns, no non-standard pieces, no queen, no rook, less than two bishops, and no knight + bishop.

It is also interesting to play the Play Random Computer example (http://chessboardjs.com/examples#5001), and try to checkmate the random computer without losing a single piece.

It combines the fun of steamrolling the opponent with the strategy of planning captures that leave your piece perfectly safe, or managing the board so that the computer could take your piece but probably won’t.

Some interesting things happen here, the queens almost always seem to go first in my games (perhaps because of their freedom of movement they tend to end up in dangerous territory quickly). Also lots of pawn promotions make the mid-end games a lot more fun, although as the promotion is also random I've ended up with unwinnable endgames (e.g. two knights).

I don't play chess beyond knowing the rules, but this is a lot more fun than watching a tournament!

I do play chess and found watching this rather painful.

I guess the next thing to do is instead of random: if you can capture a piece of equal or higher value: do so. This is, of course, not a particularly good chess strategy, but would probably be less painful to watch.

The random move is chosen by generating all legal moves, then choosing from them. This favors pieces with more legal moves, and thus tends to favor the queen the most. Compare with choosing from all pieces that have a legal move, then choosing a legal move for that piece, which would favor a lot of pawn motion, at least until they got themselves killed.

To avoid the pawn favoritism you could first select a category of piece, then a specific piece of that category and then finally select a legal move for the piece in question. I think this would be the most even handed way to make the game more entropic.

It's interesting how closely the midgame resembled a real midgame. But superficially. Better than some chess arrangements you see in movie scenes.

Some risky moves from the white and we’ve got a pretty quick checkmate https://www.dropbox.com/s/q66h70kuauog3zq/Screenshot%202015-...

So i simulated 2 games and both of them had a result. Quite interesting, my intuition says that there should be more draws but guess i am wrong. [1] http://imgur.com/rN1zfDD,sQXY6zQ

This was INCREDIBLY frustrating to watch, even as an amateur chess player. Fun project though!

Finally a chess engine I can beat.

I just had black pull out an epic victory over white in truly random fashion: http://imgur.com/9CTukc5

I'm also curious how rare a victory is here, and if it can be modeled with math.

Very dramatic! One plucky white pawn made it all to end before getting slaughtered.

The two queens got very friendly before the white king killed the black queen in a fit of jealousy.

Meanwhile one black knight just stood off in the corner watching. Waiting.

White down to King, Black with Bishop, King, Knight, pawn promoted to Queen... but oh, the mistakes. White swept up piece after piece and could Black still take it with a King-Knight combination? No. No he couldn't. Stalemate.

Very original and fun :)

Near the end of the game the probability of something interesting happening decreases. Maybe in the end it could at least prune out some moves and choose randomly only amongst those that make pieces go closer to each other?

Oooo, that makes me want to use genetic algorithms just to see if I can come up with a great chess player... Is there an online tournament where I can match my algorithm against others?

You can play bots on FICS if you disclose it.

https://chess.stackexchange.com/questions/8066/is-it-possibl...

I guess you would want to program it to only play against other bots, and many of the other ones are probably quite strong (since they're based on relatively advanced chess software). So maybe that's not the ideal environment for starting from zero.

First game I watched and I was expecting stalemate, but down to just a pawn (f2) and a king (b3), white checkmated the opposing king (at b1) by promoting the pawn to a queen

Some ideas:

* host a tournament of many different PRNG seeds.

* generate long strings of moves (random numbers) up front and then use a genetic algorithm to breed and mutate the winning strings.

The computer could probably store moves that ended up in a win. Or collecting statistics on what moves have a higher chance ending up in a win.

White caged its own king in a8 by putting pawns in a7 and a6 while black king just chilled about in c8. Checkmate!

I wonder how long it would take to run all the possible games, assuming there is no sleep time between moves.

Out of curiosity, anybody know the relative strength of this vs. other real engines?

Uh, zero?

Probably, but is it that obvious? Having an opponent that is not even trying to win is much harder to predict.

I've heard several poker players saying that it's hard to play against novices, because they do nonsense.

Surly there is some game theory that says something about this. Anyone?

I wouldn't have thought so, because there isn't the same element of unknown information that there is in poker (i.e. I don't know your hand in Poker), but I know the board and if you're just playing random moves, then I can probably use some variation of Scholars mate to end the game early. (some beginners keep playing it until they finally reach a level that their opponents know how to defend against it)

$100 to the first person to calculate the expected probability of a checkmate

To what precision? ;)

This is almost as good as the goldfish vs. goldfish Street Fighter battle...

Is the board continuously flashing for anyone else? Mac OSX 10.10.1 Safari.

Also would be fun to do with the secure random generator in Web Crypto.

So, when exactly did you record my average chess play?

Theres a bug in this when Math.random() === 1

Obviously, Math.random() must win inevitably.

I'm guessing white wins more often... ;)

surprising how riveting it is.

what .. why ..

there's a black king and a white king and white knight and its just stuck...

The real question is if these wins would change as a result of "global consciousness"

(Global consciousness project is a bunch of computers generating random numbers all over the world that seem to spike when catastrophes occur http://en.wikipedia.org/wiki/Global_Consciousness_Project )

Reply on news.ycombinator.com