nelsonic/learn-chess

Learn how to play Chess from beginner to pro!

learn-chess

Learn how to play Chess from beginner to pro!

learn-chess's Issues

No. 6 Tournament Chess Board/Set

I'm a fan of larger (tournament size) Chess sets. Thinking of ordering this No. 6 Tournament Chess Set:
https://www.ebay.co.uk/itm/BRAND-NEW-WEGIEL-TOURNAMENT-NR-6-WOODEN-CHESS-SET-52cm-WITH-WEIGHTED-PIECES/132560043635

Made by http://www.wegiel-chess.com.pl/about.html

(also, as a manufacturing process nerd, I'd love to visit their factory! raw logs to finished sets!)

Price on ebay is £49.99 (including VAT and shipping) whereas Amazon it's £56.81 (incl. VAT)
https://www.amazon.co.uk/Wegiel-Chess-Set-Tournament-Staunton/dp/B000SOGHQ4

The one negative review on AMZN is mostly about the box and inlay being damaged during shipping:

The other reviews are 5⭐️ and the quality looks great!

£50 is obviously not "cheap" for a game, but I feel that it's reasonably priced considering how much use it will get. Compare it to a console/PC game that costs the same and you finish in 10h and then never look at again ...

Chess Endgame: King and Queen vs. King and Knight

This is an excellent explanation of the "box technique": https://youtu.be/kq5OduYoNqI

Chess Engines: A Zero to One

https://www.chessengines.org/

https://news.ycombinator.com/item?id=31964685

---

Chess Engines: A Zero to One

♟️ This a guide on **how to build a Chess engine from scratch**, updated periodically as I further explore the space. This assumes some basic knowledge of Chess, search algorithms, and coding.

Want to know how chess engines work? Or how AI is now better than every human on earth in chess? Or maybe how you can beat your younger brother who is stupidly good at chess? This is the place.

👋 This is getting a lot more traffic than I thought it would! This is one of my weekly projects, so if you like it, consider [[following me on Twitter](https://twitter.com/willdepue)](https://twitter.com/willdepue) or **text WILL to (833)-255-6887** to get updates when I release something new. - Thanks, Will DePue.

• Color Key

  bold and red means it’s something you should do

  “bold, blue, and in quotes” means a new important topic.

  underlined means it’s a key point

  this means it’s an even more important point

  this means code

Setting up your space

Before you start on your engine, you need a board representation and some form of visualization. I’ve chosen Chess.js and Chessboard.js to start.

Of course, you could build this yourself, but that isn’t really the point of this project. If you’re interested in learning about chess engine board representations, lookup “bitboards” and go from there - lots of interesting ways move generation and board state can be handled with maximum efficiency.

In looking for a good library to work in, I found the Chess.js package. This is a great place to start. It handles all move generation, board state, FEN notation (will get to that in a sec if you don’t know what that is), etc.

https://github.com/jhlywa/chess.js

I do most of my work in Javascript, so this is perfect for me. Super simple (not the fastest) but great for speed and learning fast. Lots of space to mess around, though I’d recommend porting to a strongly typed and compiled language once you start optimizing for performance.

Even if you don’t code in Javascript I would heavily recommend using chess.js, because of it’s super quick implementation with chessboard.js, a HTML chessboard representation.

[chessboardjs.com " Homepage](https://chessboardjs.com/)

These hook together so well it’s unbelievable. Being able to publish a website with your chess engine live in the browser is awesome. Here’s a link to a super simple starter repo you can download and run right now, which you’ll be able to follow along with the whole time.

https://github.com/0hq/starter_chess_engine

👆 Download and run this, it’ll load up what we’re starting with.

Starting up…

It’s important to start with a good baseline, so we’ll start with an engine that only makes random legal moves. Yeah, it’s dumb, but it’s a great starting point for the rest of the project.

If you download the above repo, you’ll see this. All it does is generate random moves for each player. Run this code! Boom, we have our first engine.

var board = null
var game = new Chess()

function makeRandomMove () {
	// chess.js gives us all the possible moves in an array
	// [ move1, move2, move3 ... ]
  var possibleMoves = game.moves()

  // exit if the game is over
  if (game.game_over()) return

	// choses a random index in the list  
  var randomIdx = Math.floor(Math.random() * possibleMoves.length)

	// updates javascript board state 
  game.move(possibleMoves[randomIdx])

	// changes html board state
  board.position(game.fen())

	// call this function again in 5 secs
  window.setTimeout(makeRandomMove, 500)
}

board = Chessboard('myBoard', 'start')

window.setTimeout(makeRandomMove, 500)

https://0hq.github.io/starter_chess_engine/

Okay let’s make it smarter…

Now that we have a bot that makes random moves, let’s make it a bit better. Every time we call game.moves() it loads an array of moves, and actually shows us which ones are captures. Captures are good right? Why don’t we just do more of those?

Strategy #1: Let’s filter for moves that have a capture in them. If none exist, we can just choose a random move.

We can tell which moves are captures because they have a lower case x in them. Here, the one capture move is Qxb6, which tells us it’s a move where our Queen takes the piece on b6.

['a3', 'Qxb6', 'b3', 'b4', 'c3', 'c4', 'd3', 'd4', 'e3', 'e4',
//     'f3', 'f4', 'g3', 'g4', 'h3', 'h4', 'Na3', 'Nc3', 'Nf3', 'Nh3']

These moves are in a format called “algebraic notation”. A couple tips about algebraic notation:

• The last two characters stand for what position on
• If it’s only two characters (’a3’ for example) it’s a pawn move!
• If it has more (like ‘Nf3’) it means it’s a piece moving.
  • The codes are Q for queen, R for rook, B for bishop, K for king, and N for knight (since K is taken).

There’s more to algebraic notation but just remember that the piece comes first, then the square. You can read more here:

[Algebraic notation (chess) - Wikipedia](https://en.wikipedia.org/wiki/Algebraic_notation_(chess))

---

Try building an engine that only makes captures. Compare it against our previous random move engine.

You might also want to build into your bot the ability for human players to play against the engine, so you can test different moves. Just call different code depending on who is black or white: https://chessboardjs.com/examples#5001

⚠️ P.S: I’m not going to provide implementations of my work, because I think it hurts other people’s ability to learn - try to implement what I’m talking about yourself 🙂

Measuring performance

But wait…. how do we know how we’re doing?

Well at the end of the game, we can print something called a “PGN”. It’s basically a list of all the moves that happened in a row. For example, here’s a full game PGN.

1.Nf3 Nf6 2.c4 g6 3.Nc3 Bg7 4.d4 O-O 5.Bf4 d5 6.Qb3 dxc4 7.Qxc4 c6 8.e4 Nbd7 9.Rd1 Nb6 10.Qc5 Bg4 11.Bg5 Na4 12.Qa3 Nxc3 13.bxc3 Nxe4 14.Bxe7 Qb6 15.Bc4 Nxc3 16.Bc5 Rfe8+ 17.Kf1 Be6 18.Bxb6 Bxc4+ 19.Kg1 Ne2+ 20.Kf1 Nxd4+ 21.Kg1 Ne2+ 22.Kf1 Nc3+ 23.Kg1 axb6 24.Qb4 Ra4 25.Qxb6 Nxd1 26.h3 Rxa2 27.Kh2 Nxf2 28.Re1 Rxe1 29.Qd8+ Bf8 30.Nxe1 Bd5 31.Nf3 Ne4 32.Qb8 b5 33.h4 h5 34.Ne5 Kg7 35.Kg1 Bc5+ 36.Kf1 Ng3+ 37.Ke1 Bb4+ 38.Kd1 Bb3+ 39.Kc1 Ne2+ 40.Kb1 Nc3+ 41.Kc1 Rc2# 0-1

You can take a PGN like this and plug it into a chess analysis tool, like Chess.com’s analysis tool. This comes in handy for stepping through the game + it also tells you how well each opponent did against each other. We can now walk through the game and use Chess.com’s analysis to see how good each move was.

[Chess Analysis Board and PGN Editor](https://www.chess.com/analysis)

Go to chess.com/analysis, then click Paste FEN/PGNs, and paste in the above moves! I wont go into the evaluation bar or how chess scoring works here, but you should look that up, since it’ll help you understand your engine’s strength.

Now when you run your new engine, print out the PGN to the console and copy it to chess.com. You can call chess.pgn() and print the PGN to the console.

Another important idea to know about is “Forsyth-Edwards Notation” which is a way to represent a position in chess, rather than a game of a sequence of moves, in a single string. They look like this: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

[Forsyth-Edwards Notation - Wikipedia](https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation)

Low effort explanation: If you read left to right as each row top to bottom (marked by a / ), and black pieces are lowercase and white uppercase. The stuff on the right stores state info like who’s turn it is, castling, etc.

The way to read these is a tad bit unintuitive, just know this is a position in chess. You can read more below, but the important thing to remember is that the PGN is a sequence of moves from some position that describe a game, while the FEN represents an exact layout of pieces.

With this data, you now can take your order of moves or a certain weird position where your bot messed up in and feed it to any machine or give it to someone else to mess around with. Trust me, it’s super helpful when your machine is blundering for some ungodly reason and you need to keep replaying the same thing over and over.

---

Ok… back to our engine playing the random bot.

If we only ever make capture moves, we actually do pretty well - the random bot doesn’t really take back our pieces super often, so if we take his pawn with our queen, it doesn’t really mind.

The problem is that our engine has no clue how to make a checkmate and we trade away our pieces until it’s a stalemate. Now we could choose to make a bot that sees checkmate moves and prioritizes those (they’re actually marked by # signs in algebraic notation, like Rg4# or Rook to g4 checkmate), but that’s dumb, we can get a whole lot better than this.

Minimizing the maximum

Try it yourself: Sit down for a moment with paper and pencil and write down some ideas on how to build an engine. For real, try to do this without reading ahead, this a great opportunity to wrestle a hard problem.

---

The first thing to remember is the limits of hard-coding: even if we wrote down all the ways to not mess up (don't throw away pieces) remember that many aren’t universal laws. The best grandmasters and bots frequently gambit pieces and break rules in complicated situations. Sometimes losing your Queen by taking a pawn is a great move.

If you guessed we need to use a form of tree search, you guessed right.

If you have no experience with search algorithms, this may be hard to understand. Try watching this video if you’re a beginner (or need some review):

https://www.youtube.com/watch?v=5oXyibEgJr0&t=17s

We need to look into the future to see what the best move to make is. We can’t just take every piece we see and not think about what will happen next. Our engine must understand that taking a defended pawn with our Queen is bad because the next move they’ll probably make is take our Queen back.

When it comes to looking through all possible sequences of moves, it’s not going to be super simple. We can’t just look all the way down for the best position in the future which has us winning the most, then make that move. Imagine a possible move order:

I take your defended pawn with my queen, you blunder your rook, then I checkmate you.

That seems like a great scenario for us, right? 🎉  Since we end up winning, so why don’t we pursue that direction? Well… the other player probably isn’t going to blunder their rook, they’ll likely just take back our queen with their pawn and we’ll be losing.

This leads to the important realization: in order to choose the best possible move, we have to consider the game from our opponents perspective. ****We have to assume the other player is going to choose the best response to our move. It’s somewhat unintuitive to how humans play games (sometimes with tricks and hoping to slide by unnoticed), but the best strategy is assuming that they always respond with the best possible move against us.

This is called the minimization-maximization algorithm: we look through all sequences of moves and assume that each player tries to screw the other player over maximally at each step. If both players are perfect, what’s the best strategy? The best move is the one where our opponent can screw us over the least.

Let’s walk this through with Tic-Tac-Toe:

Okay, looks kind of confusing. We start at the top at move #1.
It’s our turn, so we decide what move we make and where the future can go.

Let’s say we choose to make the middle move, move #3: we put our square in the top middle slot and now it’s our opponent’s turn.

You can see they have two choices, move #5 and move #6. In one of them, she can place in the middle and win, and in the other, she can choose to place on the right middle and in the next move, we win.

In order to make the best move, we have to assume that our opponent will choose the move that inconveniences us the most. They’ll probably choose move #5 and we’ll lose the game.

Okay, we now know this is a bad direction to take the game in. In this situation we’ve marked wins as +10 pts and losses as -10 pts, so making move #3 has the equivalent value of -10 pts, since we know our opponent will choose that option.

How about the right option, move #4?

Same situation as before, our opponent has the choice between two moves, one which results in a win for them immediately, and one where we win in the next move.

We assume that they will try to screw us over, which means they’ll choose the -10 pts option, the smallest one. Here they are minimizing the score for themselves.

We can mark move #4 as also causing the score of -10 pts.

Finally, let’s check out move #2.

Looks like we win if we make move #2. This ends the game, and we get a score of +10 points for this move.

Remember, if there were a move that resulted in immediate loss, we would choose between a -10 pts and +10 pts option, and we’d obviously chose the move in which we win, the larger of the two point options. We’re the maximizing player here, since we always will choose the move which benefits us the most.

Okay so we have three moves, two that result in -10, one that results in +10. Since we want to win, we’ll choose the move that nets us the most points, and make move #2.

I hope this gives a better grasp of how mini-max works. Each player chooses the option that benefits them, one always trying to make the score more positive (maximizing) or more negative (minimizing).

Clarification: Which side is positive or negative is arbitrary, all that matters is that each player’s score is opposite the others, this way your enemy always chooses the move that hurts your score the most. In Chess it’s normal to make white the maximizing player (+10 means white is up 10 points) and black the minimizing (-10 means black is up 10 points).

Time to implement.

Try to implement mini-max. It’s not an easy challenge, so no fault if you go and look up how people have done it, but I’d recommend messing around with it for 30 minutes.

Some tips:

Limit your search
In the above example, we search down moves until the game ends. This isn’t possible in chess, since you might need to search down 50 moves to get to a terminal state, so you should choose a point at which you’ll stop and evaluate the board.

Evaluation functions: just subtract pieces
I’ll talk about about evaluation functions in the next section but a decent algorithm is to add up all the pieces on the board by points and see who has more. The normal piece weights are that pawns are worth 1 point, knights and bishops are 3 pts, rooks are 5 pts, the queen is 8 pts, and the king is worth 10000pts (since you lose without it). Add each side’s points and subtract them to get who’s winning.

When to evaluate
We only care about the state of the game once we reach a terminal node. In simpler terms, we don’t care who looks like they’re winning, we only care who’s winning once we reach the end or stop looking. This is important: you’re searching down all possible paths to a certain “depth” or “ply” (the number of moves you look into the future before you stop and evaluate) and then evaluating the state of the game.

Choosing the best move
Once you reach the end for each path, you can compare them to each other and move all the way up the tree you’ve built to choose the best move. Not to give too much away on how to build this, but here’s a visualization. Remember that the maximizing player chooses the highest option, while the minimizing chooses the lowest.

Don’t get stuck
There’s some issues with mini-max that we’re about to get to, so don’t get stuck on tiny ways that this might end up choosing badly. This algorithm is going to crush your last two, don’t worry.

We aren’t very good…

So we’re still blundering pieces.

Why did my engine just take a pawn with a queen? Why is this happening? Weren’t we supposed to be avoiding this with our new algorithm?

• You, probably

Okay, so there’s an issue: by putting a limit on how far we can look into the future we’re occasionally blind to trades.

If I take your pawn with my queen on the 5th move, and I can only look 5 moves into the future, I evaluate the position as if it were done. I’m completely blind to the fact that in the next move I lose my queen and potentially losing me the game.

This is called the “horizon issue”: we’re blind to anything beyond the horizon of how far we can look. This is a tough one, since it doesn’t matter how far we look. Even if we looked 50 moves down if there’s something big that happens on the 51st move, we’ll miss it.

How do you think we solve this? Try to figure it out.

This is a fun one: try to think for 15 minutes on your own.

Don’t look ahead and rob yourself of a challenge.

I’m not kidding…

Don’t keep scrolling…

Did you think about it yet?

Okay last chance.

Solving the horizon issue

The solution is to extend our search until we’re positive that there aren’t any surprises lurking ahead of us. This is called “quiescence search”.

We do this by calling a board “quiet” when it no longer has any available captures (or checks, if you want to include that). When you reach the end of your search and the board isn’t quiet, play out all captures until the board is quiet.

This is done by continuing your minimax search, except with only moves you consider to be “loud moves”. For example, if we reach a terminal node and we have 3 captures on the board still: Rxb4, Bxh7, Qxa7 we simulate each, then re-evaluate to see if they’re quiet. Let’s say Bxh7, Qxa7 are quiet (don’t have any further captures available) after we make our move, but Rxb4 isn’t. We search all of the captures at the state of the board after Rxb4… and so on.

When you finish and begin to collapse all searches upwards, simply treat these capture chains as replacing the starting terminal node. This majorly works, but creates a small issue - can you catch it?

Even though quiescence searches looks through far fewer moves than our normal search, it’ll still account for 50% to 90% of search time in terms of nodes search. Ouch. This is due to quiescence beginning at the deepest level of the tree: adding a couple searches to each branch at the bottom is very significant.

We aren’t forced to capture:

Quiescence has an issue…

In most even positions, you have pieces that are lined up and aimed at each other (like the position below). Both of the players have the option to capture and are choosing not to: if either person decides to capture, the other will capture back and it’ll be even.

It makes sense here to evaluate this position by trading away all the pieces and then checking the score. Because our engine isn’t good at pattern recognition as us, it’s usually a good measure for it to trade all the pieces and then check the state of the game to be sure. It doesn’t know when it might be about to blunder or when it’s just in a position with a lot of pieces aimed at each other.

The issue here is that by replacing the terminal node, it makes the assumption that if the board isn’t quiet, you must make a capture. It only evaluates possible futures after making chains of captures, even though either player can choose not to take.

Imagine if the situation above implied that your opponent taking your pawn was good for you but taking his pawn would result in you losing. If choosing to make any capture is a mistake, any move, even not moving at all would be better. Quiescence thinks you have to take.

There could be situations in which all captures/trade lines are bad for you and it would be far better to avoid making them, instead opting for a small developing move or useless pawn move.

Since quiescence search replaces this position only with the available capture lines, it would think this position was far worse that it is, since it’s only evaluating futures where you trade down all the pieces and must end up taking his pawn.

Here’s a more obvious example of this. It’s black’s turn to play and he’s evaluating this position using quiescence:

This board is inverted lol.

There is only one move here that’s a capture for black, taking the center pawn.

Obviously a bad move.

A human player will just not take at all, choosing to develop his position further elsewhere (maybe shifting your king or repositioning the rook), but not our algorithm:

If it only evaluates positions that involve captures, it thinks that here we’ll be down 4 points after losing our rook for a pawn.

How do consider not capturing in code?

We include the the possibility of doing nothing into our calculations with “null move proving.”

As we collapse quiescence moves, assume chess includes an option to pass on your turn, maintaining the evaluation at the parent terminal node. This is just a good substitute, since we don’t need to find a random useless pawn move to compare to the quiescence lines, we just assume it exists and has no effect on the game.

In this position, we wouldn’t evaluate this to being down a rook, since we assume that there exists at least one other non-capturing move. Problem solved!

* The Zugzwang

My younger brother has pestered me at length the idea of the Zugzwang, the situation in which the fact that you are forced to make a move is a serious disadvantage.

This game begins in a position where it’s white’s turn to play, yet all available moves force him to move away from his pawn, allowing black to take it in the next move.

Null-move pruning makes the assumption that there will always be a move elsewhere, when obviously, that is not true here.

Our engine will assume this position is better than it truly is.

Imagine having a situation in which you’re in a solidified position but since you must make a move, you have to seriously break up your pieces.

There’s a lot edge-case positions where any move is a bad one, and null move pruning can create issues since it assumes there is a move that will have negligible on the game. But honestly, that’s pretty complicated and our bot isn’t even close to being smart enough to care about that.

It’s too slow

So…. uhhhh… we can’t search very far.

This is because the average # of available moves per turn is about 31.

This means to look two moves down, you’ll have to look through 31 of your own possible moves and then look at 31 ways your opponent could respond for each. Every time we look down one more move we take 31x longer.

How do we fix this?

A cool graph of the average # of moves available over time.

Branching factor

By the way, the number of average available moves is called the “branching factor” of a game. Tic-Tac-Toe has a branching factor of 4, which means on average you’re considering 4 moves each turn. The game of Go took so long to beat because its branching factor is around 250.

[Branching factor - Wikipedia](https://en.wikipedia.org/wiki/Branching_factor)

How do we fix this?

How are we supposed to be any good at chess if we can barely look a couple moves into the future? Well you’re never going to avoid the exponential nature of this type of search, but we can get a whole lot smarter in restricting the number of moves we consider each turn.

Instead of considering every possible move we can make in a position (around 31 moves), what if we only considered the ones that were potentially interesting. Good human chess players only think about a handful possible moves in any position, far less than 31. You can’t change the exponent, but we can significantly reduce the base.

Reducing the base

💡 This also is a hard problem, and once again I’d suggest that you try this one on your own. It’s not very easy, since there are a lot of traps in thinking through the problem.

Ok, so how do we eliminate considering moves?

For one, just because a move is dangerous, like trading a queen for a pawn, it doesn’t mean we shouldn’t consider it. There are lots of checkmate patterns that involve dangerous trades like these. While we could increase a degree of pessimism in the way we evaluate dangerous positions, this isn’t a mathematical solution.

The most applicable solution (there are many) to this problem is called “alpha-beta pruning”, and ****is fairly complicated. With alpha-beta pruning, we can skip entire sections of our search tree with no impact to our results. Time for more diagrams:

A short explanation

As I search through possible moves, I can set a baseline for the best option I’ve found so far, which allows me to eliminate other moves as soon as I realize that they will already be worse than something I found already.

A weird short explanation

Keep track of how much your opponent can screw you over. If you’re going through a new move and see that it gives your opponent an opportunity to screw you over even more than before, you can stop immediately.

A long-winded explanation:

Imagine I’ve already searched the possible implications of a specific move and that regardless of what my opponent does after I make that move, I’ll end with a +3 score. If I explore another move, and as I’m searching through my opponents possible moves, I see that there is a potential response that will result in me ending with a +2 score, I can immediately stop any further search into making this move: I already know I have a better option elsewhere.

How to read the diagram:

Nodes with the blue background are the maximizing player, who always chooses the highest option. Nodes with the yellow background are the minimizing player, who always chooses the lowest option.

This graph shows our search algorithms with the first moves we evaluate starting on the left. Let’s start there to get how this works.

We first go all the way down the left.

We examine our first leftmost node, a 5. There’s nothing to do here, as this is the first move we’ve ever seen.

We then move back up to the parent node (marked with a 5 and a yellow background) and try the next move, which we evaluate to a score of 6.

It seems we’re out of nodes to explore in this parent, so as the minimizing player (shown in yellow) we mark the parent node as having a score of 5, the score of the best option.

We then move up even further up the tree, where we’re evaluating from the maximizing player’s perspective.

As the maximizing player (blue) we know that at worst, we can make the move that results in at least a 5 here. We’re going to keep looking for better options but we can always go back to that.

We now look down to the right, where we’ll go back to looking from the minimizing player’s perspective.

The first possible move here leads us to a 7, which looks great for the maximizing player. Remember though, the minimizing player will be choosing, and they’ll choose the best move for them and the worst for the maximizing.

Oh crap, the next move is a 4. We know the minimizing player will at best choose this move or at worst one that we find later that’s worse.

As the maximizing player we can now give up looking at this area, since it doesn’t matter what we find next: it’ll always be smarter to go with the option on the left. There’s no reason to look at other moves (which is the 5 marked in grey).

Important point: We could always explore the grey areas, however, it’s useless, since we already know that the minimizing player will choose a move that’s at most 4. The maximizing player, knowing that, will choose to go left, never right. We can quit and keep looking at other moves.

Where is Alpha-Beta Pruning efficient?

At the lower layers, like above, it’s not too big a deal to prune a branch. We only stopped ourselves from visiting an extra node or two. However, at the top, pruning means we can skip visiting entire sections of the tree →

It’s also incredibly valuable to look at the best moves first. For example, if we first examine a move that results in us winning our opponents queen (+8 score for us), we can eliminate our other moves after only searching through a small percentage of the move tree. Any other move where our opponent has an option to avoid losing their queen is worse, we can quit.

See below how if we had reordered the branches, we would have first seen a potential future which resulted in a +6 score, then almost immediately pruned the next tree. We’re 25% faster!

Unordered, random move orders.

Optimally ordered moves

The right move will always be worse than the left.

---

It’s very likely that my explanation here doesn’t work for you, so here are some good places to read/watch. In my opinion, this is the best video out there:

https://www.youtube.com/watch?v=l-hh51ncgDI

[Alpha-beta pruning - Wikipedia](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning)

[Artificial Intelligence | Alpha-Beta Pruning - Javatpoint](https://www.javatpoint.com/ai-alpha-beta-pruning)

Time to implement.

Try to implement alpha beta pruning! This is a pretty hard one.

Spend at least a couple minutes trying to figure out how this would work, but there’s no fault in searching for examples of alpha beta pruning. It’s not the most intuitive to implement.

Some important helpful pointers if you’re going alone:

Alpha-beta pruning happens “between two layers”
The top layer maintains a memory of the “best move I’ve seen so far” and the layer below is iterating through possible moves, cutting off if it finds worse possibilities. The bottom layer iterations can quit as soon as they know that their enemy will never go in that direction.

It’s only about limiting computation
There’s no changes to the way that moves are calculated and selected, alpha beta pruning only changes when you can stop searching and limit computation in a certain direction.

A final hint…
There is a relationship between each layer’s best move value that can help you create cutoffs. Trying to not give too much away. Know that the implementation has an elegant solution.

Ok done, what next?

Move ordering!

There are a lot of ways you can implement move ordering. So many, in fact, that I probably couldn’t fit them all in this article. But here’s a good starting place:

A promotion of a piece is usually better than most else.
Captures cause a cut-off more than non-captures. So prioritize looking at captures:
You can sort captures by the chance they will be good:

• A weak piece taking a strong piece is usually good. (A pawn taking a queen)
• An equal piece taking an equal piece is usually neutral. (A knight taking a knight)
• A strong piece taking a weak piece is rarely good. (A queen taking a pawn)

There’s so many strategies out there, so go research and explore! Also, make sure that your move ordering isn’t too inefficient 🙂

Evaluation functions

We glossed over evaluation functions earlier, mostly because just subtracting all piece values from each side works surprisingly well for a while. It could be time to start considering positional, not just material advantage.

Here’s an example of piece square tables, a way to encourage moves in move ordering or in board evaluation towards positions where your pieces are in smarter areas. Nobody wants to see their knights on the edge of the board.

As with before, there’s so many directions you can go in here. There’s tons of resources out there for chess evaluation functions and the different strategies you can take - it’s more open-ended than you think.

Oh how far we’ve come…

We’ve covered a lot, so much, in fact, that it’s hard to choose what to talk about next.

MiniMax search with Quiescence search and Alpha-Beta pruning is the foundation on which most chess engines are built. There’s tons of incredible directions you can head in from here.

This is also the point where I’d consider quitting Javascript as a language. The efficiency and speed of your engine is what decides its strength, Javascript is not built for either. I rebuilt my engine in Golang, a strongly typed language with some cool functionality around concurrency.

https://go.dev/

It’s very likely that you’re already moving forward in a specific direction that you’re excited about, and if so, go do that. Come back here later, just go build. If not, that’s fine too, we’re going to go into the last few important new improvements to your engine.

The biggest is…

Your engine has no time restraint

Very likely, your engine just keeps running and running until it finishes it’s given depth. Sometimes it can take forever and sometimes it finishes way too fast. If we’re going to play actual humans, we need to stick to a reasonable time control.

The simplest solution is called iterative deepening:

1. Start by only looking 1 move into the future + quiescence.
2. Check if time has ran out.
3. Look one move deeper.
4. Go back to step 2.

We just keep searching deeper and deeper until time runs out. This way we’ll always have an answer ready and can stick to a certain time limit. Problem solved, right?

Unfortunately no, this makes us much worse. We’ll just end up searching the same nodes over and over again as we go deeper, wasting precious computation time.

Instead of having time to search all the way to depth 4, I have to search depth 1, depth 2, then depth 3 and then run out of time

• You

Yes, and here’s where 🌈 hashing 🌈 comes in. Hashing is amazing. Let’s get started.

Saving our work

To prevent us from wasting our work when we’re running iterative deepening, we can build transposition/hashing tables. This way, we save all the computation we did at each game state ****so we can retrieve it once we start again.

Even further, we want to make sure that we never evaluate the same node twice. It shouldn’t matter whether we arrive at a position in two different ways →

To start, we need a hashing algorithm. If you don’t know what a hashing algorithm is, it’s a way to turn our chessboard state into something we can use to access our saved work.

It shouldn’t matter whether we arrive at a position in two different ways.

You could use a FEN string (rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1) to save information at each state, since FEN strings accurately represent a game state, but that’s not the greatest idea.

This doesn’t work: Using strings as hash keys is inefficient + FEN strings store information about the number of moves played, which we don’t care about.

We’d prefer to use an integer as a hash key (for efficiency) so we’ll need a way to convert a chessboard state into a unique large number. The most popular way to do this is through Zobrist hashing.

Each square on the board stores 12 unique random numbers.

These 12 unique random numbers are for the 12 different pieces: 6 types of pieces (king, queen, rook, bishop, knight, pawn) and 2 colors (white and black).

If you take every piece on the board, grab the corresponding random number for that square, and use an XOR bit operation, you can generate a random bitstring.

Include a starter random number depending on who’s turn to move it is at the board state.

---

It really doesn’t matter that you know why this works, but I’ll explain it anyways a bit.

Two random numbers, let’s say 54 and 43, have a bit representation that looks like this: 110110 and 101011. If we XOR them together ([an XOR combines two bitstrings, read more here](https://www.pcmag.com/encyclopedia/term/xor)), we’ll get 010101. We can convert that result back into a number to get 21, which would be our Zobrist key. This works because we’re combining as many numbers as pieces on the board and each one is 128 bits long, generating a unique number for each position.

The math for how unique this bitstring is, hash conflicts, etc. is pretty complicated and very math heavy. Feel free to research more into hashing algorithms!

---

Awesome!

Now we can convert our chessboard to a unique hash key and use this to store data. Up to you what you want to use (remember that this might end up taking a lot of memory as you scale up).

Overall, it’s most helpful to:

1. Keep the best move in a position to help with move ordering.
2. The bounds of the previous search + the depth it was explored at. This way, if you search a position and found it’s already been explored at a similar or larger depth, you can just use the stored value rather than re-searching.

{
	depth_explored_at: ?,
	best_move: ?
	cut_off: ?
}

That’s all for now folks!

If you implement all of this, your engine should be rated > 1000 ELO, probably more!

ChessRoots.com - best chess moves as an interactive graph

https://www.chessroots.com the most statistically probable chess moves displayed as a graph

HN Thread: https://news.ycombinator.com/item?id=21676933
a few haters ... but most positive.
Sadly it's closed source and none of the data is free even though they have used Lichess (public) data. 😞

Best Opening Moves for Black

What are the statistically best opening moves/defence for black in chess?

Kriegspiel

https://en.wikipedia.org/wiki/Kriegspiel_(chess)

@RobStallion doesn't this look like an awesome way to practice memorising the game/position? 😮

via: https://news.ycombinator.com/item?id=20572705

How To Become A Grandmaster In Chess

https://nextlevelchess.blog/how-to-become-a-grandmaster-in-chess/
via: https://nextlevelchess.blog/how-to-become-a-grandmaster-in-chess/

The thread is surprisingly insightful. tl;dr: it takes 10+ year of exclusive dedication/focus.
So basically the equivalent of any other "Master" level pursuit
e.g. concert piano player or pro athlete/sports player.

"The ability to play chess is the sign of a gentleman.
The ability to play chess well is the sign of a wasted life."
~ Paul Morphy

I actually tend to agree with this quote.
But the level of chess where it's a "wasted life" is "IM" ...
If you make it to GM at least there will be some sort of pay-off.
Still, I think it's preferable to wasting one's life on a computer game ... 🎮
At least chess can be real-life social and relaxing in the outdoors.

https://www.sciencetimes.com/articles/27306/20200915/10-things-playing-chess-brain.htm

Tiredness kills chess (concentration) abilities

Two night's ago I had a horrible night's sleep (less than 4h) and as a direct result I couldn't play chess to save myself! 😩

Last night I got 7h sleep and feel about 70% rested. (I have years of sleep debt to pay off...)
But the graph is very different when not exhausted:

Why People Make Mistakes in Chess? ♟

https://www.technologyreview.com/s/601774/data-mining-reveals-the-crucial-factors-that-determine-when-people-make-blunders/

Stockfish level 1

[Event "Casual Game"]
[Site "https://lichess.org"]
[Date "28/04/2019, 11:12:34"]
[White "nelsonic"]
[Black "Black"]
[Result "1-0"]
[PlyCount "141"]
[FEN "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"]
[Variant "Standard"]
[Termination "mate"]

1. e3 Nf6 2. d4 d6 3. g3 Bg4 4. Be2 Bd7 5. Nf3 Bc6 6. O-O h6 7. c3 Nbd7 8. Na3 e5 9. dxe5 Nxe5 10. Nxe5 dxe5 11. Qxd8+ Kxd8 12. Rd1+ Nd7 13. Bb5 Bxb5 14. Nxb5 Kc8 15. b4 a5 16. bxa5 e4 17. Ba3 Rxa5 18. Bb4 Ra4 19. Rab1 Bc5 20. Bxc5 Ne5 21. Rd4 Rxd4 22. exd4 Nf3+ 23. Kg2 b6 24. Ba3 Kb7 25. c4 Nd2 26. Rb2 Nxc4 27. Rb3 Nd2 28. Re3 Rd8 29. Nc3 f5 30. Be7 Rxd4 31. Bf8 Nc4 32. Re2 Rd3 33. Nd5 h5 34. Bxg7 h4 35. gxh4 Rxd5 36. a4 Rd8 37. Be5 e3 38. fxe3 Kc6 39. Bg3 Kd7 40. e4 fxe4 41. Rxe4 Na3 42. Rd4+ Kc8 43. Rg4 Nc2 44. Rg7 Rd2+ 45. Kh3 Nd4 46. Rxc7+ Kd8 47. Rc4 b5 48. axb5 Nxb5 49. Rg4 Rd3 50. Rg8+ Kd7 51. Rg7+ Kc6 52. Rg6+ Nd6 53. h5 Kd7 54. h6 Ke7 55. h7 Nf7 56. Rg7 Ke8 57. Rxf7 Kxf7 58. h8=Q Re3 59. Qh5+ Ke7 60. Qg5+ Ke6 61. Qxe3+ Kd5 62. Kg4 Kc4 63. h4 Kd5 64. h5 Kc4 65. h6 Kd5 66. h7 Kc4 67. h8=Q Kb4 68. Qec3+ Kb5 69. Qhe5+ Kb6 70. Qcc7+ Ka6 71. Qea5# 1-0

Lichess will always be free

https://news.ycombinator.com/item?id=26910579

Magnus Carlsen: "How My Mind Works" 2013 Interview

https://youtu.be/jdkFP30qXqM

Why?

Chess is a great "break from work" activity.
It's a "level playing field" for age, income, etc.
and a great way to meet and interact with like minded intellectuals.

I wish I had people to play Chess with IRL!
I will be building an outdoor Chess Table in https://github.com/dwyl/home
it will be EPIC.
But meanwhile, I'm opening this repo to capture what I learn along the way.

Beginner's Garden of Chess Openings

https://dwheeler.com/chess-openings/
via: https://news.ycombinator.com/item?id=25446399

How Long Does It Take Ordinary People To "Get Good" At Chess?

https://github.com/jcw024/lichess_database_ETL/blob/main/README.md
via: https://news.ycombinator.com/item?id=29035416

TL;DR: According to 5.5 years of data from 2.3 million players and 450 million games, most beginners will improve their rating by 100 lichess elo points in 3-6 months. Most "experienced" chess players in the 1400-1800 rating range will take 3-4 years to improve their rating by 100 lichess elo points. There's no strong evidence that playing more games makes you improve quicker.

Whats the simplest way to represent chess pieces in a familiar way *digitally*?

I'm trying to determine how many LEDs I will need in order to build a digital chess board.
So I need to know what the simplest possible representation of a chess piece is.

This reddit thread asked the question in almost exactly the same words:
https://www.reddit.com/r/chess/comments/4yegyc/whats_the_simplest_way_to_represent_chess_pieces

But it made me realize that I need to be a bit more specific as the answers are all analog:

What I want is digital chess pieces that fit in a specific resolution e.g. 8x8 pixels
This is the closest I found: https://brosen.itch.io/pixel-chess

https://s3.amazonaws.com/com.c64os.resources/weblog/chess_c64os_networking/pieces_c64os.png

https://www.pixilart.com/draw

How to convert images to Arduino Arrays for use on LCD displays: https://youtu.be/Q1iVtLQOZOI

Along the way I learned about Sovereign Chess: https://youtu.be/GFDSiD6it20 😮 🌈

Datasheet: https://cdn-shop.adafruit.com/datasheets/WS2812B.pdf
WS2812B led strip: https://www.ebay.co.uk/sch/i.html?_nkw=ws2812b+led+strip

But then I got sucked into the YT "oh that looks super interesting" vortex:

And I had to close all my browser tabs to recover my focus!

I think I'm going to need to build a mega LED matrix similar to this one:
DIY Ping Pong LED Wall: https://youtu.be/xFh8uiw7UiY

But with 128 x 128 = 16,384 LEDs this might be unfeasible ...
Each one uses 60mA of current so powering the full array would be 983Amps ... might need a mini power station. 🙄

https://www.aliexpress.com/item/4000833070946.html

Fatal Pawn Grab

https://youtu.be/DNiFs0MWNTA

Chessguessr

Just tried https://www.chessguessr.com/

Obvs failed cause was just figuring out how it works ...
Schoolboy error on 4th guess meant I wasted a chance! 🤦‍♂️

Actual answer was obvs in retrospect:

I just wasn't paying attention. 🙄

Source: https://github.com/Assios/chessguessr
Via: https://news.ycombinator.com/item?id=32162945

Think I still prefer the Lichess approach as I don't have to re-guess moves and the puzzle moves the opposition.
But this is a nice idea and a good way to memorise notation. 👍

How AlphaZero Mastered Its Games

https://www.newyorker.com/science/elements/how-the-artificial-intelligence-program-alphazero-mastered-its-games
via: https://news.ycombinator.com/item?id=18779221
PFD: How-AlphaZero-mastered-its-Games-TheNewYorker.pdf

zugzwang

zugzwang - https://en.m.wikipedia.org/wiki/Zugzwang

“You defeated Magnus”

These are three of my favourite words to start the day with. 😉
(Granted this is “8 year old Magnus” ... but still got to the end-game and didn’t make any mistakes)

[Event "?"]
[Site "?"]
[Date "2018.12.24"]
[Round "?"]
[White "nelsonic"]
[Black "Magnus Carlsen (Age 8)"]
[Result "1-0"]

1. d4 d5 2. Bg5 f6 3. Bh4 Nh6 4. e3 Nf5 5. Nf3 Nxh4 6. Nxh4 Rg8 7. Bd3 g6 8. a4
   c5 9. c3 Bd7 10. dxc5 Qa5 11. b4 Qc7 12. a5 Qc8 13. f3 Bh6 14. f4 b6 15. axb6
   Be6 16. bxa7 Nd7 17. O-O Bg7 18. Qd2 Nxc5 19. bxc5 f5 20. Qb2 h6 21. Nxg6 Bf6
2. Bb5+ Kf7 23. Ne5+ Kf8 24. g3 Bxe5 25. fxe5 Qxc5 26. Re1 Rxa7 27. Rxa7 Qxa7
3. Na3 Qb8 29. Qb4 Qb7 30. Rb1 f4 31. exf4 Bf7 32. Ba4 Qxb4 33. Rxb4 Kg7 34.
   Nb5 Rd8 35. f5 Re8 36. e6 Bh5 37. g4 Bxg4 38. Rxg4+ Kf6 39. Nd4 Ra8 40. Bd7
   Ra1+ 41. Kg2 Ra2+ 42. Kh3 Ke5 43. f6 Kxf6 44. Bc6 Rd2 45. Bxd5 Rd3+ 46. Kh4
   Ke5 47. Bb3 Rxc3 48. Kh5 Rh3+ 49. Kg6 h5 50. Rg5+ Ke4 51. Rxh5 Rxh5 52. Kxh5
   Kxd4 53. Bd1 Ke3 54. h4 Ke4 55. Kg5 Kd3 56. Bg4 Kc3 57. h5 Kb3 58. Kg6 Kc3 59.
   h6 Kd2 60. Bf5 Ke2 61. h7 Kf3 62. h8=Q Ke3 63. Kf7 Kf4 64. Qh5 Ke3 65. Kxe7
   Kd4 66. Qg4+ Kc5 67. Kd7 Kd5 68. e7 Kc5 69. e8=Q Kd5 70. Qe6+ Kc5 71. Qge4 Kb5
4. Q6c6+ Ka5 73. Qea4# 1-0

Raising a Chess Genius

https://youtu.be/9N6lamAfUGE

Back Rank Mate

til: the expression "back rank mate" 🏁

"Bong Cloud"

Today I learned about the "Bong Cloud" from watching this Magnus vs. Andrew Tang game:

https://youtu.be/q_6Zl1jNWYQ

I aspire to this level of comfort/fluency and creativity in the game!

Tactics

https://en.m.wikipedia.org/wiki/Chess_tactic

Free (wiki) book of Chess Opening Theory

https://en.m.wikibooks.org/wiki/Chess_Opening_Theory
Related to #4

Chessnut Pro - Full sized wooden Electronic Chess Set $600 💸

I'd love to get an electronic chess set to teach my children the valid moves i.e. rules of the game. 💭

https://www.chessnutech.com/products/chessnut-pro-1

Difficult to find from the product page, but the board has embedded LEDs:

One of the reviewers mentions the DGT Smart Board:
https://digitalgametechnology.com/products/home-use-e-boards/smart-board-with-indices

ref: https://youtu.be/2a_FdfbiK0k

PT seller: https://www.lojaxis.com/produto/dgt-smart-board/

Skewer

https://en.m.wikipedia.org/wiki/Skewer_(chess)

Positions Chess Engines Just Don't Understand‎

https://www.chess.com/article/view/10-positions-chess-engines-just-dont-understand

Does playing chess make you smarter? Not really

https://www.straitstimes.com/singapore/education/does-playing-chess-make-you-smarter-not-really
discussion: https://news.ycombinator.com/item?id=23888511

Chess CSS

https://www.chenhuijing.com/blog/recreating-the-fools-mate-chess-move-with-css-grid/

Chess tactics explained

https://www.chesstactics.org
via: https://news.ycombinator.com/item?id=25236094

Had a quick look at it. Seems good. If anything the pictures are too tiny, e.g:
https://www.chesstactics.org/introductory-matters/notation_jargon_the-look-of-the-site_hard-copies/notation-and-jargon/1_4_1_1.html

Also it's unclear what age the book is targeted at. The language seems very adult-focussed.
But great that it's free.

How Did the Chess Pieces Get Their Names?

https://www.atlasobscura.com/articles/how-did-chess-pieces-get-their-names
via: https://news.ycombinator.com/item?id=35667642