Your network blocks the Lichess assets!

lichess.org
Donate

Let's talk about trees.

A very good introduction to MinMax and programming computer chess. I suppose talking about how to optimize pruning (proper move ordering) and iterative deepening might be next. :)

A very good introduction to MinMax and programming computer chess. I suppose talking about how to optimize pruning (proper move ordering) and iterative deepening might be next. :)

@TenaciousE said in #2:

A very good introduction to MinMax and programming computer chess. I suppose talking about how to optimize pruning (proper move ordering) and iterative deepening might be next. :)

Yes, certainly proper move ordering is next. As I mentioned the only real ordering done now is checking captures before regular moves but that is a very naive approach probably often counter productive. As I am currently not considering what captures are actually made - like pawn takes Queen might as likely explored first just as Queen takes over-protected pawn. Makes no sense but it's a start.

I am also experimenting with a naive implementation of iterative deepening - I am setting a target depth of say 6ply. But I don't just perform a 6ply search but I perform a 1ply search, order the moves according to their strength, then do a 2ply search on the already ordered moves and so on until I reach the target depth. The naive idea is that while doing more searches they should be more efficient in their move pruning. Small amount of testing shows my itterative deepening approach to be slower than a direct search but I want to experiment more- test it under different positions and different tuning and settings. To see if there is some possible performance gains even from such a naive approach.

While hugely important and I will certainly put it in code and blog. But currently there are some minor housekeeping jobs to be done- biggest of them implement time management. So it can finally play some blitz, rapid and bullet games, improve evaluation as it almost never likes to castle now and still is overly aggressive with Queen threats and some issues where it either likes to repeat moves in winning positions or gives stalemates in simple mating patterns.

@TenaciousE said in #2: > A very good introduction to MinMax and programming computer chess. I suppose talking about how to optimize pruning (proper move ordering) and iterative deepening might be next. :) Yes, certainly proper move ordering is next. As I mentioned the only real ordering done now is checking captures before regular moves but that is a very naive approach probably often counter productive. As I am currently not considering what captures are actually made - like pawn takes Queen might as likely explored first just as Queen takes over-protected pawn. Makes no sense but it's a start. I am also experimenting with a naive implementation of iterative deepening - I am setting a target depth of say 6ply. But I don't just perform a 6ply search but I perform a 1ply search, order the moves according to their strength, then do a 2ply search on the already ordered moves and so on until I reach the target depth. The naive idea is that while doing more searches they should be more efficient in their move pruning. Small amount of testing shows my itterative deepening approach to be slower than a direct search but I want to experiment more- test it under different positions and different tuning and settings. To see if there is some possible performance gains even from such a naive approach. While hugely important and I will certainly put it in code and blog. But currently there are some minor housekeeping jobs to be done- biggest of them implement time management. So it can finally play some blitz, rapid and bullet games, improve evaluation as it almost never likes to castle now and still is overly aggressive with Queen threats and some issues where it either likes to repeat moves in winning positions or gives stalemates in simple mating patterns.

