MinimalChess 0.2 released

[Gabor Szots]

PSTs feel completely arbitrary and move ordering too

A laic's remark: when you yourself play chess you use move ordering as well, albeit subconsciously. You won't consider putting your queen en prise, for example.

[lithander]

Why is clearing a list so slow? Shouldn't it just reset the size to 0 but leave the contents untouched since everything still hanging around beyond the current size can be considered as irrelevant?

.Net is open source so you can just look at the implementation of List<T>.Clear() and find:

Code: Select all

        
// Clears the contents of List.
public void Clear() {
   if (_size > 0)
   {
      Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
      _size = 0;
   }
   _version++;
}

So the entire range of elements is set to their default value (for value types) or null (for reference types)!

PSTs feel completely arbitrary and move ordering too

A laic's remark: when you yourself play chess you use move ordering as well, albeit subconsciously. You won't consider putting your queen en prise, for example.

The way I've explained it to myself is that MVV-LVA orders the moves by the likelihood of the move making significant changes to the evaluation providing a chance to narrow down the search window as early as possible. What I feel is arbitrary about it is that it is very specific to chess and the value of it's pieces and not as generic as other pruning techniques. But I'm programming a chess engine after all, right? So version 0.3 will include it.

[Sven]

Why is clearing a list so slow? Shouldn't it just reset the size to 0 but leave the contents untouched since everything still hanging around beyond the current size can be considered as irrelevant?

.Net is open source so you can just look at the implementation of List<T>.Clear() and find:

Code: Select all

        
// Clears the contents of List.
public void Clear() {
   if (_size > 0)
   {
      Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references.
      _size = 0;
   }
   _version++;
}

So the entire range of elements is set to their default value for value types and null for reference types!

Yes, I forgot reference types since I was thinking in terms of a chess engine that would usually never use such a kind of highly dynamic container data structures at all ... If there were a container class designed for "plain" objects that do not contain references to other objects then this might be the better choice performance-wise than List<T>, right?

[Sven]

PSTs feel completely arbitrary and move ordering too

A laic's remark: when you yourself play chess you use move ordering as well, albeit subconsciously. You won't consider putting your queen en prise, for example.

The way I've explained it to myself is that MVV-LVA orders the moves by the likelihood of the move making significant changes to the evaluation providing a chance to narrow down the search window as early as possible. What I feel is arbitrary about it is that it is very specific to chess and the value of it's pieces and not as generic as other pruning techniques. But I'm programming a chess engine after all, right? So version 0.3 will include it.

That is not the intention of MVV/LVA, its goal is to get a smaller search tree by removing the most aggressive enemy pieces from the board as early as possible. The width of the search window is not relevant there, it is about the effective branching factor.

[lithander]

That is not the intention of MVV/LVA, its goal is to get a smaller search tree by removing the most aggressive enemy pieces from the board as early as possible. The width of the search window is not relevant there, it is about the effective branching factor.

I'm still learning the lingo. The search window I meant was the one between alpha and beta. The faster it converges the better is your effective branching factor. So alpha-beta with move ordering narrows the gap between alpha and beta faster than an alpha-beta search with unsorted moves and this reduces the branching factor and makes the searched tree smaller. Right?

Yes, I forgot reference types since I was thinking in terms of a chess engine that would usually never use such a kind of highly dynamic container data structures at all ... If there were a container class designed for "plain" objects that do not contain references to other objects then this might be the better choice performance-wise than List<T>, right?

All I'm saying is that the .Net runtime is quite fast and some long hold beliefs you may have borrowed from C/C++ like avoiding allocations are counter-productive in .Net.
I don't think you should micro-optimize C# like that. C# just puts another abstraction layer between you and the hardware. Make this layer your friend and don't try to outsmart it or get rid of it entirely. If you don't trust the runtime, the garbage collector and the JIT compiler then by all means stick with C/C++. (No offense meant!)

[lithander]

If you don't trust the runtime, the garbage collector and the JIT compiler then by all means stick with C/C++. (No offense meant!)

Which I really considered by the way. But it's been so long ago that I worked with C++ that it would have been like trying to learn two new topics at once.

[Sven]

That is not the intention of MVV/LVA, its goal is to get a smaller search tree by removing the most aggressive enemy pieces from the board as early as possible. The width of the search window is not relevant there, it is about the effective branching factor.

I'm still learning the lingo. The search window I meant was the one between alpha and beta. The faster it converges the better is your effective branching factor. So alpha-beta with move ordering narrows the gap between alpha and beta faster than an alpha-beta search with unsorted moves and this reduces the branching factor and makes the searched tree smaller. Right?

Almost right. But "narrowing the alpha/beta window" is not the key point of MVV/LVA. Instead it simply reduces the number of nodes to be searched by trying to obtain an early cutoff without leaving the enemy with a lot of possible captures you would have to examine. Therefore you try grabbing his queen, for instance, as early as possible whenever you can, even if that is "only" exchanging material instead of winning a pawn or a minor piece. It has been proven that this reduces tree size significantly in contrast to ordering based on the expected material gain. Even in a "human-like" search tree, refuting a bad move does not require the best refutation and can often be achieved with less effort by simply exchanging material and reducing the foreign forces.

Yes, I forgot reference types since I was thinking in terms of a chess engine that would usually never use such a kind of highly dynamic container data structures at all ... If there were a container class designed for "plain" objects that do not contain references to other objects then this might be the better choice performance-wise than List<T>, right?

All I'm saying is that the .Net runtime is quite fast and some long hold beliefs you may have borrowed from C/C++ like avoiding allocations are counter-productive in .Net.
I don't think you should micro-optimize C# like that. C# just puts another abstraction layer between you and the hardware. Make this layer your friend and don't try to outsmart it or get rid of it entirely. If you don't trust the runtime, the garbage collector and the JIT compiler then by all means stick with C/C++. (No offense meant!)

Not using data structures that do "magic" allocation/deallocation or even garbage collection behind the curtains is no "micro-optimization" in my view, it is how I think writing a chess engine should be approached ... And regarding that additional abstraction layer, I really prefer taking my bike to go to the bakery instead of booking a flight for that purpose

[mvanthoor]

Which I really considered by the way. But it's been so long ago that I worked with C++ that it would have been like trying to learn two new topics at once.

And that makes developing a chess engine slow, because I did exactly that: learning about chess programming and Rust at the same time. If had wanted to write the engine faster (but possibly not _better_), I would have written it in C; that's the programming language I know best. (I've been doing stuff around web development languages for some time now, but I think I can't ever forget the basics of C. I read C books as light reading as a teenager, before going to bed, in the 90's...)

Anything else but C, or would have needed to learn the language anyway. C++11, 17 or 20 would not have been easier to learn than Rust, let alone C# where most of the things I already know are basically either useless, or invalidated.

[unserializable]

Ctrl-C just quits the program without a crash on Windows. But the Callstack you provided should allow me to fix it in the next version. I might write you a PM then to ask you to confirm that fix!

IIRC EOF is not Ctrl+C on windows, but Ctrl+Z, if using simple pipe does not reproduce behaviour.

... So I forbade it to repeat positions that had been previously encountered. So when MMC or it's opponent fails to convert an endgame and the history gets longer and longer after a while MMC will starts to blunder because all good moves would lead into the repetition of a previous position.

Ah, then this should naturally improve if instead 'forbidding' repetitions, they were to just be scored as 0 (draw).