Chess program with Artificial Neural Networks (ANN)?

[diep]

Hi There,

Are there chess-engines around that have any kind of Artificial Neural Networks implemented?

On the internet I found some vague descriptions of various attempts, but I was unable to find any working engines or examples of code. (Most of the attempts failed and were subsequentely abandoned).

Has anyone here tried this approach before? I don't really expect miracles from it, on the other hand, it might be worth exploring.

I was thinking about a hybrid system of negascout combined with an ANN-based evaluation function. In general neural networks tend to be quite good at recognising patterns. Given a certain chess-position, the most important patterns is exactely the chalanging part of a good evaluation algorithm.

Stephan

In the 90s many government sponsored projects were there. If i remember names correctly Dan Thies did do a big attempt to use an existing chessprogram and let an ANN do the entire evaluation function for a 100%. though the ANN was very very fast for its days, therefore the program had a big speed in nps, it didn't score rather well against one of the first diep versions from 1994, which couldn't mate KRK actually even. Maybe elo 1600?

So years later it still couldn't beat the very first diep versions. Far more interesting attempt years later was from Alex van Tiggelen using the dutch nightmare. He tried to parameter tune the evaluation function, llike we all tried in the 90s. In fact the very first diep version had 1 big array implementation for every bonus. Some later i got rid of that as that slowed down the program too much.

Very interesting attempt i say, especially a courageous, because nightmare from Joost Buijs was a very strong program. It is interesting to have succes at a strong program, as that means your method is more serious.

I forgot what year Alex van Tiggelen has died, but what he has done i take far more serious considering Nightmare already was a well tuned program and pretty bugfree.

Overall seen however ANN's have not brought much success in computerchess.

Tuning methods such as knightcap we cannot take serious of course.

Realize all those projects used special hardware. Very expensive.

Vincent

[SuneF]

Realize all those projects used special hardware. Very expensive.

Vincent

Not necessarily so. With Nvidia CUDA cores on your standard affordable GeForce it is starting to look interesting.

For instance this dude here seems to get a nice speedup in ANN
http://www.codeproject.com/KB/graphics/GPUNN.aspx

Training them properly seems to be the issue though. I'm rather pessimistic about that to be honest.

[Gian-Carlo Pascutto]

CUDA is very interesting if you're OK with your engine not searching more than 10knps.

[jwes]

CUDA is very interesting if you're OK with your engine not searching more than 10knps.

Are latencies really that high? I was looking a little at this, and thought I might get a few hundred thousand nodes per second, which was still too slow.

[Gian-Carlo Pascutto]

AFAIK you can't hope for more than about 50k calls per second.

A call overhead benchmark of recent drivers on a recent OS would be interesting, to see if things improved, but I doubt you will get the near 1M calls/s which you realistically need to do the NN eval on the card.

[diep]

Realize all those projects used special hardware. Very expensive.

Vincent

Not necessarily so. With Nvidia CUDA cores on your standard affordable GeForce it is starting to look interesting.

For instance this dude here seems to get a nice speedup in ANN
http://www.codeproject.com/KB/graphics/GPUNN.aspx

Training them properly seems to be the issue though. I'm rather pessimistic about that to be honest.

In the 90s we didn't have the calculation power of today. So the researchers back then had hardware of hundreds of thousands of dollars or more just to simulate an ANN. Even training small networks was quite complicated back then. Additionally to all the problems back then, x86 back then was ugly slow for floating point calculations.

Today a simple quadcore already is really powerful there.

For ANN researchers, programming in CUDA is going to be a problem, as they are already not clever enough to design good learning algorithms; i don't see why someone who is not clever enough should speedup his crappy code; parallel programming in CUDA is going to eat a lot of time of that researcher, so he'll even have less time to invent something that might work.

There is some exceptions. It seems in China there is a big expert in ANN's busy using it to scan all phonecalls with his ANN's. Of course that is extremely complicated, because even simple burglars already speak in code with each other; they're not saying: "let's rob bank XYZ". So the job to pick out the right conversations with ANN's is really complicated, as each group of criminals will use other code words and forms of saying things.

In that sense the challenge is similar to chess, because you train ANN at patterns X, whereas in reality you want it to not make a mistake in patterns Y, though similar to X, not exactly the same.

