How many plys without pruning?

[hgm]

Just to diagnose what the problem could be: How do you generate moves? Do you use a piece list? What language are you programming in anyway?

[Ralf Müller]

The language is C++
I don't use Piece-Lists, my board representation is square-centric.

So far I see, only legal moves are generated.

[hgm]

Not having a piece list requires a scan over the entire board to find your own pieces, which is a source of inefficiency, as even in the most favorable situation only 25% of the squares will contain one of your pieces.

If your move generator tests all move for legality to weed out the ones that put your King in check, it wastes a lot of time, because in about half the nodes only the first move will be searched to produce a cutoff. So you would have tested the other 40 moves for legality to no effect. A better design is to postpone legality testing to when you actually want to play the move (because all earlier moves failed low, or proved illegal).

[Ralf Müller]

Ok, many thanks for your help.

Do you think, I can fix this things in the source code or should I start from scratch?

Because a start from scratch would be to difficult for me, since I'm no good programmer.

[Sven]

Ok, many thanks for your help.

Do you think, I can fix this things in the source code or should I start from scratch?

Because a start from scratch would be to difficult for me, since I'm no good programmer.

Hi Ralf,

I think you should not worry too much about speed issues in the beginning. Think of:
1) correctness,
2) a good search with an acceptable branching factor,
3) testing!

Trying to change basic data structures of a chess program you initially did not write on your own may or may not work, but definitely it will not change much the situation you have described: your engine searching about 6 plies in few seconds. This is all about the branching factor (and possible bugs, of course). Move ordering is essential, killer moves and hash table are standard as well. Especially implementing the latter takes time. So don't start by trying to improve NPS, you will be disappointed about the result.

Starting from scratch is of course an option which you have at any point in time. In your case I would start with the code you have, and try to understand what happens and whether bugs or lack of features (or both) explains its current behaviour. Try to improve it step by step, and see what is possible with this code base.

As someone else wrote, I'd also suggest to reduce the evaluation to a minimum in the beginning: material + perhaps piece square table. Comment out all other positional evaluation features, and concentrate on the three items above. You can add eval features later when you have a decent search.

Furthermore, define your goals and try to check which of these are realistic for you. (A possible goal might be "learning"!) Writing or maintaining a chess engine is not a trivial task, and will require a lot of patience. You'll never get a strong chess engine "for free", unless you copy someone else's work.

Sven

[valdiorn]

"Post subject: How many plys without pruning?"

..."just with iterative alpha-beta-search"

Alpha Beta IS pruning, it's even called "alpha beta pruning".

http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

Did you mean how many plies by just using minimax, thus exploring every possible move at every turn? Otherwise, Alpha beta is what does the actual pruning, so this topic wouldn't make any sense... or am I misunderstanding something?

[Ralf Müller]

You're totally right, I meant "without pruning after alpha-beta", because that's my current standing.

[Ralf Müller]

Hi Sven,
also many thanks for your answer.

Fortunately, I was able to convince my old partner to start from scratch.
Whereas we were writing all without help or external ideas previously, we have now the CPW, this forum and other sources / step-by-steps as help, so we have not to "invent" all this stuff.

Propably we will using this site as basis or do you have other suggestions? http://www.sluijten.com/winglet/index.htm

[Sven]

"Post subject: How many plys without pruning?"

..."just with iterative alpha-beta-search"

Alpha Beta IS pruning, it's even called "alpha beta pruning".

http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

Did you mean how many plies by just using minimax, thus exploring every possible move at every turn? Otherwise, Alpha beta is what does the actual pruning, so this topic wouldn't make any sense... or am I misunderstanding something?

Alpha-beta pruning is only one of several forms of pruning:
- Nullmove pruning
- Futility pruning
- Late move pruning
- ...

But alpha-beta pruning is absolutely safe, while the others are "more or less safe" (but some of them are necessary for a strong program).

Sven

[tpetzke]

Hi,

to give you an impression, I just looked at my old references

In this position
position fen 3Q4/5q1k/4ppp1/2Kp1N1B/RR6/3P1r2/4nP1b/3b4 w - -

it took an early version of my engine without move ordering 712 seconds to reach depth 7

With move ordering by SEE this was reduced to 8 seconds

Neither version found the best move at this depth.

So good move ordering is one of the most important facts to speed up the search.

Thomas...