Comment by AnotherGoodName
3 days ago
I wonder if they gave the chess bot X seconds of thinking time in an era when computers were slower?
The way you set difficulty for turn based game ai is that you limit how far ahead the algorithm searches. If you set the lookahead based on compute time your difficulties will be way out of line if someone upgrades the CPU.
Something similar happened to the macOS chess game, which has always been bundled with OSX/macOS. Once upon a time it was easy to beat in easy mode, which restricted how long it could thing in advance.
When Big Sur rolled out around 2020, Apple introduced a bug which disabled the difficulty slider: no matter what it was set to, it was hard or impossible to beat. In macOS Sequoia, the Chess app got updated again, and supposedly they fixed the difficulty slider, but in the interval silicon improved so much that the old restraints (like think for only a second) mean little. The lowest levels play like a grand master.
is there some reason to implement it as a time limit instead of iterations or something else deterministic? it being affected by CPU speed or machine load seems obvious.
or whatever makes sense if “iterations” isn’t a thing, I know nothing about chess algorithms
It’s simpler. Chess is a search through the space of possible moves, looking for a move that’s estimated to be better than the best move you’ve seen so far.
The search is by depth of further moves, and “better” is a function of heuristics (explicit or learned) on the resulting board positions, because most of the time you can’t be sure a move will inevitably result in a win or a loss.
So any particular move evaluation might take more or less time before the algorithm gives up on it—or chooses it as the new winner. To throw a consistent amount of compute at each move, the simple thing to do is give the engine consistent amounts of time per move.
3 replies →
A time limit is also deterministic in some sense. Level settings used to be mainly time based, because computers at lower settings were no serious competition to decent players, but you don't necessarily want to wait for 30 seconds each move, so there were more casual and more serious levels.
Limiting the search depth is much more deterministic. At lower levels, it has hilarious results, and is pretty good at emulating beginning players (who know the rules, but have a limited skill of calculating moves ahead).
One problem with fixed search depth is that I think most good engines prefer to use dynamic search depth (where they sense that some positions need to be searched a bit deeper to reach a quiescent point), so they will be handicapped with a fix depth.
1 reply →
Heh, I was just discussing this some minutes ago: https://news.ycombinator.com/item?id=46595777
Getting more thinking time tends to give surprisingly small improvements to playing strength. For a classical alpha-beta search based engine, for a given ply (turn) you might have ~20 moves to consider each depth of the search tree. If you're trying to brute force search deeper, a 10x increase in compute time or power doesn't even let you search an extra ply.
Elo gains for engines tend to come from better evaluation, better pruning, and better search heuristics. That's not to say that longer search time or a stronger CPU doesn't help, it just doesn't magically make a weak engine into a strong engine.
There is a strategy called alpha beta pruning meaning you can discard a lot of move options quickly based on the results of similar branches. That and caching similar board states means 20x options does not mean 20x CPU time.
The comment you're replying to already mentions this.
True, although better pruning can massively lower the effective branching ratio compared to pure alpha-beta, making the algorithm benefit more from longer search time again (which is why pruning is so important).
https://en.wikipedia.org/wiki/Turbo_button
Naming it the "Turbo" button rather than making "turbo mode" the default and then pressing a button for "slow" mode, IMO, was marketing genius, even though the results are the same.
Blizzard did a similar thing in World of Warcraft during the beta. After playing for a while, your character would get "exhausted" and start earning half experience for killing mobs. The only way to stop being exhausted would be to log off or spend a LONG time in an inn. At some point, they flipped the script. They made the "exhausted" state the default, and while offline or in an inn, you would gain a "rested" experience buffer, where you would earn double experience.
The mechanic worked exactly the same, but by giving it different terms, players felt rewarded for stepping away from the game occasionally, rather than punished for playing too long. They also marketed it as a way of giving players a way to "catch up" after spending a day or two offline.
The original intention behind the turbo button was to give a way to set the clock speed something closer to a 4.77 MHz Intel 8088 for the benefit of games that relied on CPU cycle timing. Therefore turbo was the default and slow mode the exception.
For some reason this feature persisted in PC compatibles long past having any useful purpose, e.g. toggling a 386 between 33 MHz and 25 MHz. Perhaps manufacturers feared any PC without such a button would be perceived as slower, even though as you say, it's really a slow-down button not a turbo button.
1 reply →
Alternatively, since there's only one difficulty provided ("easy"), I wondered if the programmer have selected say, DifficultyLevels array index 0 meaning the easiest, but it was actually sorted hardest first.