Null move in PV

[hgm]

In games where null-moving is legal... Would you still reduce it when you search one in a PV node? Even if at that depth it would come up as the best move?

Perhaps one should only reduce when at least one other move scores above alpha?

[Rémi Coulom]

In games where null-moving is legal... Would you still reduce it when you search one in a PV node? Even if at that depth it would come up as the best move?

Perhaps one should only reduce when at least one other move scores above alpha?

IIRC, at the time when some programmers were still trying alpha-beta in Go, even ordinary null-move pruning did not work. It reduced time to depth, but it did not improve strength for the same thinking time. Probably because the depth reduction hides important long-term threats.

Rémi

[hgm]

Interesting. This is always the danger in reducing moves that fail high: that the search will start to use them as 'defense' against distant threats. So there must be some balance between how much you reduce, and how much you hasten your own demise by passing your turn, compared to optimal defense.

In Chess-like games you can usually interject some meaningless threat (like attacking a Queen with a minor) to force a two-ply attack-evasion delay of anything except checkmate. So a two-ply reduction seems justified. (That modern programs can afford larger reductions is probably because the typical delaying tactics also suffers reductions, such as LMR.)

In Go it might be more difficult to set up a threat with a single move in most positions.

[Daniel Shawul]

In games where null-moving is legal... Would you still reduce it when you search one in a PV node? Even if at that depth it would come up as the best move?

Perhaps one should only reduce when at least one other move scores above alpha?

IIRC, at the time when some programmers were still trying alpha-beta in Go, even ordinary null-move pruning did not work. It reduced time to depth, but it did not improve strength for the same thinking time. Probably because the depth reduction hides important long-term threats.

Rémi

Well null move is still considered a bad move in Go so it should work to some level despite the reduction amount. The null mover is already giving up big so the other side should be able to see some strategic advantages with in its search if not some clear tactics. I think presence of too many zugzwangs is more deterimental to the use of null move than anything else f.i checkers. Many Go programs don't try null moves in middle games since it is usually a waste of search time anyway. It is only a good move when you are left with no choices but filling your eyes. I used it in my engine before the monte-carlo version surpassed it and didn't see much problems with it to reach a 1500 or so cgos rating. It still increases the depth by 2 plies or more for 9x9 which uses heavy LMR too.

[diep]

In games where null-moving is legal... Would you still reduce it when you search one in a PV node? Even if at that depth it would come up as the best move?

Perhaps one should only reduce when at least one other move scores above alpha?

Nullmove works excellent in go.

[Rémi Coulom]

These are the computer-go messages I remembered:

http://osdir.com/ml/games.devel.go/2005 ... 00067.html
http://osdir.com/ml/games.devel.go/2005 ... 00071.html

So at least in principle traditional chess techniques work in go but
since you only can search 2 ply with a complex evaluation function all
the cool chess stuff such as null moves and transposition tables has no
impact.

Rémi

[diep]

These are the computer-go messages I remembered:

http://osdir.com/ml/games.devel.go/2005 ... 00067.html
http://osdir.com/ml/games.devel.go/2005 ... 00071.html

So at least in principle traditional chess techniques work in go but
since you only can search 2 ply with a complex evaluation function all
the cool chess stuff such as null moves and transposition tables has no
impact.

Rémi

Total BS - in 1999 i already searched 10 ply in go with a complex evaluation function with nullmove. It also had several layers of influence function which is expensive to calculate.

Some guys even have java programs there, losing factor 4 or so compared to the C engines we got.

What some did do back then is have a local tactical search that searched in ASSEMBLER to estimate alive & death of groups at a specific edge of the board; of course that then limits the speed of the 'huge evaluation function'.

This is total nonsense postings. these guys just don't know how to search in go - not the same superbrilliant guys who worked on chess worked so far on go of course, otherwise within a year or 5 from now go engines would be stronger than chess engines.

Go is an ideal game to design magnificent selective searching engines for - most moves really are total nonsense to consider, so you can selective deepen specific moves in a manner that's total impossible in chess.

Total board evaluation is seemingly slower in go- but that's again not true. In 99 i made an incremental datastructure that incremental updates which stones are connected to which and therefore form groups. If you update alive and death incremental it's suddenly very rapid, just like chess.

Claims on 2 ply is therefore total nonsense. We can hard prune about 90% of all moves so to speak. Most engines until recently did do HARD PRUNING in the root.

So just *not* considering majority of the moves *ever* in root.

You wonder why monte carlo and what you've been busy with yourself beated them?

These guys didn't consider specific moves at all!

You don't need to search such moves deep of course, but hard pruning everything is not so clever as it seems.

So a 2 ply search if we do it at end of a search is going to be similar tree size like in chess.

