Ethics in chess programming

[syzygy]

If you know nothing, you are extremely unlikely to come up with alpha-beta. Most will not even be able to figure out recursion.

I don't think so. Recursion is a general programming technique, and even many mathematical functions are recursively defined.

By "know nothing" I mean you start from "Hello, world" and from there you are on your own. Not many people would independently develop the concept of recursion.

One of the programs I wrote in high school played Connect Four. It looked ahead a few moves and used various heuristics, but it did not implement recursion (or any form of minimax). (A bit later I may have used recursion to implement evaluation of symbol expressions in an assembler/linker, but I probably implemented it iteratively with a stack structure. For sure I had seen some examples of more advanced programming techniques by then. But recursion might be the one programming technique I learned in university.)

And alpha-beta is natural to chess players, who all know that a single refutation is enough to disqualify a variation. And that is really all there is to it. Chess players consider you crazy when during an analysis you start discussing moves that should have been cut off (i.e. are already refuted).

Clearly chess players do not juggle two bounds in their head. Being aware that sometimes you do not need to consider other moves is not yet an algorithm (and certainly does not directly lead to alpha-beta). And likely early programmers thought of this more as a fringe optimisation idea rather than a technique that potentially doubles the search depth and should therefore be exploited to the fullest.

When I wrote my first chess program I was only vaguely aware of alpha-beta, and the implementation I first made was faulty because it was missing the 'deep cutoffs'. (In modern terminology: I started alpha in every node at -INF, rather than -beta of the parent.)

This is what I described a few posts earlier. If a chess programmer (without prior knowledge of chess programming but with knowledge of recursion and minimax) does not spend all his time thinking about how to pick the N most promising moves (the rest to be discarded), then this seems to be the correct implementation of the "single refutation" idea.

[hgm]

By "know nothing" I mean you start from "Hello, world" and from there you are on your own. Not many people would independently develop the concept of recursion.

And if you cannot read or write, even "Hello, world" would be completely over your head. And if you would just be given a bag of 7400 TTL chips, you probably would not get the idea of building a stored-program digital computer with them. Especially when you did not know how to count, and had to invent that too. I guess we agree that no single person would ever be able to reinvent all technological development of the last 10,000 years just on his own steam.

But I don't think that is a reasonable starting point. I think the issue was whether any of us, when in the same situation as Shannon, except with a few hundred times larger and faster computer hardware, would come up with alpha-beta within a few years, when asked to develop a program to play chess.

Clearly chess players do not juggle two bounds in their head.

As a matter of fact they do. When analyzing a position chess players are very well aware what are the thresholds for considering a variation refuted. Be it by themselves, or by the opponent. Like: "when I play move X the opponent just grabs a pawn for free, and I don't want to lose a pawn, so I will first think about an alternative for X, before I start worrying whether the opponent has some complex trick up his sleeve by which I lose even more than a pawn". That is not just alpha-beta, it is even aspiration (when he did not analyze an alternative to X yet with a neutral outcome). And it doesn't matter to them whether the pawn that X blunders away is actually taken on ply 2 or ply 4 (say after a knight's fork), if it is obvious that there is no solace on ply 3 (because they are in check).

This is what I described a few posts earlier. If a chess programmer (without prior knowledge of chess programming but with knowledge of recursion and minimax) does not spend all his time thinking about how to pick the N most promising moves (the rest to be discarded), then this seems to be the correct implementation of the "single refutation" idea.

Indeed. And I continued with the story how it became obvious very quickly that this was somehow broken, and led to the program often spending time on moves that human players already would consider refuted. After some thinking I realized that the beta I had to pass to the negamax daughter was not just -bestScore, but max(-bestScore, beta_parent), because the deviation that showed the already achieved result was unnecessary poor needed to occur not on the previous ply, but 3 ply ago. After which I did have a correct implementation of alpha-beta.

[Mike Sherwin]

By "know nothing" I mean you start from "Hello, world" and from there you are on your own. Not many people would independently develop the concept of recursion.

And if you cannot read or write, even "Hello, world" would be completely over your head. And if you would just be given a bag of 7400 TTL chips, you probably would not get the idea of building a stored-program digital computer with them. Especially when you did not know how to count, and had to invent that too. I guess we agree that no single person would ever be able to reinvent all technological development of the last 10,000 years just on his own steam.

