Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I feel old. Old-old-fashioned(pre-alpha beta) chess engines used a heavyweight evaluator to limit graph searched branch factor.


I think there was some debate on this, actually. I did a lot of research on the subject in the late 2010s and it seems like there were those who felt like limiting the branching factor was the goal, while others felt like fast eval to guide search in order to prune the tree was better.

For what it’s worth, “prune the tree” is still the winningest strategy. MCTS in AlphaGo/AlphaZero scored some wins when they came out, but eventually Stockfish invented the efficiently updatable neural network that now guides their search & it’s much stronger than any MCTS agent.


I suspect you are talking a few decades after the time I am talking about. Many of the earliest chess programs used lossy pruning(type b Shannon engines), under the assumption that the static evaluation at some node could just be bad enough to say don't look down this branch anymore. But they were not provably correct like with alpha beta. Shannon's paper explains a lot more about this. In the late 1940s some of these programs were being run on pen and paper.

For what it's worth stockfish didn't invent efficiently updatable neural networks, Yu Nasu did. Hisayori Noda ported it to Western chess and Stockfish. NNUE is really neat.


Threads like this are why I love HN. Thanks for teaching me new things. :-)


Could you elaborate on this? I thought alpha-beta first appeared way back in the 50s/60s.


The first non trivial chess programs were 'playing' in the late 40s(with pen and paper CPUs). Some of these include features you'll still see today.

https://www.chessprogramming.org/Claude_Shannon proposed two types of chess programs, brutes and selective. Alpha-beta is an optimization for brutes, but many search chess programs were selective with heavyweight eval, or with delayed eval.

Champernowne(Turing's partner), mentions this about turochamp, "We were particularly keen on the idea that whereas certain moves would be scorned as pointless and pursued no further others would be followed quite a long way down certain paths."

You can read more about the A/B/A/B algorithm shift here: https://www.chessprogramming.org/Type_B_Strategy




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: