Fruit fly races on steroids?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

smatovic
Posts: 2927
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Fruit fly races on steroids?

Post by smatovic »

To open a new thread on this topic, taken from the Obsidian thread:
Frank Quisinsky wrote: Mon Jan 29, 2024 5:47 pm ...
I can imagine there are highly skilled, talented and educated engine programmers out there, and the development speed might have increased significantly cos of multiple reasons, nevertheless, I share John's opinion:
JohnWoe wrote: Fri Aug 13, 2021 1:43 pm [...]
How does it improve competition if everybody contributes to Stockfish?

The problem space is simply too massive for an individual to come up with code that equals Stockfish. Without significant copy-paste.
That's why we have the same program basically. I see no problem with Fire for example. It's as original as any other.

Crafty for example around 3,000 ELO while Hyatt worked on this project like 40 years professionally. This is where super originality leads you.

Of course the modern society only rewards winners and the others can go home. So here we are.
[...]
.,.,and, some people still can not distinguish between science and engineering, theory and practice, ideas and implementations.

Further, one could criticize the test-driven development of engines, w/o working out the theory behind:

From Esoteric to Transcendental Chess Programming?
viewtopic.php?f=7&t=76286


***edit***

"Fruit fly races on steroids?"
Unfortunately, the competitive and commercial aspects of making computers play chess have taken precedence over using chess as a scientific domain. It is as if the geneticists after 1910 had organized fruit fly races and concentrated their efforts on breeding fruit flies that could win these races.
https://www.chessprogramming.org/Artifi ... n_McCarthy

And, as already mentioned in another post, the two most important recent impacts in computer chess came from the outside. Lc0 is an open source adaption of AlphaZero, an generalization from AlphaGo applied on Go, Shogi and Chess. The NNUE technique came from the Shogi world to chess.

--
Srdja
smatovic
Posts: 2927
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Fruit fly races on steroids?

Post by smatovic »

That being said, nothing wrong in participating in/watching fruit fly races...let them fly ;)

--
Srdja
User avatar
towforce
Posts: 11865
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

It all comes down to what you want from computer chess.

You've previously suggested constraining the system by all using the same hardware, suggesting that what you want is competition between developers witing their own hand-coded programs. That's a good thing - but not enough developers seem to want to do that.

Mentioning fruit flies in the context of genetic research implies a thirst for scientific data - but what scientific data do you want?

Some people want a chess program that's great fun to play against.

How about the people that love playing against different chess computers by different authors? Like having a new girlfriend each week!

I know you're desperate to know what I want! :D

I want chess solved and fully explained. In contrast to most other people, I think that this is achievable with today's technology, Like you, I find nobody wanting to do exactly what I want. :cry:
The simple reveals itself after the complex has been exhausted.
smatovic
Posts: 2927
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Fruit fly races on steroids?

Post by smatovic »

towforce wrote: Mon Jan 29, 2024 8:07 pm ...
:) my own objective was already solved, how to use a GPU for chess....for you my friend, we talked about knowledge graphs and chess patterns -> Morph:

https://www.chessprogramming.org/Morph

--
Srdja
smatovic
Posts: 2927
Joined: Wed Mar 10, 2010 10:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic

Re: Fruit fly races on steroids?

Post by smatovic »

Further remark:

Chess engines do not scale anymore with more powerful hardware*, in principle a Raspberry Pi for 50,- bucks plays Remis against a 5000,- dollar CPU, but I believe computer chess will remain of interest as benchmark for AIs in general and also as test bed for new technologies, cos the domain of computer chess has an limited and measurable socio-techno-cultural impact, or alike.

*with unbalanced openings in tournaments/rating lists/testing we are already in extra time.

--
Srdja
User avatar
towforce
Posts: 11865
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

smatovic wrote: Sat Apr 06, 2024 7:49 am...with unbalanced openings in tournaments/rating lists/testing we are already in extra time.

Draw-death is coming for computer chess.

Many ways have been suggested to reduce the draw rate - but none of them will work for long, except for... bigger boards. The complexity of chess increases exponentially with board size.

The big killer, that will get close to perfect play even with a bigger board, is the God algorithm.

The ultimate aspiration for chess: the knowledge of how to create a God algorithm for any size of board.

That will be the end of computer chess as a place for the advancement of AI - but would be the start of a new way to attack problems that look NP-Hard, but which will actually yield to uncovering their underlying patterns.
The simple reveals itself after the complex has been exhausted.
petero2
Posts: 701
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Fruit fly races on steroids?