But I don't think that is a reasonable starting point. I think the issue was whether any of us, when in the same situation as Shannon, except with a few hundred times larger and faster computer hardware, would come up with alpha-beta within a few years, when asked to develop a program to play chess.

Clearly chess players do not juggle two bounds in their head.

As a matter of fact they do. When analyzing a position chess players are very well aware what are the thresholds for considering a variation refuted. Be it by themselves, or by the opponent. Like: "when I play move X the opponent just grabs a pawn for free, and I don't want to lose a pawn, so I will first think about an alternative for X, before I start worrying whether the opponent has some complex trick up his sleeve by which I lose even more than a pawn". That is not just alpha-beta, it is even aspiration (when he did not analyze an alternative to X yet with a neutral outcome). And it doesn't matter to them whether the pawn that X blunders away is actually taken on ply 2 or ply 4 (say after a knight's fork), if it is obvious that there is no solace on ply 3 (because they are in check).

This is what I described a few posts earlier. If a chess programmer (without prior knowledge of chess programming but with knowledge of recursion and minimax) does not spend all his time thinking about how to pick the N most promising moves (the rest to be discarded), then this seems to be the correct implementation of the "single refutation" idea.

Indeed. And I continued with the story how it became obvious very quickly that this was somehow broken, and led to the program often spending time on moves that human players already would consider refuted. After some thinking I realized that the beta I had to pass to the negamax daughter was not just -bestScore, but max(-bestScore, beta_parent), because the deviation that showed the already achieved result was unnecessary poor needed to occur not on the previous ply, but 3 ply ago. After which I did have a correct implementation of alpha-beta.

HGM, You just reminded me something I did, that worked, decades ago when I was still programming in 6502 assembler. When I switched to an 8086 I forgot what it was and never could remember afterwards. But now I think I might be remembering. It was a deep beta cut. The current move was not cut. It was the move two ply earlier that was cut. Ohmy it is leaving my mind quickly. It had something to do with if the player at ply - 1 not being able to increase his alpha after so many moves tried then cut at ply - 2 instead of at ply. I'm not sure if that is it exactly but it is something like that.

[xr_a_y]

Maybe the question of the explorator follower dilema or the exploration/exploitation trade-off has its place in this discussion ?
As a whole, the chess community shall "work" better with a good rate of followers just as in any science ; and I guess this is the situation today.

This says nothing about licensing, or rights, or ethics, or respect, or sharing, or ideas, or teaching, ... but it says that everyone input can be usefull, innovative or not.

[algerbrex]

I have a pretty simple rule, I just don't look at sources of other engines at all (at least these parts related to search or evaluation, others should be ok) - I accept reading about general ideas, but the implementation itself is always mine. Not the most effective in Elo terms, but feels the most fun.

I think this is a very admirable yet difficult path to follow, and it's something I myself have considered doing for a while.

I've lost most of my interest in chess programming right now, since my original goal was to break 2000 Elo and I've already far surpassed that, I'm mostly satisfied for now. But when I do return (I know I will eventually in the coming months when I start to get bored again), I've decided I want to start all the way over from scratch. Not just modifying what I have now, but literally starting from a single, hello world file.

Part of this, I will admit, is because I often have a pathological itch to start projects anew once I've been away from them for a good while. But my other two reasons coincide with what you talk about here. For this new version of Blunder, my two primary goals are rigorous testing and code/play-style originality.

The first is because looking back I realize now how much I cut corners with testing, and how Blunder isn't as strong as it should be given its feature set because I was too focused on climbing the Elo ladder. For this new version, every potential strength gaining feature will be consistently tested and the Elo gain will be documented in a consistent changelog. If a feature hasn't been tested, it won't be added. I recognize chess programming isn't always an exact science, but to the best of my abilities, I'd like to change that in my codebase.

But secondly, as you touched on, for this new version I'm not going to be looking at other engines' code. I was very careful in Blunder never to just copy-paste code, and always either get permission from the original author or re-implement things my own way and keep things more original. But it would definitely be a lie to say parts of Blunder weren't heavily influenced by code from other open-source engines: Stockfish, Rustic, Loki, Vice, MinimalChess, MadChess, etc. without these engines Blunder wouldn't be what it is today. So for this new version, my goal is to make all of my code completely my own. I'm of course fine with getting ideas from others, but that'll be the extent of my copying.

Also I'm debating on whether or not I want to stick with Go...