dynamically modified evaluation function

[Don]

In another thread (in the general topics forum) the idea of modifying the piece square tables during the search itself came up. The idea was based on using the history information to somehow make the piece square table more relevant to the position being searched.

One observation concerning this is that the history table can be a more accurate predictor of move quality than a static evaluation function call. For example most evaluation functions will always believe Rd1d7 is a good move but the history tables can show that this move has not had good success, perhaps it always get attacked by a bishop or knight for instance.

I wonder if this concept can be generalized. I'm just dreaming here - I have no concrete proposal, but an intriguing idea is to have a program that generates it's own evaluation function (from scratch) based on things learned during the search. It would be as if the evaluation function is created specifically for each starting position.

In modern computer go programs there is NO evaluation function as such - the value of each playable move is determined dynamically via monte carlo simulations. The moves that seem to work best get tried more. So it's not a completely ridiculous idea as this is working far better in GO currently than alpha/beta searching with a traditional evaluation function.

One could start with an already good evaluation function and modify it on the fly or perhaps actually try to generate one from scratch.

In computer go, domain specific knowledge is still important and used to guide the random play-outs these program perform.

A chess program is easily capable of playing hundreds or perhaps thousands of games per second too - especially if they are designed and optimized specifically for this kind of thing.

Any ideas?

[Antonio Torrecillas]

the refered thread http://talkchess.com/forum/viewtopic.ph ... 66&t=37012

[Daniel Shawul]

Pre-calculated tables are very bad sources of search instability. Fritz 5 had pre-calculated piece square tables IIRC (not from history though), before starting each iteration. I read in the other post , new pst tables in every iteration ? well i can't imagine how much instability the hash table can introduce.
Use of history for move ordering is good as it is

[Antonio Torrecillas]

My first experiment on this, was to construct a pst specific for some tipical mid game positions. From the starting position, I do a long search and stored the resulting history table. Then I constructed the pst with this data. An evaluation with just this pst + material, was as good as the initial program, but only up to the depth the tuning search got us. So this term just reflect the information already found so far.

Move ordering is also a kind of hidden evaluation, so there is an overlap between a pst constructed on fly from history tables and the ordering by history table.

[Don]

Pre-calculated tables are very bad sources of search instability. Fritz 5 had pre-calculated piece square tables IIRC (not from history though), before starting each iteration. I read in the other post , new pst tables in every iteration ? well i can't imagine how much instability the hash table can introduce.
Use of history for move ordering is good as it is

It will require a lot more imagination than this. I don't want to think in terms of why it won't work, but what would be required to possibly make it work.

It's a very speculative long shot idea, but it's more like we (humans) think. In our analysis of a position we pick up ideas, noticing things that might work or not work and in my opinion we use this to dynamically alter our own evaluation functions and act as plausible move generators.

I have had that eureka moment in my own games where I happen to notice that some normally ordinary move is actually quite devastating to the opponent, and suddenly I'm searching for ways to get that move in and it becomes (for this game only) a thematic concept. I don't see any reason why a computer has to be so ridiculously static about it's notions of what is good and bad.

[Daniel Shawul]

Search instability is often something that tends to be neglected, which
I belive in this case is very serious. You are trying to incorporate
a dynamic term in to static evaluation. And this dynamic term is not constant,
unlike the case where some incorporate a static exchange evaluation (SEE) f.i.
That one is completely dependent on the position of the pieces.

Also we are talking about zero window searches (PVS & MTD), so the slightest change
in eval term means immediate introduction of instablility every time the eval is
updated with history info. Even something like "side to move" bonus has been discussed here
as a serious cause of search instablity for a null move search.

I don't want to sound too pessimistic but search instablity is a serious issue
that should be consdidered, whenever dynamic & static terms are mixed.

[Daniel Shawul]

Move ordering is also a kind of hidden evaluation, so there is an overlap between a pst constructed on fly from history tables and the ordering by history table.

I don't think so. If you use brute force and search all moves, move ordering doesn't matter. The result will be the same. But if you change eval terms , you get different results.

[Antonio Torrecillas]

Quote:

Move ordering is also a kind of hidden evaluation, so there is an overlap between a pst constructed on fly from history tables and the ordering by history table.

I don't think so. If you use brute force and search all moves, move ordering doesn't matter. The result will be the same. But if you change eval terms , you get different results.

a search tell you: there is no better than this PV, but you can have equal scores so the order is relevant and it say wich is the best move.(the first in this particular case).

[Michael Sherwin]

In another thread (in the general topics forum) the idea of modifying the piece square tables during the search itself came up. The idea was based on using the history information to somehow make the piece square table more relevant to the position being searched.

One observation concerning this is that the history table can be a more accurate predictor of move quality than a static evaluation function call. For example most evaluation functions will always believe Rd1d7 is a good move but the history tables can show that this move has not had good success, perhaps it always get attacked by a bishop or knight for instance.

I wonder if this concept can be generalized. I'm just dreaming here - I have no concrete proposal, but an intriguing idea is to have a program that generates it's own evaluation function (from scratch) based on things learned during the search. It would be as if the evaluation function is created specifically for each starting position.

In modern computer go programs there is NO evaluation function as such - the value of each playable move is determined dynamically via monte carlo simulations. The moves that seem to work best get tried more. So it's not a completely ridiculous idea as this is working far better in GO currently than alpha/beta searching with a traditional evaluation function.

One could start with an already good evaluation function and modify it on the fly or perhaps actually try to generate one from scratch.

In computer go, domain specific knowledge is still important and used to guide the random play-outs these program perform.

A chess program is easily capable of playing hundreds or perhaps thousands of games per second too - especially if they are designed and optimized specifically for this kind of thing.

Any ideas?

This is another idea that I posted about years ago. It is being used in RomiChessP3k with advantage. RomiChessP3k is now 3 years old.

EDIT:

Posted: Sat Apr 28, 2007 5:48 am Post subject: RomiChessNG1 vs. Hamsters 0.2
There is a new RomiChess beta in both 32 bit and 64 bit versions ready to be tested. This beta has something new in it that as far as I know has never been done before! It has a search/eval that evolves with each iteration of the search. Values from a special history table are used to 'evolve' (tune) the eval after each iteration which in theory not only makes the eval more accurate it also results in a faster search as the eval and search work better together. A circular feedback loop is created between the two. It is still in the very early stages of development, however, the results so far are very promising.

Useing my set of 50 positions (Sherwin50.pgn) the last series of betas known as Death Kitty 1 thru 6 were only able to achieve 55% vs. Hamsters 0.2. Death Kitty was not able to handle these new tougher, heavily armored, mechanized Hamsters! So I sent Romi to ninja school!

Actually my new beta naming scheme is rather flexible. RomiChessNG stands for, if Romi does bad--RomiChess No Good, if RomiChess does good--RomiChess Ninja Girl!

This betas first test was a Ninja Girl result!

Even if the following result had not been nearly so good I would still have been very happy as the change in playing style has changed in a very dramatic and positive way!

[Daniel Shawul]

If you have equal scores , none is better than the other We just happen to pick the one that we searched first . Multi-pv will say both are equal. Also this case is very rare, no ?