gowan - the ladder puzzle you posted is quite likely more complex and interesting for a human to solve. But actually, it is much *easier* for a simple computer algorithm than the position I posted.
Most ladders are super-easy to brute force, even the whole board ones you usually need only to example a few hundred to a few thousand positions - the attacker has to keep playing atari, the defender just keeps running (or capturing, if if possible) and the attacker assumes they lose any variation where they can no longer give atari, and you just try all the possibilities.
The interesting thing in the ladder position I posted is
not merely that it's a whole board ladder problem - there are plenty of those out there. What's interesting is that the defender (white) actually gets six mostly-independent branches where in every branch separately they can choose how far to run before proceeding to the next branch, and
every possible combination of distances to run between all six branches has to be proven not to work. So for this ladder, the naive brute force algorithm needs to explore something like (roughly some number between 10 and 20)^6 different variations, because of all the possible combination. This gives millions of positions that need to be examined, rather than just thousands.
Still solvable though - computers are fast. If you continued it around the board you could probably fit another 5 or 6 branches, which would make it a bit harder (although each branch usually wouldn't go as far), but probably still solvable. If there was a more compact way to achieve this kind of branching-like behavior though, such that you could pack in more densely than that, you'd probably make it completely intractable for any pure brute-force solver.
Login
Register
FAQ
Search
lightvector
