New Search Method(s)

[lucasart]

Code: Select all

     if(a != 0 || 1 || 2 ||3 || 4 ||5 || 6 || 7||8||9||10||11||12||13||14||15||
     16||17||18||19||20||21||22||23||24||25||26||27||28||29||30||31||32||33||34||35||
     36||37||38||39||40||41||42||43||44||45||46||47||48||49||50||51||52||53||54||55||56||
     57||58||59){

     a = 0;
     }

Your code is wrong in so many ways. I picked that piece just as an illustration of how little programming you know. You need to learn how to program for another 5 years or so before you can make any significant contribution to this field. Perhaps I am being generous.

Please, stop wasting our time.

100% agreed !

I've never seen such a horrible code in my life... Not only it makes no sense at all and is wrong, but even if it did compile and do anything at all, it's so badly written and illegible that it's not even worth the bytes it's using on your hard drive...

So Joshua, before questionning advanced methods of computer chess that you will never understand until you code them yourself... Just program an engine that can play a game of chess. And you will see for yourself why your revolutionnary approach will never work (millions have tried and failed before you, so accept with humility what the community has to teach you before trying to teach them what you dont know!)

[Don]

Hi Joshua,

Don't let the comments discourage you. Take what you have and try to build a simple chess playing program out of it, one that does not search but finds a move heuristically. This is a good exercise because it will help you determine what issues are involved in selecting a good move and you will have great fun in doing this.

But here is what I think you will discover. You will continue to make rules that prevent blunders. It will be all about tactics. I assume that you want to find moves in master style, based on plans and what the position calls for. But every game is going to be overwhelmed by tactically issues. Still, consider it a success of sorts if you manage to make it play moves that look attractive most of the time and can compete with a 1 or 2 ply search from a strong chess program. (I suspect you will find this very difficult to do without a search.)

Since you are looking at things from a completely different point of view there is always a good chance that you can learn something that could be applied to a "regular" chess program, perhaps discovering simple tactical rules that helps a lot but is not obvious, something that could be integrated into a typical chess program as an evaluation feature or extension.

After doing this you will likely become dissatisfied with the code (I always feel this way about my code) and may want to start again from scratch. Figure out what needs to change and don't be afraid to start over, even more than once. That will make you a better programmer.

By the way, you didn't do everything wrong, it was obvious for instance that you tried to lay out the code to be understandable and you chose easy to understand names for variables and such. Keep up that good practice.

Here are a couple of tips - just a couple so as not to overwhelm you:

In general you don't want to call external programs using the system call when you can easily write your own pause function. You should figure out how to do that.

You almost always want to use an array to represent sets of things (or some other other data structure but let's keep it simple.) The chess board should be some sort of array for instance. Chessprogramming wiki gives good examples of data structures to use for representing the chess position.

The sample code snippet someone posted may not do what you thought. It's the one that says, "if(a != 0 || 1 || 2 ...." That statement will always be true and you could have just said, "a = 0" but I don't think you meant that. Did you mean: if (a < 60) { a = 0; } ??

[AlvaroBegue]

Don, now everyone can see which of us is the teacher. Or perhaps you are just a better person than I am.

[Don]

Don, now everyone can see which of us is the teacher. Or perhaps you are just a better person than I am.

I think I have posted way more negative posts that you have, I don't think that way at all.

[bhlangonijr]

Don, now everyone can see which of us is the teacher. Or perhaps you are just a better person than I am.

I think I have posted way more negative posts that you have, I don't think that way at all.

I think he (Joshua) has a point - the original post. Although I think he could be more cautious before posting his first attempts.

Anyway, good post Don.

Regards,

[diep]

It's time to head in another direction for search methods. Alpha/Beta has been milked dry. The human mind is the most powerful "computer"... why not try to be like it with computer chess?

When asked how many moves ahead Kasparov can think, he replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

The normal GM searches a few moves per second, while a chess engine searches millions per second. See the difference?

Search()->

30+ conditions for root.

Conditions:

What type of move are you?

1) Developing (including castling)
2) Exchange
3) Sacrafice
4) Fork
5) Pin
6) Discovery (check, attack)
7) Skewer
8) Tempo
9) Mate (Threat)
10) Draw (Repeat)
11) Mobility
12) Positional
13) Attacking
14) Defensive/Protective
15) Capture
16) Open rank
17) Open file
18) Open diagonal
19) Castled or Not Castled or Capable of Castling
20) Castling stopping
21) Controling squares
22) Attacking squares
23) Free squares
24) Occupied squares
25) King Safety
26) Safe/Retreat squares
27) Supporting
28) Attack Supporting
29) Capture Supporting
30) Pin Supporting
31) Center Control
32) Other