Nullmove works *way better* in go than in chess.

Getting 30 ply there in a selective manner is pretty easy in go, just in theory, in practice it's of course hard work.

But it's total obvious the algorithmic brilliant never worked in computer-go.

the reason i quitted my go-engine is the total lack of support from the go community itself. I asked around if someone could help me with some go knowledge at the time - and after 1 year of no one responding (actually 1 response i had of a guy in Netherlands who was prepared to 'sometimes play a few test games'), and after me reading a few go books, i realized the problem was good go knowledge.

The go books written by a 9 dan i have here, you can burn those books directly. Total nonsense.

here is one: Ma Xiaochun, 9 dan.

"the thirty-six stratagems applied to go"
I had a few of those books.

The title of the stratagems seem smart clever and nice. Then you go read and basically he advices to ATTACK the enemy at his strongest point.

In chess that's total stupid. You of course attack where your opponent is weak. Preferably you first chop off a hand that's wounded a tad already.

Just to be sure go isn't a total different game than chess i asked a strong go player (not sure, 5 dan or so). He confirmed exactly what i thought. In go you also should NEVER attack where your enemy is strong.

In this sense the Asian theory is even worse than what the chess GM's wrote down, which also already can be put in the famous library of the forgotten who didn't know how to factorize which pattern causes the advantage in a given position.

Go is even worse there. And other than this you have real little, as they don't annotate their moves. Asian culture in combination with no evidence of what happens is the ideal mixture for fairy tales - but at the end of it you still don't have the knowledge needed to make that good move ordering, total crucial to get a strong program.

Doing that go suddenly is a simple game, also at a 19x19 board, with todays computing power, as that's of course a total necessity - you DO need big computational power - no discussions there.

Having that, you selectively can see tactical way more in go than you can in chess, as in chess you can search very selective but not *that* selective like go, as statistics simply are telling the reality in chess and in go, and in go it's far easier to kick out silly moves out of your 'selection maybe to not reduce too much'.

You don't use an actual movelist in go of course. You directly hammer it down. In that manner your effective nps is higher than in chess and selectively hitting 40-50 ply is EASY (ladders not counted of course).

The easiest proof on how silly they used to be in computer go, prior to Monte Carlo and especially UCT type techniques getting introduced, is that if you gave the go engines more time, they actually played worse, not better.

You know that's some hard truth about those go engines a few years ago - that's telling the ENTIRE story.

No wonder that a few computer chess guys back then, especially those bad in chess, not to mention go, thought: "we can easily beat the crap out of all these go programmers - these engines PLAY WORSE with more time AND they prune in hard manners everywhere". The guys thinking like that GCP, Chrilly Donninger, SMK and another few. Well we saw what happened.

GCP, according to himself with just 6 months work, had worlds number 1 engine on the PC, won tournaments with it. And he sold... he sold... less than what you can buy a ticket for to Japan... ...just like i had warned him for.

So he quitted computer-go directly then.

If you don't speak Japanese yourself, writing a go engine is not very clever (except when you got a sponsor).

It's possible there, using some go knowledge, to make a magnificent engine that beats the crap out of everyone.

Saying that: "but you could play a human and win big cash with that", that's not true. First of all that was limited time fram.e Secondly, even if you would've made it within that time frame, you simply wouldn't have gotten the match - too many ways out for the go players and the sponsor of that match.

Third - you have the deep blue problem then. You build something for 1 specific goal, you reach your goal, then no one is interested anymore...

Further you'd need several matches of course to really beat. You don't manage a project like this within 1 or 2 years and each time that's how their bet works. They bet ahead just a few years. Not 5 let alone 10. And they have 100 ways to get rid of the bet without contractual sureness that you can actually show up and beat the guy.

We had a computer beat Kasparov back in 1989 already. Deep Blue won by contract as it seems, games were ugly, far underneath FM level (5 - 6 blunders a game - sorry i can make less than that). Only past few years ago it got really tough for GM's to play computers. Still it's not 100% clear as Gm's enjoy a major openings advantage.

I remember testing world champs books against some GM's doing preparation for top GM's - they total hammered the book. Out of 20 attempts all 20 ended in big advantage, bot hwhite and black, for the GM side. ON average around a +2 to +3 advantage resulting. So not just a 'pawn up' or so. Just game over.

That's the advantage Topalov had with those seconds.

So you need more than just a 1 million dollar prize with 100 ways out of the contest.

If you work hard a few years you make 1 million anyway.. ..in a more sure manner.

This huge difference computerchess and computer-go will always remain - the Japanese market is simply too closed.

Note that go is the ideal game for supercomputers because of the long time controls such official matches use.

[diep]

Another big problem of computer-go is the 'say nothing' culture.