Many years ago, I was "between jobs" and decided I would kill 2 birds with 1 stone, learn a new language AND write a chess program so I could start getting knowledgeable with coding AI techniques (back when there was still an argument that Chess programming could be considered AI ...whole 'nother topic joking about AI defninitions here)

The board, while potentially a trivial part of the code, has a HUGE effect on the nature and speed of evaluation. Beginning OO courses sometimes use chess as an example for objects and come up with horrendously cumbersome OO baggage for pieces and how they move on a board. While nice from an educational standpoint, even with current hardware, they would be monumentally inefficient for even a mediocre chess engine.

Because of that, I hope you don't shirk discussion of your choice for how to code a board.

Many years ago, I was "between jobs" and decided I would kill 2 birds with 1 stone, learn a new language AND write a chess program so I could start getting knowledgeable with coding AI techniques (back when there was still an argument that Chess programming could be considered AI ...whole 'nother topic joking about AI defninitions here) The board, while potentially a trivial part of the code, has a HUGE effect on the nature and speed of evaluation. Beginning OO courses sometimes use chess as an example for objects and come up with horrendously cumbersome OO baggage for pieces and how they move on a board. While nice from an educational standpoint, even with current hardware, they would be monumentally inefficient for even a mediocre chess engine. Because of that, I hope you don't shirk discussion of your choice for how to code a board.

@RichAlexander said in #4:

Many years ago, I was "between jobs" and decided I would kill 2 birds with 1 stone, learn a new language AND write a chess program so I could start getting knowledgeable with coding AI techniques (back when there was still an argument that Chess programming could be considered AI ...whole 'nother topic joking about AI defninitions here)

The board, while potentially a trivial part of the code, has a HUGE effect on the nature and speed of evaluation. Beginning OO courses sometimes use chess as an example for objects and come up with horrendously cumbersome OO baggage for pieces and how they move on a board. While nice from an educational standpoint, even with current hardware, they would be monumentally inefficient for even a mediocre chess engine.

Because of that, I hope you don't shirk discussion of your choice for how to code a board.

Well coming in with zero knowledge of chess programming and a lot of experience in OOP - I did exactly that. I made my board as a object consisting of some game data like castling rights, en passant target squares etc... and the board as a [8][8]int array. I am now aware that it is as you said very cumbersome and have learnt of BitBoards and while I have not yet implemented them. I have written a small introduction to BitBoards and in general how bit operations work and how integers for example can be used to store information via their bits. You can find it here: https://lichess.org/@/likeawizard/blog/bits-aint-nothing-but-bytes-and-tricks/DsGGP92d

@RichAlexander said in #4: > Many years ago, I was "between jobs" and decided I would kill 2 birds with 1 stone, learn a new language AND write a chess program so I could start getting knowledgeable with coding AI techniques (back when there was still an argument that Chess programming could be considered AI ...whole 'nother topic joking about AI defninitions here) > > The board, while potentially a trivial part of the code, has a HUGE effect on the nature and speed of evaluation. Beginning OO courses sometimes use chess as an example for objects and come up with horrendously cumbersome OO baggage for pieces and how they move on a board. While nice from an educational standpoint, even with current hardware, they would be monumentally inefficient for even a mediocre chess engine. > > Because of that, I hope you don't shirk discussion of your choice for how to code a board. Well coming in with zero knowledge of chess programming and a lot of experience in OOP - I did exactly that. I made my board as a object consisting of some game data like castling rights, en passant target squares etc... and the board as a [8][8]int array. I am now aware that it is as you said very cumbersome and have learnt of BitBoards and while I have not yet implemented them. I have written a small introduction to BitBoards and in general how bit operations work and how integers for example can be used to store information via their bits. You can find it here: https://lichess.org/@/likeawizard/blog/bits-aint-nothing-but-bytes-and-tricks/DsGGP92d

Just terminology questions (not affecting the blog efficiency within, but for other sources maybe)

Isn't terminal node restricted nowadays to leaf nodes which are also chess terminal outcome positions per ruleset?

Also, I thought the branch could include root and leaf node in some contexts. While the term "interior" node might be more specific about nodes not the root or not the leaf in a branch (basically the score attributed to root from a best PV is the static evaluation value obtained from the PV leaf).

I like to make a distinction for those nodes like you do, calling them branch nodes apparently, because I would know not to associate those positions to the score attributed via the leaf evaluation further down the branch, to the root position..

Interior nodes, whether they had been evaluated by static evaluations in previous iterations (of iterative deepening) where they would have had leaf status), have only served in exploring the search tree and compressing it back using the optimization like min-max and AB pruning version of it, into the output PV lines.

I like the thick arrows on your tree traversals, as completing the description and making explicit the PV output.

Missing might be the extra stuff beyond strict AB pruning that has been used by engines for a while to keep competing to stratospheric levels among themselves. This is not necessary for a first presentation, but it seems to always stop there, at strict min-max equivalent AB pruning.

You evaluation first paragraph, I find agreeable... (i might need to revisit the opinion in there.... tired at the moment). It might be the most human intelligible part of such engine.

Good initiative anyway... We need translators for chess users that are not wiling/able or having time to code themselves to understand what the engines are doing to chess.

Just terminology questions (not affecting the blog efficiency within, but for other sources maybe) Isn't terminal node restricted nowadays to leaf nodes which are also chess terminal outcome positions per ruleset? Also, I thought the branch could include root and leaf node in some contexts. While the term "interior" node might be more specific about nodes not the root or not the leaf in a branch (basically the score attributed to root from a best PV is the static evaluation value obtained from the PV leaf). I like to make a distinction for those nodes like you do, calling them branch nodes apparently, because I would know not to associate those positions to the score attributed via the leaf evaluation further down the branch, to the root position.. Interior nodes, whether they had been evaluated by static evaluations in previous iterations (of iterative deepening) where they would have had leaf status), have only served in exploring the search tree and compressing it back using the optimization like min-max and AB pruning version of it, into the output PV lines. I like the thick arrows on your tree traversals, as completing the description and making explicit the PV output. Missing might be the extra stuff beyond strict AB pruning that has been used by engines for a while to keep competing to stratospheric levels among themselves. This is not necessary for a first presentation, but it seems to always stop there, at strict min-max equivalent AB pruning. You evaluation first paragraph, I find agreeable... (i might need to revisit the opinion in there.... tired at the moment). It might be the most human intelligible part of such engine. Good initiative anyway... We need translators for chess users that are not wiling/able or having time to code themselves to understand what the engines are doing to chess.

Positive or negative infinity can sometimes be used to indicate that either black or white is checkmated. The numeric values it returns have usually no real meaning to chess - it's just an opinion. And only relative differences between different evaluations have a meaning- compare two moves in a position

This is what i want to dissect. while the last statement can hold even if the 2 previous need updating.
infinity for king:
Legal tree search with a subtreee not yet backwartd min-maxed (including all the amendments) mixing branches with non terminal leave as well as branches with terminal leaves (such as checkmate), can't assign infinitiy to the leafs with mates, or any legal mate (not best min-maxed yet) would win over the other non terminal leafs with material count strong signal (not small imbalance). Somehow in the past it might have worked, i have difficulty getting that. but i know this is not the case anymore.

So many cases about this fundamental mismatch of game outcome currency as material coutining on non terminal nodes, and terminal chess outcome currency, have been developed in the versions prior to SF12 (NNue arrival), and still apply given that classical SF has been frozen (? still true?). I have been told that there were a few endgame classes (not TB) which become conditionals for the static evaluation to improve that (fundamental) mismatch of leaf things to detect with static eval. This is opionion of mine with some argumentation. the fundamental and mismatch is my own wording.. better choices welcome.

The numeric values having no meaning might be a stretch, altough having NNue peek previews at leafs with small classical evaluation signal, might make it hard to follow, but the material counting preset from AB begginning can still be followed by looking deep enough into the PVs all the way to the leafs.. increasingly distants and a moderate depth search on top of that for NNue dispatched leaves.

> Positive or negative infinity can sometimes be used to indicate that either black or white is checkmated. The numeric values it returns have usually no real meaning to chess - it's just an opinion. And only relative differences between different evaluations have a meaning- compare two moves in a position This is what i want to dissect. while the last statement can hold even if the 2 previous need updating. infinity for king: Legal tree search with a subtreee not yet backwartd min-maxed (including all the amendments) mixing branches with non terminal leave as well as branches with terminal leaves (such as checkmate), can't assign infinitiy to the leafs with mates, or any legal mate (not best min-maxed yet) would win over the other non terminal leafs with material count strong signal (not small imbalance). Somehow in the past it might have worked, i have difficulty getting that. but i know this is not the case anymore. So many cases about this fundamental mismatch of game outcome currency as material coutining on non terminal nodes, and terminal chess outcome currency, have been developed in the versions prior to SF12 (NNue arrival), and still apply given that classical SF has been frozen (? still true?). I have been told that there were a few endgame classes (not TB) which become conditionals for the static evaluation to improve that (fundamental) mismatch of leaf things to detect with static eval. This is opionion of mine with some argumentation. the fundamental and mismatch is my own wording.. better choices welcome. The numeric values having no meaning might be a stretch, altough having NNue peek previews at leafs with small classical evaluation signal, might make it hard to follow, but the material counting preset from AB begginning can still be followed by looking deep enough into the PVs all the way to the leafs.. increasingly distants and a moderate depth search on top of that for NNue dispatched leaves.

@dboing

A lot to unpack here.

Your comments on my node classifications. I think you are spot on with those comments. The distinction between leaf and terminal, branch nodes and internal nodes. Nodes having children that are a mix of leaf and branch nodes are all valid points. But I think for the basic understanding of minmax and alpha-beta pruning these various distinctions do not bring much added value to the discussion. When I will write about search algorithms that have strategies to create more aggressive pruning via ordering or other heuristics and transposition tables. The extra distinctions might be valuable to the conversation. In this context I believe it would rather cause more confusion than clarity to a layman reader.

Again exploring more involved topics than minmax and alpha-beta would be too much to ask for a casual reader. I already think this might be on the heavy side, but I could not think of a way to accurately convey the information in a more approachable manner.

I am not quite sure what your comments are about the mixing of mates (+/- inf) and material balances mean. Sounds like some algorithms that are way smarter than me if they can mix values of incomplete searches.

When I say the numeric values have no meaning, I am referring to matches between Stockfish and Lc0 for example. I have often observed that stockfish eval is usually Lc0 eval times two. That does not mean that they widely disagree on their evaluation of the position (it can happen but usually not to that extent). It simply means they use different formulas and constants and scaling.

The numeric value of a eval function has no meaning. If you take the result of an eval function and always add +100 to it. The engine will not change the way it plays. You simply move your zero point from 0 to 100. My point was the only meaning of eval values is when you internally compare them - which is bigger. I think many engines have tried to create evaluations that are intuitive for humans and changing the scaling from one version to another one would cause confusion for humans reading the value but has no effect on the engine play.

I dont know whether the stockfish classical eval has been frozen and further work is only done on the NNUE eval. I would think not. I think NNUE is disabled by default so feature freezing core functionality in favor of optional one that might not even outperform the classical one on older hardware might be a strange choice. I could look into this at some point.

@dboing A lot to unpack here. Your comments on my node classifications. I think you are spot on with those comments. The distinction between leaf and terminal, branch nodes and internal nodes. Nodes having children that are a mix of leaf and branch nodes are all valid points. But I think for the basic understanding of minmax and alpha-beta pruning these various distinctions do not bring much added value to the discussion. When I will write about search algorithms that have strategies to create more aggressive pruning via ordering or other heuristics and transposition tables. The extra distinctions might be valuable to the conversation. In this context I believe it would rather cause more confusion than clarity to a layman reader. Again exploring more involved topics than minmax and alpha-beta would be too much to ask for a casual reader. I already think this might be on the heavy side, but I could not think of a way to accurately convey the information in a more approachable manner. I am not quite sure what your comments are about the mixing of mates (+/- inf) and material balances mean. Sounds like some algorithms that are way smarter than me if they can mix values of incomplete searches. When I say the numeric values have no meaning, I am referring to matches between Stockfish and Lc0 for example. I have often observed that stockfish eval is usually Lc0 eval times two. That does not mean that they widely disagree on their evaluation of the position (it can happen but usually not to that extent). It simply means they use different formulas and constants and scaling. The numeric value of a eval function has no meaning. If you take the result of an eval function and always add +100 to it. The engine will not change the way it plays. You simply move your zero point from 0 to 100. My point was the only meaning of eval values is when you internally compare them - which is bigger. I think many engines have tried to create evaluations that are intuitive for humans and changing the scaling from one version to another one would cause confusion for humans reading the value but has no effect on the engine play. I dont know whether the stockfish classical eval has been frozen and further work is only done on the NNUE eval. I would think not. I think NNUE is disabled by default so feature freezing core functionality in favor of optional one that might not even outperform the classical one on older hardware might be a strange choice. I could look into this at some point.

@likeawizard said in #8:

A lot to unpack here.

Well thank you for going through the effort of answering. I will get back later when i will have assimilated your response, paragraph per paragraph. To perhaps correct or approve of your understanding of the points. Thanks for confirming some of my terminology, like you I take the discovery or research stance of most everything is hypothesis, needing some level of modelling of the objective thing we are trying to understand or build. So, my comments even if affirmative can be corrected.. We adjust.

taking notes about audience adjustments and assumptions.

about the mixing of actual terminal leafs with non terminal leafs (and mate not being assigned infinity for a long time in AB-engine at the top), this is also a problem that a strict AB pruning engine would have. That all AB engine by their initial design have. With increased depth, the proportion of terminal leafs will augment. And so the problem of the diversity of positions for same terminal outcome to be weighted against non terminal leafs measure (dominated de facto by parameter values by material counting).

about the meaning of evaluation. It has only relative meaning. but once you fix a referential. then it has meaning within. Does a gram or a meter have meaning? The meaning is about signal proportions and effect on the ordering.

if a measure system can't significantly differentiate 2 or more variations, or does not have enough discriminating power to evaluate postions differently, then it will dismiss some variations according to that set grain of ordering scrutiny, in any min-max (the purest also) some variations.

yes we could have given 100 to pawns. Point count system gives them 30 i think (side note).

this was my initial response to yours. need a physical break. and will complete if needed. Thanks again for the thinking and careful response.

@likeawizard said in #8: > A lot to unpack here. > Well thank you for going through the effort of answering. I will get back later when i will have assimilated your response, paragraph per paragraph. To perhaps correct or approve of your understanding of the points. Thanks for confirming some of my terminology, like you I take the discovery or research stance of most everything is hypothesis, needing some level of modelling of the objective thing we are trying to understand or build. So, my comments even if affirmative can be corrected.. We adjust. taking notes about audience adjustments and assumptions. about the mixing of actual terminal leafs with non terminal leafs (and mate not being assigned infinity for a long time in AB-engine at the top), this is also a problem that a strict AB pruning engine would have. That all AB engine by their initial design have. With increased depth, the proportion of terminal leafs will augment. And so the problem of the diversity of positions for same terminal outcome to be weighted against non terminal leafs measure (dominated de facto by parameter values by material counting). about the meaning of evaluation. It has only relative meaning. but once you fix a referential. then it has meaning within. Does a gram or a meter have meaning? The meaning is about signal proportions and effect on the ordering. if a measure system can't significantly differentiate 2 or more variations, or does not have enough discriminating power to evaluate postions differently, then it will dismiss some variations according to that set grain of ordering scrutiny, in any min-max (the purest also) some variations. yes we could have given 100 to pawns. Point count system gives them 30 i think (side note). this was my initial response to yours. need a physical break. and will complete if needed. Thanks again for the thinking and careful response.

@dboing said in #9:

about the meaning of evaluation. It has only relative meaning. but once you fix a referential. then it has meaning within. Does a gram or a meter have meaning? The meaning is about signal proportions and effect on the ordering.

That's exactly my point and we agree on that. It is a self-contained and system. The values are well defined and have meaning inside the system. But when removed from that system and compared with a value from another system it loses all meaning.

A good example is people comparing Elo (or Glicko) ratings from different Elo pools, which have different players and even different constants. I have heard people say "Chess.com is better than lichess, because my rating on lichess is 1300 and on chess.com I am only 1100. So the players on lichess must suck". This is a flawed argument and casually comparing things that should not be compared. Because people quite often make this logical fallacy I thought it was important to stress the point that the engine evaluation is just its opinion and expressed in a way that does not have to align with a different engine. Even when those two engines evaluate the position in the same way their way of conveying that can have a differently scaled value attached to it.

@dboing said in #9: > about the meaning of evaluation. It has only relative meaning. but once you fix a referential. then it has meaning within. Does a gram or a meter have meaning? The meaning is about signal proportions and effect on the ordering. That's exactly my point and we agree on that. It is a self-contained and system. The values are well defined and have meaning inside the system. But when removed from that system and compared with a value from another system it loses all meaning. A good example is people comparing Elo (or Glicko) ratings from different Elo pools, which have different players and even different constants. I have heard people say "Chess.com is better than lichess, because my rating on lichess is 1300 and on chess.com I am only 1100. So the players on lichess must suck". This is a flawed argument and casually comparing things that should not be compared. Because people quite often make this logical fallacy I thought it was important to stress the point that the engine evaluation is just its opinion and expressed in a way that does not have to align with a different engine. Even when those two engines evaluate the position in the same way their way of conveying that can have a differently scaled value attached to it.