Plausible move generator

[Jorge Garcia]

Hi All,

Recently I have taken a glance on an abstract written by Reijer Grimbergen talking about the possibility of making a selective move generator, here I transcript some parts of the abstract, has somebody tried a similar approach on their engine? thanks for the feedback.

Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi, Reijer Grimbergen

In games where the number of legal moves is too high, it is not possible to do full-width search to a depth sufficient for good play. Plausible move generation (PMG) is an important search alternative in such domains. In this paper we propose a new method for plausible move generation in shogi. During move generation, Move Merit Analysis (MMA) gives a value to each move based on the plausible move generator(s) that generated the move. These values can be used for different cut-off schemes. We investigate the following alternatives: 1) Keep all moves with a positive MMA value; 2) Order the moves according to their MMA value and use cut-off thresholds to keep the best N moves. PMG with MMA and cut-off thresholds can save between 46% and 68% of the total number of legal moves with an accuracy between 99% and 93%. Tests show that all versions of shogi programs using PMG with MMA outperform an equivalent shogi program using full-width search. It is also shown that MMA is vital for our approach. Plausible move generation with MMA performs much better than plausible move generation without MMA. Cut-off thresholds improve the performance for N = 20 or N = 30.

[diep]

Hi All,

Recently I have taken a glance on an abstract written by Reijer Grimbergen talking about the possibility of making a selective move generator, here I transcript some parts of the abstract, has somebody tried a similar approach on their engine? thanks for the feedback.

Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi, Reijer Grimbergen

In games where the number of legal moves is too high, it is not possible to do full-width search to a depth sufficient for good play. Plausible move generation (PMG) is an important search alternative in such domains. In this paper we propose a new method for plausible move generation in shogi. During move generation, Move Merit Analysis (MMA) gives a value to each move based on the plausible move generator(s) that generated the move. These values can be used for different cut-off schemes. We investigate the following alternatives: 1) Keep all moves with a positive MMA value; 2) Order the moves according to their MMA value and use cut-off thresholds to keep the best N moves. PMG with MMA and cut-off thresholds can save between 46% and 68% of the total number of legal moves with an accuracy between 99% and 93%. Tests show that all versions of shogi programs using PMG with MMA outperform an equivalent shogi program using full-width search. It is also shown that MMA is vital for our approach. Plausible move generation with MMA performs much better than plausible move generation without MMA. Cut-off thresholds improve the performance for N = 20 or N = 30.

Written in the 1970s?
As in 2012 this is a pathetic idea.

[syzygy]

The paper is from 2001, so it might not be representative of current top Shogi programs.

It does mention in the introduction that PMG is from the early days of chess research. Not the 70s, but the 50s and 60s. It also states that in chess it is known not to work, but that it could be useful in games in which it is impossible "with current technology" to search deep enough with standard full-width search to get a high performance program.

I suppose Shogi programs nowadays don't need to discard moves anymore without any search, as long as they apply aggressive reduction and pruning techniques.

[lucasart]

Hi All,

Recently I have taken a glance on an abstract written by Reijer Grimbergen talking about the possibility of making a selective move generator, here I transcript some parts of the abstract, has somebody tried a similar approach on their engine? thanks for the feedback.

Plausible Move Generation Using Move Merit Analysis with Cut-Off Thresholds in Shogi, Reijer Grimbergen

In games where the number of legal moves is too high, it is not possible to do full-width search to a depth sufficient for good play. Plausible move generation (PMG) is an important search alternative in such domains. In this paper we propose a new method for plausible move generation in shogi. During move generation, Move Merit Analysis (MMA) gives a value to each move based on the plausible move generator(s) that generated the move. These values can be used for different cut-off schemes. We investigate the following alternatives: 1) Keep all moves with a positive MMA value; 2) Order the moves according to their MMA value and use cut-off thresholds to keep the best N moves. PMG with MMA and cut-off thresholds can save between 46% and 68% of the total number of legal moves with an accuracy between 99% and 93%. Tests show that all versions of shogi programs using PMG with MMA outperform an equivalent shogi program using full-width search. It is also shown that MMA is vital for our approach. Plausible move generation with MMA performs much better than plausible move generation without MMA. Cut-off thresholds improve the performance for N = 20 or N = 30.

Written in the 1970s?
As in 2012 this is a pathetic idea.

+1

[PK]

Many ideas from 1970s are really bad when used as pruning, but suddenly become sensible when applied as reductions. For example MatHack6 calculated only a couple of plausible moves, modern programs don't reduce only a couple of plausible moves.

Beside that the article is about shogi, a game involving drops - which means that after exchanging three or four pieces one has to deal with about 200 moves per node. GnuShogi progressively generates less and less moves going furter away from the root. LesserKai does not, and even after doing away with hardcoded depth limit it cannot search deeper than 5 or occasionally 6 plies.

[diep]

Many ideas from 1970s are really bad when used as pruning, but suddenly become sensible when applied as reductions. For example MatHack6 calculated only a couple of plausible moves, modern programs don't reduce only a couple of plausible moves.

Beside that the article is about shogi, a game involving drops - which means that after exchanging three or four pieces one has to deal with about 200 moves per node. GnuShogi progressively generates less and less moves going furter away from the root. LesserKai does not, and even after doing away with hardcoded depth limit it cannot search deeper than 5 or occasionally 6 plies.

