[dragontamer]

The existence of KataGo and it's super-AlphaGo / AlphaZero strength is because Go players noticed that AlphaGo can't see ladders.

A simple formation that even mild amateurs must learn to reach the lowest ranks.

KataGo recognizes the flaw and has an explicit ladder solver written in traditional code. It seems like neural networks will never figure out ladders (!!!!!). And it's not clear why such a simple pattern is impossible for deep neural nets to figure out.

I'm not surprised that there are other, deeper patterns that all of these AIs have missed.

[scotty79]

> And it's not clear why such a simple pattern is impossible for deep neural nets to figure out.

Maybe solving ladders is iterative? Once they make chain-of-thought version of AlphaZero it might figure them out.

[dwaltrip]

It’s very iterative and mechanical. I would often struggle with ladders in blitz games because they require you to project a diagonal line across a large board with extreme precision. Misjudging by half a square could be fatal. And you also must reassess the ladder whenever a stone is placed near that invisible diagonal line.

That’s a great idea. I think some sort of CoT would definitely help.

[dragontamer]

These are Go AIs.

The MCTS search is itself a chain-of-thought.

Or in the case of KataGo, a dedicated Ladder-solver that serves as the input to the neural network is more than sufficient. IIRC all ladders of liberties 4 or less are solved by the dedicated KataGo solver.

It's not clear why these adversarial examples pop up yet IMO. It's not an issue of search depth or breadth either, it seems like an instinct thing.

[scotty79]

> The MCTS search is itself a chain-of-thought.

I'm not quite sure it's a fair characterization.

Either way...

MCTS evaluates current position using predictions of future positions.

To understand value of ladders the algorithm would need iteratively analyse just the current layout of the pieces on the board.

Apparently the value of ladders is hard to infer from probabilisticrvsample of predictions of the future.

Ladders were accidental human discovery just because our attention is drawn to patterns. It just happens to be that they are valuable and can be mechanistically analyzed and evaluated. AI so far struggles with 1 shot outputting solutions that would require running small iterative program to calculate.

[dwaltrip]

Can MCTS dynamically determine that it needs to analyze a certain line to a much higher depth than normal due to the specifics of the situation?

That’s the type of flexible reflection that is needed. I think most people would agree that the hard-coded ladder solver in Katago is not ideal, and feels like a dirty hack. The system should learn when it needs to do special analysis, not have us tell it when to. It’s good that it works, but it’d be better if it didn’t need us to hard-code such knowledge.

Humans are capable of realizing what a ladder is on their own (even if many learn from external sources). And it definitely isn’t hard-coded into us :)

[dragontamer]

Traditional MCTS analyzes each line all the way to endgame.

I believe neural-net based MCTS (ex: AlphaZero and similar) use the neural-net to determine how deep any line should go. (Ex: which moves are worth exploring? Well, might as well have that itself part of the training / inference neural net).

[mafuy]

In my understanding, in KataGo, the decision of how long to follow a line is made solely by MCTS via its exploration/exploitation components. These in turn are influence by the policy/value outputs of the DCNN. So in practical terms, your statement might just be called true.

The raw net output includes some values that could be used in addition, but they are not used. I don't know if they were ever looked at closely for this purpose.

[bwfan123]

>It seems like neural networks will never figure out ladders (!!!!!). And it's not clear why such a simple pattern is impossible for deep neural nets to figure out.

this is very interesting (i dont play go) can you elaborate - what is the characteristic of these formations that elude AIs - is it that they dont appear in the self-training or game databases.

[dragontamer]

AlphaGo was trained on many human positions, all of which contain numerous ladders.

I don't think anyone knows for sure, but ladders are very calculation heavy. Unlike a lot of positions where Go is played by so called instinct, a ladder switches modes into "If I do X opponent does Y so I do Z.....", almost chess like.

Except it's very easy because there are only 3 or 4 options per step and really only one of those options continues the ladder. So it's this position where a chess-like tree breaks out in the game of Go but far simpler.

You still need to play Go (determining the strength of the overall board and evaluate if the ladder is worth it or if ladder breaker moves are possible/reasonable). But for strictly the ladder it's a simple and somewhat tedious calculation lasting about 20 or so turns on the average.

--------

The thing about ladders is that no one actually plays out a ladder. They just sit there on the board because it's rare for it to play to both players advantages (ladders are sharp: they either favor white or black by significant margins).

So as, say Black, is losing the ladder, Black will NEVER play the ladder. But needs to remember that the ladder is there for the rest of the game.

A ladder breaker is when Black places a piece that maybe in 15 turns (or later) will win the ladder (often while accomplishing something else). So after a ladder breaker, Black is winning the ladder and White should never play the ladder.

So the threat of the ladder breaker changes the game and position severely in ways that can only be seen in the far far future, dozens or even a hundred turns from now. It's outside the realm of computer calculations but yet feasible for humans to understand the implications.

[tasuki]

I'd argue it's clear why it's hard for a neural net to figure out.

A ladder is a kind of a mechanical one-way sequence which is quite long to read out. This is easy for humans (it's a one-way street!) but hard for AI (the MCTS prefers to search wide rather than deep). It is easy to tell the neural net as one of its inputs eg "this ladder works" or "this ladder doesn't work" -- in fact that's exactly what KataGo does.

See the pictures for more details about ladders: https://senseis.xmp.net/?Ladder

[dragontamer]

Doesn't MCTS deeply AND broadly search though?

Traditional MCTS searches all the way to endgame and estimates how the current position leads to either win or loss. I'm not sure what the latest and greatest is but those % chance to win numbers are literally a search result over possible endgames IIRC.

I guess I'd assume that MCTS should see ladders and play at least some of them out.

[immibis]

I don't know that much about MCTS, but I'd think that since a ladder requires dozens of moves in a row before making any real difference to either player's position, they just don't get sampled if you are sampling randomly and don't know about ladders. You might find that all sampled positions lead to you losing the ladder, so you might as well spend the moves capturing some of your opponent's stones elsewhere?

[tasuki]

The short ones, sure. The long ones, it's hard for pure MCTS to... keep the ladder straight?

[earnestinger]

https://senseis.xmp.net/?Ladder

(Kind of like wikipedia for go players)

[erikerikson]

Some of our neutral networks learned ladders. You forgot the "a" standing for artificial. Even so amended, "never"? Good luck betting on that belief.