It is there where all forms of automatic learning (not to confuse with tuning) have failed so far.

The fields where they have proven succesful is recognizing fixed patterns with a very bad granularity.

[diep]

CUDA is very interesting if you're OK with your engine not searching more than 10knps.

Well you're assuming communication latency to the main CPU of course.

That is not reality however. You run the entire thing on the GPU of course and bandwidth optimize things.

However all this is extremely complicated. Knowing the level of the average AI researcher he or she won't manage. Only the very best can.

Vincent

[Gian-Carlo Pascutto]

That is not reality however. You run the entire thing on the GPU of course and bandwidth optimize things.

Sure, where's your program that runs entirely on a current GPU and is still competitive?

[diep]

CUDA is very interesting if you're OK with your engine not searching more than 10knps.

Are latencies really that high? I was looking a little at this, and thought I might get a few hundred thousand nodes per second, which was still too slow.

Forget communication card vs cpu.

In theory it could be 5 microsecond or so if they wanted to. Yet GCP has tested all this and didn't manage to push through more than i could push through at 100mbit networks.

Which also was a few thousands per second.

It doesn't make sense to be dependant upon the main CPU, as the bandwidth from the GPU to the cpu is always limited bandwidth.

Say 1-2 GB/s max.

So anything you do on the gpu has to run entirely within the GPU.

All this is not new. Brutus/Hydra project had a similar problem.

Chrilly soon concluded that search in hardware was too inefficient, so he pushed the search back to the CPU's. The limitation which he had with the fpga cards was that latency didn't allow more than a 90k-100k searches per second per card.

Chrilly didn't understand why Deep Blue did do such huge searches in hardware, as those in his eyes were even more inefficient.

However if he would have had a calculator he would have figured out one of the reasons already; Hydra steers like 1 fpga card per memory node,
but deep blue steered 16 or so per node. 30 nodes, 480 hardware processors.

So 100k / 16 = 6k searches per hardware chip per second maximum.

Additionally a branching factor of 10.0 or so back then was more acceptable than nowadays and obviously they could show ibm progress by getting more nps, which is the opposite of what Hsu did do in his thesis, where the SEARCH DEPTH was important and not the nps. So he got corrupted by money later on in life.

What was a good branching factor for hydra is however a very bad branching factor nowadays.

Hydra with its 220 million nps got like 18-20 ply at 2 minutes a move.

Todays software gets a lot deeper than that.

Yet in all cases the problem is the same. You do not want to backtrack from special hardware to the main CPU. Only for very complex parallel software (nuke explosions?) such things are interesting to solve well. It is all total fulltime time to solve and we see that very gifted persons such as Hsu and Donninger also didn't manage to solve it for chess.

So just run the entire ANN within the GPU i'd argue.

This means obviously that the entire process has to get coded in CUDA. So all code must run there. This is why i commented what i commented a few postings before; that it is too difficult for the average researcher to do this.

Vincent

[diep]

That is not reality however. You run the entire thing on the GPU of course and bandwidth optimize things.

Sure, where's your program that runs entirely on a current GPU and is still competitive?

Actually, i shipped both Nvidia and AMD emails regarding that but they weren't interested in supporting such a project. Most people have too high expectations from porting software to gpu type hardware.

If you can be factor 5-10 faster in CUDA or Brooke than a simple quadcore that's really a lot of course. OpenCL not gonna manage there btw.

They have unrealistic speedup expectations of software that is already competative at x64 hardware. You won't sell a GPU project saying it "maybe" will get 5-10x faster than a x64 chip.

Yet some might buy a new x64 cpu if it is 20% faster or so. Just 1.2. What if a new x64 chip would be 5x faster?

What always amazes me, if you look to deep blue and hydra, that's that the programs with real little program code have been ported to hardware; porting a chess engine like diep to hardware is far more interesting as it executes really a lot of code per node. So the focus then is less on the memory subsystem; all these guys started those projects without doing ANY effort for the memory subsystem whereas this is most important!

In case of diep: Of course it is also a lot of extra work and initially didn't fit on the $500 fpga's as those had too little gates (space to fit in that much evaluation code)

Vincent