16 March 2017

Chess problem

From The Telegraph:
The puzzle above may seem hopeless for white, with just a King and four pawns remaining, but it is possible to draw and even win.

Scientists have constructed it in a way to confound a chess computer, which would normally consider that it is a win for black.  However an average chess-playing human should be able to see that a draw is possible.  A chess computer struggles because it looks like an impossible position, even though it is perfectly legal...

The first person who can demonstrate the solution legally will receive a bonus prize.

Both humans, computers and even quantum computers are invited to play the game and solutions should be emailed to puzzles@penroseinstitute.com.

27 comments:

  1. I don't think White can win in 50 moves if the bishops remain on the same B8-H2 line. But if white doesn't move his pawns, he can't lose.

    Lucy

    ReplyDelete
    Replies
    1. Agreed. I don't think White can win unless Black blunders, and I don't think Black can win unless white blunders. Stalemate.

      Delete
  2. Oh.. nice problem. Like the other responses, if White doesn't move except for the King to stay on the White squares, he can't lose. And if black blunders, he has the possibility of improving his position.. If he can force the bishops out of position, he can possibly promote a pawn to a Queen, and then the balance shifts. But Black would have to blunder to allow that.

    But yes, basically a stalemate -- a draw.

    ReplyDelete
    Replies
    1. Not only does the balance shift, but if white promotes the forward C pawn to a queen or bishop checkmate is immediate.

      Delete
  3. 3 black bishops? How?

    ReplyDelete
    Replies
    1. Promoting (at least) two pawns since they are all dark squared bishops and you start with one light squared bishop and one dark squared bishop.

      Delete
    2. Correct. And it has to be the ones on the f and h files, so that a-e can form the walls of the enclosure, and those two have to capture something so that they promote from a black square.

      Delete
  4. I'm...confused why this is confusing people. I suck at chess and see a very simple way to win here. Is there a win that happens no matter what black does? Or are they looking for people to see the simple two-move win that happens if black makes a mistake on their turn?

    ReplyDelete
  5. Normally a chess problem assumes that ''both make the best moves''.
    If people see a win for white, I would love to hear it.
    Hitting the black rooks only releases the black queen and the C pawn can't reach C8 without a bishop hitting it.

    Lucy

    Lucy

    ReplyDelete
  6. What bothers me about this particular puzzle - and the main reason I posted it - is that it seems so trivial. The descriptive language suggests that it is "possible to draw," but all that's required is for the white king to dance on the white squares.

    Nor do I see how a computer would "normally consider that it is a win for black."

    And finally, chess puzzles are typically constructed to be as simple as possible, with no extraneous, unnecessary elements. So why the third black bishop? The second, certainly, to protect the first one against the white king. But why a third? It's not an elegant puzzle.

    Unless I'm missing something.

    ReplyDelete
    Replies
    1. So the verbiage in the Telegraph article is quite confusing, but I might be able to shed a little light on the issue.

      Having written a simple chess AI in grad school I will say that computers do not play chess at all like humans do. We tend to look at "lines of force" from powerful pieces and evaluate groups of pieces attacking or defending together in familiar ways.

      Computers work differently. Let's assume the computer is playing white. From the starting position a computer will see that white has 20 possible moves (16 pawn moves and 4 knight moves). It will then make 20 "copies" of the board one where white made each of its possible moves. Taking each of those 20 cloned positions as a starting point it will then look for what its opponent might do. Again black has 20 legal first moves so, for example, it will make 20 "copies" of the board with each of the possible responses to white's possible queen pawn opening (d4) and 20 "copies" of the board in response to white's possible queen's rook pawn opening (a3) and so on until there are now 400 "virtual positions" that it can see two moves out.

      It then continues this making virtual more and more positions for itself on every odd move and more and more responding positions for black on every even move. As you can see above the number of positions tends to explode exponentially. And although millions of positions are no problem for a computer quadrillions would be. So at some search depth (i.e. some number of moves looked ahead) or after some time limit it gives up and "scores" the boards it has produced.

      Usually this scoring is something very similar to the piece scoring we are used to P=1,N=3,B=3,R=5,Q=9 plus additional scoring of something like +1,000,000 if you find a board with your opponent in checkmate and -1,000,000 if you find yourself in checkmate.

      Now by choosing the best scoring board for each side at each level of the tree of moves you want to pick the move that moves you toward the highest scoring board for white even assuming your opponent makes the best move you can see for them on their turn.

      Thus a move is chosen by brute force evaluation of all possible moves. Humans look at a board and see a rook free to move on the back rank and they will only consider moving it to a pile where it can break out and "get into the game" each time its move comes around a computer will re-evaluate the possibility of moving that rook behind each blocking pawn in light of its new knowledge of its opponents last move.

      Note that the computer has not "understood" any patterns about the board at all. It has just produced millions of legal positions based on the rules of chess and picked the best one for it at each odd level and the worst one for it at each even level.

      Here is a youtube video describing what I just spilled so much ink over.
      https://www.youtube.com/watch?v=CFkhUajb8c8

      Delete
    2. So. Why is this "puzzle" (man I am using a lot of scare quotes) the way it is? It is created to be very hard for the computer.

      Black has a lot of valuable material trapped behind its pawns. This screws up its "scoring" of boards. A lot of boards in the future look fantastic for black because it has 33 points of material on the board vs. white's 4 points of material. I am fairly certain that this is what is meant by the very clumsily written "normally consider that it is a win for black."

      This is also why the problem is not simplified. Each unnecessary element tortures the computer with massively more processing.

      The computer will not in be able to come to the conclusion that this is a draw until it has played damn near 50 moves (as 50 moves without a capture or pawn advancement is considered a draw under standard tournament rules).

      Now white can hypothetically have between 9 and 1 legal moves (including blunders) on its turn, but for simplicity let's say that on average white has about 3 possible moves. Similarly let's say the black bishops usually have at least 10 squares they can move to.

      Now the computer wants to look 20 moves ahead. It needs to evaluate 3^10*10^10 or 590,490,000,000,000 possible boards which isn't going to be computed within a day it might take weeks.

      The computer knows what new board positions the bishops can create by moving, but it never "understands" the greater pattern that white squares are always safe for the white king.

      If the computer is offered a draw it will count up all that valuable material and likely reject it.

      Delete
  7. If you remove two bishops, white still can't win

    Lucy

    ReplyDelete
  8. Lucy,

    If you remove two bishops, White King can move the remaining one off their square or capture it, freeing up the pawn to become a queen. However, I can't see a win for white.

    Stuart

    ReplyDelete
  9. But the Bishop can still move on the B8-H2 diagonal and so prevent being captured by the king. If you remove all bishops, white still can't win!

    Lucy

    ReplyDelete
    Replies
    1. If you remove all the bishops, white mates by queening on c8. (unless maybe it's a draw because black has no moves, if that's the rule)

      Delete
    2. Yes, that's a stalemate and a draw.

      Delete
  10. Black has no moves unless white move the C6 pawn, in which case the black king grabs it on move 2.

    Lucy

    ReplyDelete
  11. Got it! Three moves for white to win with black making their best moves. Since someone has asked, is there a way to hide things below a spoiler blocker on here?

    ReplyDelete
    Replies
    1. I don't know of any way to hide a comment "below the fold", nor have I seen anyone write a comment in a color that only shows after highlighting. I would say just post it. Anyone who is this deep in the comments will not be disappointed to see a "spoiler."

      Delete
    2. Sounds reasonable. Apologies for the verbose descriptions; I don't know the row/column numbers.
      So...the trick is that the bottom-most white pawn has made it all the way across the board. It's already a queen.
      The white pawn just up from it takes the bottom rook, thus becoming another queen. The black king is in check and has to take it. Then white moves its first pawn-queen to the square the second one started in. The black king is in check again, but can't take the first pawn-queen because that would put it in check with the next white pawn up. The only move black can make is to move its king back to its starting square. The pawn-queen then takes the black pawn right in front of it for checkmate.

      Delete
    3. I have seen the kind of "rotated board" puzzles you describe here before, but there are two problems with that here.
      (1) In the proper setup of a chess board both the white player and the black player should have a light colored square in the bottom right of their board from their point of view. So this setup would be wrong.
      (2) It isn't possible for the black pawns to be behind their starting rank (i.e. on the back row where white would queen) via any legal series of moves.

      Delete
    4. Oh shoot, you're right! Thanks for catching that.

      Delete
  12. No way are there ANY moves to win, IF black is making best moves. If I'm wrong, I will gladly apologize in the presence of genius!

    ReplyDelete
    Replies
    1. I tend to agree. In particular on black's next move they can park a bishop on C7 in front of the white pawn and never move it. That seems a reliable method of preventing white from promoting the forward C pawn.

      Delete