The program that beat Kasparov avoided a full breadth first search because it was fairly easy to decide if something was a bad move. So, it could generally pick from a fairly small number of moves when branching. What makes GO so much harder than chess is how hard it is to evaluate the board and decide if a move is good or bad.

>What makes GO so much harder than chess is how hard it is to evaluate the board.

And the 300-fold increase in branching factor.

First order branching factor is less important than you might think.

You could setup a game of Nim: https://en.wikipedia.org/wiki/Nim with much higher branching factor vs Go, but because you can trivially separate a winning moves vs. losing moves those branches become irrelevant in Nim. AKA, if there are 2,000 winning moves then they are all equivalent.

Deep Blue wasn't a full brute-force search, and AlphaGo does perform plenty of brute-force searching too.