Order your root move based on the total count of conditions met, bonus, penalty, etc.

To be more successful at Chess, an engine or individual should take these conditions into consideration for a move. Planning is a key to winning. Design & develop a search for just the 3 basic attacks would be a good place to start (forks, pins, & skewers). This will lead to the removal of piece table scores, and if done correctly, alpha/beta. Also, more human-like play will occur.

This would be a step forward for chess.

If i speak for myself, just a simple FM, achieving 12-14 moves is not so complicated when i take time. Of course you miss all sorts of things. That's a ply or 25.

As for this saturday where i had an average game with many mistakes, i missed of course 1 small thing, but after that i did do well in the endgame.

Some 20 plies i really achieved there, though it never came on the board what i calculated. Usually when your opponent sees the same, he's not gonna play that (which is why i choose for that).

Kasparov really is another league there. There is hard evidence he achieved in one game a move or 22 (44 ply), from which many moves were not really forced. Had he not seen the last few moves, he would for sure not have chosen for that line. It was not a lucky shot and later also got confirmed by Kasparov he saw it (many GM's take of course too easily credit they 'did see it', where usually they play things based upon a feeling).

The level is really different, because at this 2600+, in this case even 2800+ level they KNOW they didn't make any major mistake, not even small mistake, so they KNOW that after an obvious weird move of their opponent, that their combination is going to work out fine most likely.

If you make no big blunders and play a great game, tactics you go into simply will work fine, as there will be some refutation you can find for this odd move the opponent played, without that there is tactics for him that works against you.

So that is another level, i seldom have games like that. Just sometimes i have a game like that.

This directly also gives the big problem in finding a search method that is close to the human top players.

alfabeta is unbeatable as a search algorithm. Adding more (correct) forms of selectivity might work however. everyone probably has tried everything there. End 2004, start 2005, i really have tried a lot of selectivity algorithms, but it is really tricky to get to something that gives you some sort of elo.

Vincent

[diep]

Hi Joshua,

Don't let the comments discourage you. Take what you have and try to build a simple chess playing program out of it, one that does not search but finds a move heuristically. This is a good exercise because it will help you determine what issues are involved in selecting a good move and you will have great fun in doing this.

But here is what I think you will discover. You will continue to make rules that prevent blunders. It will be all about tactics. I assume that you want to find moves in master style, based on plans and what the position calls for. But every game is going to be overwhelmed by tactically issues. Still, consider it a success of sorts if you manage to make it play moves that look attractive most of the time and can compete with a 1 or 2 ply search from a strong chess program. (I suspect you will find this very difficult to do without a search.)

Since you are looking at things from a completely different point of view there is always a good chance that you can learn something that could be applied to a "regular" chess program, perhaps discovering simple tactical rules that helps a lot but is not obvious, something that could be integrated into a typical chess program as an evaluation feature or extension.

There was a program called Paradise which exactly is doing what gets proposed here. It was written in a functional programming language and i did checkout the program bigtime.

So where we completely agree of course on the principle that brute force always wins it, it is completely unclear what to do the last few plies of the search.

Rybka simply is doing the same what 9 years ago already got done by Omid David Tabibi, namely a hard form of razoring using a pawn window.

This misses a lot of tactics.

Yet to quote Frans Morsch on the last few plies: "if you get that huge nps you simply don't have the system time to be clever".

So for Rybka & clones this is the case.

Yet for the Diep type engines selecting a bunch of moves, instead of doing an expensive nullmove, might be very interesting those last few plies.

A big problem thereby is the positional score swings.

For example picking up a pawn at a7 is maybe improving the evaluation by 0.2 pawn, but moving a knight from a3 to c4, so from the edge of the board to the semi-center, might improve the evaluation function 1.5 pawn.

So the big question is: what do we want to pick up last few plies and how selective do we want to be there?

What i already experiment since 2004, start 2005, so before Rybka had it, was a nullmove where the reduction factor is dependant upon the difference between eval and beta.

I used 0.5 pawn there, Rybka uses 1.0 pawn there; so:

if( eval >= beta + 0.5 ) then R=4; else R=3;

That's the nullmove reduction factor. I used it basically for the last few plies, as the overhead from nullmoves in the mainsearch already is such a tiny fraction of nodes that going to R=4 there wasn't worth it back then (diep didn't search so deep back then).

Yet all this is really primitive. So having some chessknowledge based upon which you do a better job the last few plies, is a real interesting research question.

I'd argue that it is a fulltime job to be busy with it though, which is why i didn't really research it after the failed experiment of 2005.

I really lost nearly a full year to experiments from short after world champs 2004 until world champs 2005, trying to really search plies deeper with Diep using dubious search methods. Yet it gave a lot of insights and also produced some ideas from which i still feel they could work.

After doing this you will likely become dissatisfied with the code (I always feel this way about my code) and may want to start again from scratch. Figure out what needs to change and don't be afraid to start over, even more than once. That will make you a better programmer.

By the way, you didn't do everything wrong, it was obvious for instance that you tried to lay out the code to be understandable and you chose easy to understand names for variables and such. Keep up that good practice.

Here are a couple of tips - just a couple so as not to overwhelm you:

In general you don't want to call external programs using the system call when you can easily write your own pause function. You should figure out how to do that.

You almost always want to use an array to represent sets of things (or some other other data structure but let's keep it simple.) The chess board should be some sort of array for instance. Chessprogramming wiki gives good examples of data structures to use for representing the chess position.

The sample code snippet someone posted may not do what you thought. It's the one that says, "if(a != 0 || 1 || 2 ...." That statement will always be true and you could have just said, "a = 0" but I don't think you meant that. Did you mean: if (a < 60) { a = 0; } ??

[diep]

It's time to head in another direction for search methods. Alpha/Beta has been milked dry. The human mind is the most powerful "computer"... why not try to be like it with computer chess?

When asked how many moves ahead Kasparov can think, he replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

The normal GM searches a few moves per second, while a chess engine searches millions per second. See the difference?

Search()->

30+ conditions for root.

Conditions:

What type of move are you?

1) Developing (including castling)
2) Exchange
3) Sacrafice
4) Fork
5) Pin
6) Discovery (check, attack)
7) Skewer
8) Tempo
9) Mate (Threat)
10) Draw (Repeat)
11) Mobility
12) Positional
13) Attacking
14) Defensive/Protective
15) Capture
16) Open rank
17) Open file
18) Open diagonal
19) Castled or Not Castled or Capable of Castling
20) Castling stopping
21) Controling squares
22) Attacking squares
23) Free squares
24) Occupied squares
25) King Safety
26) Safe/Retreat squares
27) Supporting
28) Attack Supporting
29) Capture Supporting
30) Pin Supporting
31) Center Control
32) Other

