Pattern matching and chess

[Artem Pyatakov]

I am currently working on a small chess engine, primarily as a learning
experience and not as an attempt to make the best engine in the world.

One thing that I've found to be an accepted belief in the AI community is
that 1) computers are much stronger at searching all combinations of moves
2) humans are MUCH stronger at board evaluation.

I've also heard that main reason humans are stronger at board evaluation is
because of "pattern matching" - seeing chess patterns. For example, a GM
supposedly knows around 50,000 different board "patterns" (of course I am
not talking about conscious knowledge).

I know there HAS been some research in chess patterns, but has it been at
all successful? Could anybody point me to any papers or sources on the
topic? In general, do you think it's a good idea to try to put this kind of
matching into my engine or should just go for the good ol' minimax stuff?
Thanks.

Artem Pyatakov

[Harris Georgiou]

Ο Artem Pyatakov <art...@home.com> έγραψε στο μήνυμα συζήτησης:
Ec3Y6.96635$G5.20...@news1.rdc1.md.home.com...

Hello :-)

I cannot say I have direct knowledge of these matters (I have only
implemented simpler board games), but as far as I know, pattern matching is
better used in relatevely small search spaces. In fact, I think that latest
versions of the Deep Blue s/w used pattern matching methods during the
opening and the endgame, in order to better evaluate the situation and
select the (historically) best response to every opponent's move. The
middle-game is usually the most difficult part because of the large
expansion factor, so it is usually more effective to implement it with
traditional tree search and prunning techniques.

Of course, rummor has it that during the last confrontation of G. Kasparov
with Deep Blue, the programmers at IBM had done so much good work in the s/w
that even the middle-game was actually using some pattern matching in order
to exploit some of the historically best-played games from human players -
and they say it included even Kasparov's own strategy characteristics. So,
it is no wonder that it was able to finally win a human player - if all
these are true, he had to be better than any human player ever played chess,
even better than himself.

PS: Sorry I don't have any links. Maybe IBM research labs have some clues on
these issues.

--

Harris

- 'Malo e lelei ki he pongipongi!'

[Shaul Markovitch]

I suggest that you look at the work of Robert Levinson from UCSC.
He wrote several papers about using patterns in chess search.

For example:
http://citeseer.nj.nec.com/148934.html
http://citeseer.nj.nec.com/context/42620/0
http://forum.swarthmore.edu/~jay/learn-game/projects/morph.html

Another source of information about this topic is
a paper by Johannes Fürnkranz:
Machine Learning In Computer Chess: The Next Generation
http://citeseer.nj.nec.com/furnkranz96machine.html

You can also look at the paper:
"Learning to play chess selectively by acquiring move patterns"
by Finkelstein and Markovitch available at
http://www.cs.technion.ac.il/~shaulm/research.html

All these papers contain references to some older related work.

"Artem Pyatakov" <art...@home.com> writes:

--
===============================================================
Shaul Markovitch, Computer Science Department
Technion - Israel Institute of Technology, Haifa 32000, Israel.
http://www.cs.technion.ac.il/~shaulm/ shaulm @ cs.technion.ac.il