Best example is Paradise. Written in a functional language. I have the code printed on paper here, it was published.

That was 1979.

It has a plausible move generator and in this manner tries to find tactics. So there is no depth limited search at all.

Note that it is also a good example on how functional languages overshoot their target.

Arguably one of the ideas mentionned in the description of Paradise we know nowadays as nullmove.

[Jorge Garcia]

Thanks for the info Vincent, I was trying to write a plausible move generator approach in toga, but at least nothing remarcable to say. May be it's not a good idea, but I think it could be a different approach on writing an engine...

[diep]

Thanks for the info Vincent, I was trying to write a plausible move generator approach in toga, but at least nothing remarcable to say. May be it's not a good idea, but I think it could be a different approach on writing an engine...

It implies in this context to not search the other moves at all.

It is David E Wilkins who is the author of the paper.

Though i'm in my office now i can't find the paper - probably still in a moving box it is. From memory i say it was published in 1979.

If you look at the huge tactical code he wrote it's very impressive piece of work. The move selection was only intended to find tactics - back then tactics was everything of course. Then we consider how many tricks it missed, it's obvious that a brute force search is total beating this approach.

In that sense Paradise was one of those very important attempts to implement chessknowledge, in this case in order to search.

Note that Paradise AFAIK couldn't play games - it just was an attempt to find tactical tricks at the win at chess positions. From memory i say it solved about half.

If you would implement chessknowledge now to order moves better or to get algorithms better to work - i'm sure it can work.

That's something different from functions that select moves and throw away the rest. Selecting moves to try and throwing away the rest as a main mechamism is from the 70s and before

It's what we call a B* search, whereas all of todays engines are family of A*.

On the wikipages there is a link to shannon's original article. Note it's most interesting that as a reference he gives a dutch research which was written in Dutch in 1946 by De Groot.

http://archive.computerhistory.org/proj ... 303002.pdf

Basically the selectivity applied today proves my lemma from the 90s that there is a tactical barrier you have to cross after which a much deeper tactical search is no longer beneficial.

That's why all the reductions and other forms of shortening some of the paths all work now, instead that we have to search fullwidth.

[syzygy]

That's why all the reductions and other forms of shortening some of the paths all work now, instead that we have to search fullwidth.

Stockfish already plays a very strong game on hardware that lets it search just 50-70knps, so I think today's approach could already have worked very well at the end of the 90s or even earlier.

[diep]

That's why all the reductions and other forms of shortening some of the paths all work now, instead that we have to search fullwidth.

Stockfish already plays a very strong game on hardware that lets it search just 50-70knps, so I think today's approach could already have worked very well at the end of the 90s or even earlier.

That's why i started with reductions in the 90s.

World champs 1999 Diep used reductions.

That's why it got 20 ply in some endgames at bob's quad box with still quite some pieces on the board.

Diep searched 70k nps at it (GCC back then was not so great you know).

I can't remember anyone else got 20 ply back then. I saw DeepFritz world champs 1999 get 17 plies, yet it didn't get deeper in endgame than that as well. So in middlegame it really outsearched Diep, basically nps wise, yet no chance in endgame search depth wise.

As it appears of course, Ed Schroder already used reductions already years before that...

I don't think it matters which of todays programs you take. They'd all win world champs 1997 really hands down with a 100% score of course.

That's software progress. Yet i do not believe the search is the biggest reason for that.

If you would use todays Stockfish search and use evaluation function of the popular program back then. Say Crafty or Gnuchess (so deliberately NOT nimzo98 which is a year later anyway) and then play that with search back then from say Diep 1998 which didn't have reductions yet, yet just was using R=3 nullmove and good working hashtables, then equip Diep 1998 with todays evaluation function of Diep.

You win everything of course with that Diep then.

It's evaluation function that wins everything.

I did do this test already back in the year 2000 at Jan Louwman's 36 computers. I played at 18 autoplayers a match then with Diep 2000 against old engines from 90s.

Back then i was total shocked to learn that the old engines, still in my mind strong, got total hammered with 100% scores.

It was slaughter. Software progresses so much every few years - using something that's strong today back at hardware from back then and then play against engines from back then is gonna win everything.

This because the hardware from back then is pretty capable - yet realize clearly - how fair would such contest be?

It's like letting a german fighter from world war 2 do a dogfight with a F22.

Such contest has pretty much the same outcome...

Therefore much of what we see today is not so interesting of using hardware at time controls which effectively gives the same number of nodes a search like i did get world champs 1999 at Bob's quad Xeon.

Interesting today is using modern hardware at slow time controls so that we see how it is doing in todays society instead of the usual 'blast from the past' contests which go about nothing.

Please note that the manufacturers aren't serving us well lately. The ivy bridge nonsense you can buy in the shops now has just 4 cores. Where is the hardware progress?

It's mostly in the server hardware now that progresses...

You can build relative cheap now from parts of ebay a 48 core AMD machine for around 3k euro. Using for example the 6180 SE processor (though it got up at ebay a tad).

That's 48 cores.

However no 'tester' is using for his elorating lists such hardware currently... ..they all use at most a core or 4 at fast time controls.

Where is progress in computerchess there?