19
$\begingroup$

In some (historical) papers, chess has been referred to as the drosophila of artificial intelligence. While I suppose that in current research, the mere application of a search algorithm is at best advanced computer science, I believe that there are still area's where can apply (and practice) AI-techniques.

A simple example would be opening book learning where one can teach the program whether to use or to not use certain moves in the opening because the program is unsuited to certain types of position. We can use a form of re-inforcement learning and automate this: I suppose I could play the program against itself and increase the probability of winning lines and decrease the probability of losing lines.

The more complex example is to use a learning evaluation function (for example, one could tweak the values of piece-square tables). However, I'm thinking:

  • given all the noise due to there being an enormous amount of realistic positions (as opposed to the amount of realistic opening lines)
  • and with the cost (duration) of a computer chess game, and the need to play loads.

How can one do this effectively? (or should I look at other techniques, for example neural networks.)

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ The standard approach is alpha-beta pruned minimax. with a heuristic. It is from the Search family of AI, rather from the machine-learning family. $\endgroup$
    – Frames Catherine White
    Feb 9, 2014 at 11:23
  • 2
    $\begingroup$ Actual chess masters basically just remember all the games that they've previously played... So they have strong memoization. $\endgroup$
    – screenmutt
    Feb 10, 2014 at 13:45
  • 2
    $\begingroup$ There's also the counter claim. I can't remember who said it but it goes like this. Biologists use experiments on drosophila to obtain deeper and deeper understanding of physiology, genetics and so on. AI people write chess computers to be better and better at playing chess. This doesn't teach us much at all about computer science; it would be like the biologists breeding super-fast, super-strong drosophila and making them fight each other. $\endgroup$
    – David Richerby
    Apr 29, 2015 at 12:45
  • $\begingroup$ wrt the metaphor, it is conceivably more than "drosophila of artificial intelligence" wrt different aspects, esp considering it didnt decisively beat the top human until ~1997, & research into it continues, etc $\endgroup$
    – vzn
    Apr 29, 2015 at 19:25

3 Answers 3

Reset to default
16
$\begingroup$

The whole state space for chess is enormous - it can be roughly estimated as 1043 (Shannon number (Shannon, 1950), (Wikipedia)).

The idea you present - Reinforcement Learning agents playing with each other to learn the game - was successfully applied to Backgammon - TD-Gammon (Tesauro, 1995), (Chapter in Reinforcement Learning by Sutton&Barto). It also used Neural Networks to estimate game's value function. This problem is however much simpler, as number of states in Backgammon is significantly smaller than in chess, namely: 18,528,584,051,601,162,496 (Backgammon Forum Archive thread).

If you, however, would end the game after few initial moves and aim only to learn "good openings" you could succeed with analogous approach. The main problem would be to evaluate the game after the opening game, which seems hard. Just a similarity measure to the established positions after well known openings is not enough, because position can be far from them if opponent would make a stupid move (so it wouldn't be because of learning agent's mistake, so the position even if "incorrect" should be evaluated as a good outcome).

References:

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The hardest part indeed is coming up with an empirical way to score the result of openings. Different openings are be good in different ways, so there is probably a multitude of acceptable openings. $\endgroup$
    – JDong
    Feb 7, 2014 at 21:19
3
$\begingroup$

I am pretty sure that any possible (or weird) method of AI or ML in textbooks has been tried and pretty much failed compared to simple brute force.

My personal perspective is that chess per se is of no interest to modern AI any more... Simply, because it is solved: by just using a modern computer and brute force. So, I don't feel that there is a need to create an "intelligent" system to solve it more efficiently (works just fine in my cell phone), and I believe that there isn't even the need for some unknown and more "intelligent" approach to exist.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I'm not sure why this got downvoted. The argument that chess is "solved" is a little inaccurate, in that no computer can look at any possible position and evaluate it perfectly. That said, iliasfl is spot-on that it chess has lost most of its appeal for AI research. For one thing, the best computer chess programs are now vastly stronger than the best humans, given enough processing power and time. This makes it increasingly difficult for programmers even to evaluate how well an algorithm works. $\endgroup$
    – elixenide
    Feb 10, 2014 at 17:06
  • 1
    $\begingroup$ Thanks, I said solved in the sense that brute force is a solution. Of course AI community (in general not just in here) is not happy with that "solution". However, we already have a computational system that presents "intelligent" behaviour for solving this task, and even win best humans, period. Personally, I believe that chess will be off-topic for AI after a few years when current mass of academics who spent careers on attacking it retire. $\endgroup$
    – iliasfl
    Feb 10, 2014 at 20:32
  • $\begingroup$ I wouldn't call the current computer chess implementations as 'solved by brute force' - they are still searching over huge amounts of gamestates, but there are many components of non-brute force there. Of course, they are not a "human-style" solution that would generalize well to other problems, but I wouldn't be surprised that if we had a "human-style" chess AI, then it would be multiple orders of magnitude less efficient than the current specialized solutions, making it simply inferior. $\endgroup$
    – Peteris
    Feb 16, 2014 at 17:33
  • $\begingroup$ I think this answer and its comments were quite clearly refuted by Google's AlphaZero: en.wikipedia.org/wiki/AlphaZero Even if you accept the criticism about the setup for Stockfish and they had drawn all the matches, a system that got to that level with a few hours of training is clearly superior. $\endgroup$
    – Kamal
    Sep 30, 2018 at 18:44
2
$\begingroup$

I think it's worth noting that in order to determine how to tackle an AI problem you must define it. Whether it is Fully Observable or Partially Observable, and whether it is Deterministic or Stochastic/Chance.

Chess is Fully Observable, (unlike Backgammon, Monopoly or Poker for example) It is also Deterministic (like Checkers, and Go for example) Lastly, adversaries exist and because of that when determining next best move it is useful to use Adversarial Search type of algorithms such as MiniMax. Classifying a problem can help us determine what kind of search algorithm we'd want to apply. And in case of chess, Adversarial Search would be fit.

Minimax in particular has a

Time Complexity is $O(b^n)$

Space complexity of $O(bm)$ (depth-first)

So in case of chess, b would be 35, and m would be 100 There are ways around it or strategies for making it more efficient, like alpha-beta cutoff.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Also worth noting in this context, that end games for chess for up to few pieces are already tabularized - a further optimization. $\endgroup$
    – BartoszKP
    Feb 10, 2014 at 12:55
  • $\begingroup$ This is the normal approach but not a machine-learning approach. The question uses the Machine-learning tag. $\endgroup$
    – Frames Catherine White
    Feb 11, 2014 at 4:14
  • $\begingroup$ @Oxinabox although that used to be true, the asker mentioned no where in the title or body that he was interested in machine learning approach, only at the end where he was sharing one example of an approach he had in mind. There's no need to restrict the problem to Machine Learning, nor a single learning algorithm (NN). $\endgroup$
    – Iancovici
    Feb 11, 2014 at 11:52
  • $\begingroup$ Indeed, this is good $\endgroup$
    – Frames Catherine White
    Feb 11, 2014 at 11:57
  • $\begingroup$ to be precise, chess is not Full Observable, since given a position we don't know, for example, has a king or a rook already moved or not, though it is important for move generation (is castling is still possible?), but a programmer can make it Fully Observable by changing position representation differentiating non-moved king/rook and moved king/rook as a different figures, though it adds some difficulties. $\endgroup$
    – Dmitriy Iassenev
    Feb 12, 2014 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.