HOW TO TOUCH THE COMPUTER TO PLAY RENJU
I have found rather an effective way to teach a computer to play renju and
gomoku. These games attracted me with a special simplicity of rules. Maybe
it's because I'm a physisist by education.
The aim in both renju and gomoku is to build a continuous row of five
belonging to the player stones in the squares of a 15x15 playing board.
Unlike chess, where the number of pieces decreases during the game, in renju
and gomoku their number increases and so does the number of their types. The
word "piece" here means not single stones but their certain geometrical combin-
ations. Along only any line the number of combination types exceeds 20.
In order to play renju well you must at least recognize these combinations.
Large number of combinations in renju makes purely scanning approach
impossible. Maybe that explains why authors of the first algorythms dropped
the scanning approach altogether. They based their decision on the supposition
that it was possible to build an ideal choice function as a function of state
of 40 squares belonging to lines which are crossing on the analyzed square.
But a simple example refutes this contention. It's easy to cite a position
where the winning quality of a move to a certain square is affected by state
of another square on the opposite side of the board. So even if there exists
an ideal value function it is a function of a much greater number of squares
most likely of all squares on the board. Nobody could build such a function
yet.
The most intricate thing in building an effective algorythm for games with
high coefficient of branching is to find a reasonable ratio between the
quantity of the needed scanning which depends on the quickness of the algorythm
and the effectiveness of the choice function.
A good choice function allows us to reduce the number of scanned variants
for a certain position and to increase the probability that those scanned
variants will include one of the best moves.
As a rule the more effective the function the higher price in calculation
we have to pay. So we have to reduce the tree to scan.
On the other hand if we use a simple choice function for games with
high coefficient of branching we get an interesting effect. With large
quantities of scanning the quality of playing nearly stops to grow with the
growth of scanned volume. It is easily understandable if you take into account
that in order to get a reliable appraisal of the situation on a greater depth
we shall have not only to deepen but also to widen the tree on all lesser
depths. Otherwise mistakes will happen.
To my mind most of renju programs which exist now on modern computers reach
this threshold of scanning "saturation". Experience shows that the more
intricate the euristics are used in a program the better it plays.
Maybe it will be appropriate to make a comparison with a human brain here.
Most games played by a man have such a wide variety of possible choices that
a scanning approach is out of the question. So Nature didn't strive to endow
a human with an ability to go through a million of possibilities a second.
Instead it gave him the ability to choose one-two variants out of a multitude.
It's called intuition.
So a realistic way to building effective algorythms which analyse multi-
possibility situations goes through improvement of choice functions.
For instance, a strong effect can be achieved through use of a dymamic
choice function which forms the next move not only upon the analysis
of a static position but also upon the information which comes up in the
process of scanning. Such a function imparts goal-oriented quality to the
process of scanning.
Artyom Shaposhnikov