FIDE & Google Efficient Chess AI Challenge

Discussion of chess software programming and technical issues.

Moderators: hgm, chrisw, Rebel

User avatar
towforce
Posts: 12027
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: FIDE & Google Efficient Chess AI Challenge

Post by towforce »

Uri Blass wrote: Sat Nov 23, 2024 12:48 pmI do not think that it is interesting to disallow recursion and looping. I believe that even engines from 1980 used recursion and looping.
Nearly every chess program ever written - going right back to the early 1950s, will have used recursion and looping.

Uri Blass wrote: Sat Nov 23, 2024 12:48 pmIt may be interesting to have a competition of what you can achieve with very old hardware but for this you do not need to disallow recursion and looping.
Indeed: the early dedicated chess computers used recursion and looping - and their specification was tiny compared to what's allowed in this competition.

hgm wrote: Sat Nov 23, 2024 3:18 pm
towforce wrote: Sat Nov 23, 2024 12:02 pm5. The following programming techniques disallowed: recursion and looping
That is completely non-sensical. Without recursion or looping a 64KB program would finish in a few micro-seconds, as every instruction could be executed at most once.
Not quite: you're basically right - but here's a counterexample:


if (bool) {
..call methodA;
..call methodB;
}
else {
..call methodC;
..call methodD
}

call methodE;
call methodA;
call methodC;



The competition preamble states that they're looking for new types of AI, so the developers need to be require to do something different to what they have done before - hence the no looping and no recursion rule.
Want to attract exceptional people? Be exceptional.
abulmo2
Posts: 440
Joined: Fri Dec 16, 2016 11:04 am
Location: France
Full name: Richard Delorme

Re: FIDE & Google Efficient Chess AI Challenge

Post by abulmo2 »

Uri Blass wrote: Sat Nov 23, 2024 12:42 pm I see no problem with the time control.
people use 10+0.1 time control to test engines.
People, me included, use 10+0.1 time control to play one game. Here it is 10+0.1 to play one move.
Richard Delorme
abulmo2
Posts: 440
Joined: Fri Dec 16, 2016 11:04 am
Location: France
Full name: Richard Delorme

Re: FIDE & Google Efficient Chess AI Challenge

Post by abulmo2 »

abulmo2 wrote: Sat Nov 23, 2024 9:11 pm
Uri Blass wrote: Sat Nov 23, 2024 12:42 pm I see no problem with the time control.
people use 10+0.1 time control to test engines.
People, me included, use 10+0.1 time control to play one game. Here it is 10+0.1 to play one move.
I may have been not clear, the 0.1 s is simple delay (or us delay) it means the clock will start after 0.1 second. It is a kind of margin, not an increment. The engines have 10 seconds per move to play with a margin of 0.1 second.
Richard Delorme
User avatar
hgm
Posts: 28216
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: FIDE & Google Efficient Chess AI Challenge

Post by hgm »

towforce wrote: Sat Nov 23, 2024 9:07 pm Not quite: you're basically right - but here's a counterexample:


if (bool) {
..call methodA;
..call methodB;
}
else {
..call methodC;
..call methodD
}

call methodE;
call methodA;
call methodC;



The competition preamble states that they're looking for new types of AI, so the developers need to be require to do something different to what they have done before - hence the no looping and no recursion rule.
OK, I assumed that 'no recursion' meant 'no function calls', and this is formally not correct. But if your example is allowed, the rule 'no recursion' basically becomes ineffective. I would rewrite my alpha-beta searcher that wants to recursively call search up to depth 10 like

Code: Select all

function SearchRoot() { Search1(); }
function Search1() { Search2(); }
...
function Search9() { Search10(); }

So I would just add a different dummy routine for each recursion level, which call each other but never call back to themselves, and the only thing these do is call the routine I would really have liked to call itself. This takes up almost no extra space.

Same with loops: you make a different dummy function for every iteration, which all call the function that does what you want the iteration to do, and make sure there are sufficiently many for the worst case. And after each you should test whether you are done, and then skip the remaining ones:

Code: Select all

function LooplessLoop()
{
  if(Iter1()) return;
  if(Iter2()) return;
  ...
  if(Iter99()) return;
  Iter100()
}
function Iter1() { Iter(1); return done(); }
function Iter2() { Iter(2); return done(); }
...
function Iter100() { Iter(100); return done(); }
I could even pass 'Iter' and 'done' as arguments to LooplessLoop(), so that this function can be universally used for unrolling all loops in the program.
User avatar
towforce
Posts: 12027
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: FIDE & Google Efficient Chess AI Challenge

