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