I was for years on the computer-go mailing list. then the most interesting scandal to follow, namely a Korean program which had cloned a commercial programs go knowledge and became world champion with it, there was 0 postings about on the mailing list.

years later i had to find out by word of mouth at an ICGA meeting about this.

You hear nothing useful there. Yeah that a few go programs use 32 bits Zobrist for their hashtable...

That's the type of level these guys have

You like to compete there?
That's not interesting without payment.
To use a Dutch saying: "One-eyed in the land of the blind..."

Note that in complexity go is not simpler or more difficult than chess. The goal is to beat others, not to solve the game.

Beating others is the same problem. It's a real game.
Yet that game you can only play if you speak Japanese, or form a team with someone who speaks Japanese.

Otherwise it's not interesting, that was my conclusion back in 90s, and it still is.

Right now my viewpoint also changed. More like that of GCP but then in realistic manner - it has to get paid. I speak probably for most genius algorithmic guys there.

So in computer-go one has to wait for that computer-go programmer that is total genius algorithmic who is going to lay the base ideas on which moves to selective search and how and how to get real deep in a selective manner without too much randomness.

This is total different and provable on paper more effective than UCT/ Monte Carlo of course, yet it's obvious that this has given the big wake up call in the computer-go community. Someone had to do that. And not surprisingly it was a few computerchess guys who did do so.

[diep]

To give some indication, what would work very genius in go.

First a note on nullmove. basically a nullmove is legal but it also terminates the game for you. Good players will simply play as their last move a nullmove.

So nullmove is our basic pruning algorithm in innernodes. It works far more effective in go than in chess. Reduction factor also far bigger than in chess, reduction factor real quick you let it go up to R=8 or so; of course dependant upon the maximum reduction for normal moves as well.

Then we can do something that won't work in chess which might work pretty great.

We don't use LMR but a more classical system. Each move belongs to a specific group that defines its reduction.

Now we just search to the full depth the best move, if any makes the selection, which means normal reduction 1 unit.

We have at most 1 or 2 moves with reduction 2.

And all the real stupid moves we reduce 8 units. It's possible after some parameter tuning yo ufigure out you can reduce a specific group 16 units.

That's more likely than 8.

So you see 95% of the moves belong in the group 8-16 units.

That 5% is obviously more than 3-4 moves. So we have then a handful of moves that's gonna get reduced more than 2 units and less than 8.

Say most 4 units.

Obviously from hashtable we learn which moves are great and should be tried first and also how great they are.

Of course we use big knowledge on alive and death endangered groups and the quality of that knowledge will determine our succes.

I hope though you realize how deep a search like this is gonna get in go, especially parallellized.

The pittfall in this approach is that one really can only have 1 move reduced 1 unit and very few moves of 2 units. This selection really must be limited in order to search real deep in go. In short the code to select must be excellent go knowledge quality. It's far more important than in chess there.

Parallellization is the same problem like in chess with the above algorithm, and i could calculate in chess at 500 cpu's as well, with near to no testing on the 500 cpu partition. Simply 0 games were played.

Getting in this manner 40-50 ply is gonna be possible and you see tactics fantastic deep, as all tactics are in positions where things are nearly semi-forced in order to avoid losing ground.

He has to put on square X or Y in order to not lose ground, and the rest of the board is total irrelevant. Your pattern knowledge with sureness selects this move to be tried to the full depth.

Spectacular high % of 'selecting best move as first' you get in go. Easily 98%. That would be the result of good knowledge to select which moves to try.

Tactical this is at much higher level than any chess engine is now. We saw this in 10x10 checkers as well.

Initially the programs were at much lower level than chess engines, as 10x10 international checkerplayers simply could read much deeper than the engines.

Then sudden boom there and total over.

Go is similar in that sense. the way to not lose ground in local dogfights is so dominant that a computer can more accurately read this ahead with 100% sureness. In go machines can total dominate humankind there in a manner that's not even funny.

The real difficulty is getting the knowledge strategically correct for the openingsposition, namely an empty board. Don't underestimate this problem, it's much harder than most guess here. This is the big challenge and determines how fast you can beat the strongest professional players.

Let's however sum it all up:

a) right now there is no one with this search in computer-go
b) let alone in a parallellized manner - and you sure need big crunching in order for this search to have effect

You'd basically need diep's parallel search

c) need for a good evaluation function with good tuned strategic weights for openings position (empty board)

d) not only you need a good evaluatio nfunction, you need to write speedy code for it as well - i get the impression most have NO IDEA how to do this in go - some of the actual 'top programmers' there. A good example is the influence function. To large extend you can do that incremental and no one is doing that AFAIK.

In all this nullmove works fantastic and total dominates, much more than in chess.