Olithink

[cms271828]

Hi, anybody tried the java engine Olithink?

Its so much quicker than my engine, but I donno why, I can't see where its ordering moves or doing quiescence search.

I guess if it wasn't doing QS, that would explain why it completes 10 ply seach in several seconds, but surely QS can't be missing?

The website is here if anyone is interested...
http://home.arcor.de/dreamlike/chess/index.html

[Sven]

Olithink does QS, of course. The function is named "quiesce()". The functions responsible for move ordering are qpick() (for QS) and spick() (for the main search).

Olithink has a very fast and almost minimalistic evaluation, uses bitboards, and also appears to be a very well-written chess engine. Each of these factors certainly contributes to both speed and strength.

If your engine usually does not complete the first 10 plies within some seconds then it is most probably either
- a bug,
- an insufficient search algorithm,
- a move ordering issue, or
- a very slow implementation.
Since you are using magic bitboards, and since I assume you now have a decent move ordering after our SEE discussion last year, it is quite likely one of the former two that slows you down somehow. Nevertheless I'd like to ask for your current EBF and NPS, just to be sure. Null move? Hash table, also used for move ordering? Quiescence search done correctly? You have probably checked all of these already.

Sven

[cms271828]

Thanks,

Olithinks code is very hard for me to understand in comparison to mine, and mine seems to take up lots and lots of code.

My own engine has:
QS [Node not in check, search captures that raise score. In check, full width search]
Hash Table: 2^21 entries
Null Move Pruning
MVVLVA move ordering, reading about SEE to put into next rewrite of program
Magic Move Generation (Configured Fixed Shift Magics for next rewrite, 25% faster)
EBF, not sure, never calculated it, but probably huge
NPS, 3.7M from start position(32 bit linux), around 5.5M (64 bit linux)
Also, no killer moves, no history heuristic, no aspiration windows or anything like that.
Evaluation function, is currently empty except for material that is calculated incrementally.
Small built in opening book, [35000 games], have built online version containing 1.7M games, to be used in next rewrite also.

I'm in progress of a rewrite, so any thoughts are welcome.

[Sven]

My own engine has:
QS [Node not in check, search captures that raise score. ...]

I am not sure whether that is a correct QS. You should also search equal captures at least since these can sometimes improve the positional eval. (Currently not having a positional eval - see below - is not a good argument against that.)

EBF, not sure, never calculated it, but probably huge

You should calculate it, maybe even let your engine print it regularly. There was a recent thread about it.

NPS, 3.7M from start position(32 bit linux), around 5.5M (64 bit linux)

No surprise with an empty eval

Also, no killer moves, no history heuristic, no aspiration windows or anything like that.

If there is no move ordering utility other than MVV/LVA then killer moves will really help a lot. The same applies to using the hash table move for move ordering, a feature of which I am not sure that you have it. Maintaining a hash table only for transpositions does not give a sufficient benefit.

Evaluation function, is currently empty except for material that is calculated incrementally.

No positional evaluation at all means that your engine has to waste a lot of time for searching bad positions, since it does not have that knowledge. This is one part of the explanation for the time needed for N iterations, you currently search too many nodes. No eval also means that the engine decides about its moves based on static move ordering and/or move generation order most of the time, which is of course not the goal.

You might start with a PST (Piece Square Table) that allows for a fast evaluation of some static and first-order aspects, like centralization, rook on 7th rank, or penalization of rook pawns. Adding mobility is also quite cheap with bitboards, the same applies to some aspects of pawn structure, including also rooks on open files. This should already help a lot, together with the other points I mentioned it may even double your further motivation

Good luck,
Sven

[JuLieN]

Evaluation function, is currently empty except for material that is calculated incrementally.

That's what hurts your move ordering, as an eval with just a material component will return the same value for half of the nodes. Try to add a few basic components, like mobility or simple pawn structure. Maybe rudimentary king safety too. All terms adding a few dozens of centipawns and make no leaf receiving the same value of another one, and your move ordering will get much better.

Prédateur (which is a relatively weak engine), reaches 10 plies under a second.

[cms271828]

Yes, thats a very interesting point about the evaluation, I never looked at it like that.
Minute differences in scores will allow the alpha-beta pruning to kick in better, and I suppose EBF will drop too.

I'm unsure how one measures EBF, is it basically the amount of the all moves played from every node searched divided by the amount of these nodes? This should give an average EBF over the search.

Regarding hashmove, the first thing I do in each node, is play the move (if any) stored in hash table.

I looked at killer moves before, but was never totally sure how to go about it, so have just left it.

For evaluation, this was one of the things I was going to do last, as I felt the 'skeleton' of the program should be done first, before taking it further.

Also, the Olithink code I was looking at was Olithink 4.1.2 Jan 04, now I see 5.3.0 version has the QS, and the code is a lot more understandable

[Sven]

I'm unsure how one measures EBF, is it basically the amount of the all moves played from every node searched divided by the amount of these nodes? This should give an average EBF over the search.

Take the time to read the essential part of this recent thread, and choose one definition you like. Comparing two subsequent iterations by using the formula "nodes(N) / nodes(N-1)" given in the CPW is one possible way to go, "sqrt(nodes(N) / nodes(N-2))" (for N = iteration number) is an improved version of it, and there is also the pure AI approach favored by Daniel Shawul, beneath others, to take the N-th root of the node count of iteration N (if that iteration was searched to full width depth N) and regard it as that iteration's EBF.

Note that in each case you need
a) to always look at fully completed iterations only, and
b) to take the node count only of the given iteration itself, not the cumulated one starting at the very first iteration.

I looked at killer moves before, but was never totally sure how to go about it, so have just left it.

You can find useful hints here. It is used for non-captures only, and therefore not in QS. Many programs maintain two killer moves per ply, organized like a small queue, i.e. whenever a new killer move is found and the queue is full you toss out the oldest entry.

For evaluation, this was one of the things I was going to do last, as I felt the 'skeleton' of the program should be done first, before taking it further.

True but the "skeleton" should already include a minimal positional evaluation (PST at least), since otherwise you run into trouble when trying to get other parts of the "skeleton" to run, like QS or move ordering. And as you now see, it has also a huge effect on overall search run time which in turn increases your effort for testing and debugging ...

Also, the Olithink code I was looking at was Olithink 4.1.2 Jan 04, now I see 5.3.0 version has the QS, and the code is a lot more understandable

You are right, up to now I was not aware of Olithink 4.1.2 having no QS at all. Implementing QS in 5.x might have given another ELO boost, though.

Sven

[OliverBr]

Hi, anybody tried the java engine Olithink?

Its so much quicker than my engine, but I donno why, I can't see where its ordering moves or doing quiescence search.

I guess if it wasn't doing QS, that would explain why it completes 10 ply seach in several seconds, but surely QS can't be missing?

The website is here if anyone is interested...
http://home.arcor.de/dreamlike/chess/index.html

OliThink java is nothing else than a 1-1 translation of the OliThink C Code, which wasn't that much work since OliThink source code is very small compared to other engines strong than OliThink.