Post by towforce »

Very good! :D

I don't want to spend too much time discussing a rule that will probably never be implemented, but the basic intention here is to evaluate at ply 1, using intelligence only, and no brute force, so that nothing but intelligent knowledge of the position is used.

So maybe either:

1. Say that a "coded out" loop is still a loop and disallow it

2. Simply say that generating moves beyond the legal moves in the root position is disallowed

If this were implemented, it would be the best computer chess competition ever: change the question from Who's got the biggest game tree? to What are the great secrets of chess?
Want to attract exceptional people? Be exceptional.
Uri Blass
Posts: 10610
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: FIDE & Google Efficient Chess AI Challenge

Post by Uri Blass »

towforce wrote: Sat Nov 23, 2024 11:32 pm Very good! :D

I don't want to spend too much time discussing a rule that will probably never be implemented, but the basic intention here is to evaluate at ply 1, using intelligence only, and no brute force, so that nothing but intelligent knowledge of the position is used.

So maybe either:

1. Say that a "coded out" loop is still a loop and disallow it

2. Simply say that generating moves beyond the legal moves in the root position is disallowed

If this were implemented, it would be the best computer chess competition ever: change the question from Who's got the biggest game tree? to What are the great secrets of chess?
I see nothing intelligent by not searching.
Part of the idea of chess is to search.

I can understand that intelligence means limited speed or limited memory but not avoid searching.
User avatar
towforce
Posts: 12027
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: FIDE & Google Efficient Chess AI Challenge

Post by towforce »

Uri Blass wrote: Sun Nov 24, 2024 1:11 amI see nothing intelligent by not searching. Part of the idea of chess is to search. I can understand that intelligence means limited speed or limited memory but not avoid searching.

A beginner needs to mentally try out all the moves and all the responses to those moves: this takes lots of time, and he still chooses the wrong move.

A GM looks at most positions and just knows.
Want to attract exceptional people? Be exceptional.
Uri Blass
Posts: 10610
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: FIDE & Google Efficient Chess AI Challenge

Post by Uri Blass »

towforce wrote: Sun Nov 24, 2024 11:16 am
Uri Blass wrote: Sun Nov 24, 2024 1:11 amI see nothing intelligent by not searching. Part of the idea of chess is to search. I can understand that intelligence means limited speed or limited memory but not avoid searching.

A beginner needs to mentally try out all the moves and all the responses to those moves: this takes lots of time, and he still chooses the wrong move.

A GM looks at most positions and just knows.
GM's also search otherwise what they do in their thinking time in a chess game?
User avatar
towforce
Posts: 12027
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: FIDE & Google Efficient Chess AI Challenge

Post by towforce »

Uri Blass wrote: Sun Nov 24, 2024 11:40 am
towforce wrote: Sun Nov 24, 2024 11:16 am
Uri Blass wrote: Sun Nov 24, 2024 1:11 amI see nothing intelligent by not searching. Part of the idea of chess is to search. I can understand that intelligence means limited speed or limited memory but not avoid searching.

A beginner needs to mentally try out all the moves and all the responses to those moves: this takes lots of time, and he still chooses the wrong move.

A GM looks at most positions and just knows.
GM's also search otherwise what they do in their thinking time in a chess game?

There is a strong negative correlation between "chess knowledge" and "thinking time needed to make a good move".

If a chess entity had very strong knowledge, it would almost never require a significant amount of thinking time.
Want to attract exceptional people? Be exceptional.
User avatar
hgm
Posts: 28216
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: FIDE & Google Efficient Chess AI Challenge

Post by hgm »

That depends on your definition of 'significant'. With current computer technology a stupid alpha-beta searcher can move faster than a human GM can blink. Ever since 1980 or so chess programs have been judged by their performance at equal thinking time, and putting in knowledge that required time to evaluate has always been a losing proposition versus using the same time towards searching deeper. In engine-engine games, that is.

The Alpha-Zero descendants sort of broke this trend; they store an enormous amount of knowledge in their neural nets. So much that Leela Chess Zero with a big net is already very difficult to beat without searching (i.e. limited to 1 node, just using the output of its policy head to selectthe move). This was only possible because the time needed to apply the knowledge enormously benefits from the parallelism that modern CPUs (and to an even larger extent GPUs) offer at the single-thread level through SIMD instructions. Plus the fact that, unlike AB-search, running a NN is an extremely wide parallel effort rather than a serial one.

But if the proposed rules for this challenge (in particular the 64K limit) exclude anything, it is using NN for encoding the knowledge.