Order your root move based on the total count of conditions met, bonus, penalty, etc.

To be more successful at Chess, an engine or individual should take these conditions into consideration for a move. Planning is a key to winning. Design & develop a search for just the 3 basic attacks would be a good place to start (forks, pins, & skewers). This will lead to the removal of piece table scores, and if done correctly, alpha/beta. Also, more human-like play will occur.

This would be a step forward for chess.

As for the chessknowledge you write down here. In 1999 i wrote a selective search model for Diep based upon reductions. Much of the knowledge you quote here, and in fact a lot more sophisticated chesknowledge, but most of it tactical knowledge, was used to select moves.

Selected moves did not get reduced, the rest did.

So no hard forms of forward pruning. This version played in the world champs 1999 actually in that manner.

I was a bit amazed that it searched very deeply especially in far endgames, this at bob's quad xeon 400Mhz, using a very inferior GCC compiler.

Despite diep being a low nps program, it got handsdown 20 plies in endgame. No opponent even got close to that. Note not round 1 and not round 7, as then i could not access Bob's machine, for whatever weirdo reason. Had to play single core at a local machine then (which sucked ass), lost both those games. Of course Ferret was a leap better (round 1).

The reason why i stopped with the experiment is complicated to explain. Basically in the year 2000, Diep searched without any reductions anymore.

Vincent