Post by petero2 »

towforce wrote: Sat Apr 06, 2024 12:42 pm The big killer, that will get close to perfect play even with a bigger board, is the God algorithm.

The ultimate aspiration for chess: the knowledge of how to create a God algorithm for any size of board.
If you ignore performance of the algorithm, this is trivially achieved by the minimax algorithm.

If you don't ignore performance, a problem is that chess on an n x n board has already been proven to be exptime-complete. See the article "Computing a perfect strategy for n x n chess requires time exponential in n": https://www.sciencedirect.com/science/a ... 6581900169

A potential way out is that you write "close to perfect" and not "perfect". It seems odd to me though to call a non-perfect algorithm "the god algorithm".
User avatar
towforce
Posts: 11865
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

petero2 wrote: Sat Apr 06, 2024 1:24 pm
towforce wrote: Sat Apr 06, 2024 12:42 pm The big killer, that will get close to perfect play even with a bigger board, is the God algorithm.

The ultimate aspiration for chess: the knowledge of how to create a God algorithm for any size of board.
If you ignore performance of the algorithm, this is trivially achieved by the minimax algorithm.

If you don't ignore performance, a problem is that chess on an n x n board has already been proven to be exptime-complete. See the article "Computing a perfect strategy for n x n chess requires time exponential in n": https://www.sciencedirect.com/science/a ... 6581900169

A potential way out is that you write "close to perfect" and not "perfect". It seems odd to me though to call a non-perfect algorithm "the god algorithm".

Excellent find! 8-)

This paper proves what I said in my previous post - the game becomes exponentially more complex with increasing board size.

However, it doesn't prove the non-existence of a God algorithm (I have in the past explained why I think it's "very likely" that a God algorithm which is much smaller and quicker than most members of this forum (who mostly belong to a "deep search of a game tree" culture: no complaints about that - this is what worked best for most the existence of computer chess) would currently believe possible).

Super simple example:

[d]8/8/8/8/3k4/8/8/4KR2 w - - 0 1

It's 29 moves to checkmate here (link). On a 100x100 board, a similar position might be hundreds of moves to mate, and the search tree would be many orders of magnitude larger. However, it's still just as easy to get the checkmate, because a well known pattern exists. The evidence strongly suggests simple patterns also exist from which an algorithm to accurately evaluate any chess position can be built (obviously a more complicated one than required for the above position - but a lot less complicated than you'd expect).
The simple reveals itself after the complex has been exhausted.
chesskobra
Posts: 269
Joined: Thu Jul 21, 2022 12:30 am
Full name: Chesskobra

Re: Fruit fly races on steroids?

Post by chesskobra »

petero2 wrote: Sat Apr 06, 2024 1:24 pm
If you ignore performance of the algorithm, this is trivially achieved by the minimax algorithm.

If you don't ignore performance, a problem is that chess on an n x n board has already been proven to be exptime-complete. See the article "Computing a perfect strategy for n x n chess requires time exponential in n": https://www.sciencedirect.com/science/a ... 6581900169

A potential way out is that you write "close to perfect" and not "perfect". It seems odd to me though to call a non-perfect algorithm "the god algorithm".
Why is the complexity growing exponentially with board size relevant? We are dealing with 8x8 board, and the difficulty of finding a perfect algorithm has nothing to do with exponential complexity as a function of board size.
petero2
Posts: 701
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Fruit fly races on steroids?

Post by petero2 »

chesskobra wrote: Sun Apr 07, 2024 12:14 am
petero2 wrote: Sat Apr 06, 2024 1:24 pm
If you ignore performance of the algorithm, this is trivially achieved by the minimax algorithm.

If you don't ignore performance, a problem is that chess on an n x n board has already been proven to be exptime-complete. See the article "Computing a perfect strategy for n x n chess requires time exponential in n": https://www.sciencedirect.com/science/a ... 6581900169

A potential way out is that you write "close to perfect" and not "perfect". It seems odd to me though to call a non-perfect algorithm "the god algorithm".
Why is the complexity growing exponentially with board size relevant? We are dealing with 8x8 board, and the difficulty of finding a perfect algorithm has nothing to do with exponential complexity as a function of board size.
You should ask the person I was responding to, who brought bigger boards into the discussion by writing this:
towforce wrote: Sat Apr 06, 2024 12:42 pm The big killer, that will get close to perfect play even with a bigger board, is the God algorithm.
It seems relevant to know what has already been proven to be theoretically impossible before trying to solve a problem.