Possible experiment/exercise -- distributed chess player

Your Libraries & Packages Libraries
#1

I just had a brief chat in Slack about this, I’ll paste the chat, then more details
about what I have in mind.

hal9000 I am thinking of working on a little project as an experiment and a learning exercise – a distributed chess player that farms out its work to multiple nodes
if anyone is interested in collaborating on that, let me know

ssijak @hal9000distributed min-max?

hal9000 not necessarily - thinking i might impose restrictions on the algorithm to make it interesting - i’m not knowledgeable about “real” chess algorithms anyway

tfarla @hal9000: that does sound interesting

ankhers I think that would be fun.

hal9000 i’ll post on the google group to avoid cluttering here

So… my basic idea.

  • The goal is not to create a wonderful, competitive robot chess player.
  • That might be a later goal.
  • The goal is to distribute the work in a reasonable way and make it nice
    and modular.
  • It doesn’t have to play “super-well”; it has to obey the rules, respond in
    reasonable time, and play acceptably well, whatever that means.
  • I am leaning away from the traditional chess engine techniques.

Aside: I have often felt that chess playing algorithms are in a sense “cheaters” –
a human player does not consciously look ahead millions of moves. Humans
are smart and slow; our algorithms are very fast and very dumb. (We never
have “contests” between an autistic savant and a hand calculator, do we? As I
see it, the machine-human chess matches are not much different.)

This, by the way, is one reason Arimaa is notoriously difficult for machines
to play. The game is inherently more amenable to human intuition that to any
kind of optimized brute-force search. An algorithm to play Arimaa is something I
have often thought of working on (but never will).

Therefore, I am leaning toward the idea of some kind of “handicap” or limitation
on the algorithm. Something like: You can analyze the board statically all you want,
but you can only look at N total “what-if” scenarios. (The search tree may be as
deep or shallow as you like, but can only have N nodes.)

So there could be two possible scenarios for this project, and they are not
mutually exclusive:

  1. Write a distributed bot that plays acceptably well against a human.
  2. More interestingly: Let two versions of the bot play against each other. Let
    each team tweak the algorithms and heuristics within certain boundaries. Then
    we can have a tournament between the two sets of heuristics (essentially a
    competition of programmers).

If anyone is interested in working on this, let’s talk… :slight_smile:

Thanks,
Hal Fulton

1 Like
#2

I would like to collaborate on this project! We already have a head-start with chexx which has a functioning (but crappy) minimax algorithm, and broken alpha-beta. I was thinking of using Elixir-based neural nets to make a kind of naive AI, and/or using Tensorflow for DNNs. But yes, I would love to see how the AI can scale horizontally.

#3

You’re obviously far more knowledgeable about game engines
than I am.

Did my constraints make sense to you? Do you find this approach
acceptable?

Hal

#4

I am hardly knowledgeable about such things! Learning as I go along.

I don’t really understand why you would want to prevent the computer from searching the game tree thoroughly. I want to make the chess AI as strong as possible. Neural nets may be the best way to get that kind of human intuition, but it still requires a lot of simulated game play. I don’t understand much about what makes certain chess engines better than others, but maybe this is what you mean by heuristics, since they all seem to employ a brute-force search like minimax.

#5

Sounds very interesting, happy to help out. I know nothing about game models, but I’m keen to learn and this would be a great vehicle.

1 Like
#6

I’d personally rather make a “smart” and creative algorithm that has not necessarily
been tried before. That, to me, is more interesting than saying “Let’s do it much the way
we’ve done it for 35 years, only on faster hardware.”

Hal

1 Like
#7

That’s fair. What about implementing new research on chess intelligence? It still seems to be an active topic.

Google Scholar search results:

#8

Well, there actually have been quite a few interesting developments lately. In how you describe the heuristic functions that determine as how desirable a certain position in the game tree is seen by the AI, as well as the check that determine how far to look down in a certain position (quiesence search, for instance), there is a lot of room for creativity and cleverness.

A whole different approach would of course be to make a Monte Carlo AI, which would work a lot different from a Negamax one.

In any case, I was thinking a bit about creating my own algorithm for Negamax-esue games a while back. One of the things I was wondering about at that time, was how to represent game boards efficiently in a functional programming language.

In the end I got sidetracked, and instead of building a Negamax player, I am now building the Tensor library, which allows you to create and manipulate Vectors, Matrices and other Tensors. It was made with, amongst other things, two-dimensional game boards like Chess’ in mind.

1 Like
#9

Brilliant, @Qqwy! I admire your ability to Get Things Done :grin:

1 Like
#10

I’m being sort of wishy-washy here, I guess. :slight_smile: I don’t know
what I really want to do.

It has just always bothered me somehow that human players
and machine players don’t work the same way at all. In a sense,
we’re comparing apples and oranges.

A human grand master can put up a good fight against a machine,
but he/she does it without making 10 million simulated moves.
If a human could use his normal methods and look ahead at a few
million possibilities, the computer wouldn’t stand a chance.

Likewise, if we forced a computer to “think more like a human,” it
might once again not stand a chance.

Crude analogy: Cars have been faster than human runners for many
decades. But it’s only recently we’ve made robots that can run (and
they still aren’t fueled by steak and potatoes).

I hadn’t really considered the issue of how to represent the board in
a functional language. That in itself seems nontrivial now that I think
of it.

I wonder if I/we should consider some game other than chess?

Hal

3 Likes
#11

I think deep neural nets are what you’re looking for here as they simulate that intuitive human decision-making. Of course it is far easier for a computer to consume a huge training set relatively quickly, while a human takes years to play a couple thousand games. We have some other cognitive abilities that make up for that. Perhaps your question is more philosophical: Can a computer ever play a game as a human would?