1 Bots
jannis edited this page 5 months ago

Flang Bots

This page is meant to explain my ideas behind the flang bots that currently exists to any interested person. I have to say that they are easy to beat IF you're more or less a good player (not me btw lol). If I really concentrate, I can beat them most times.

At the moment there are two bots. In theory they are exactly the same bots but due to some minor differences their playing character is a lot different.

The basic idea

Please look at explanations for the Minimax algorithm. It searches for the best move for white and plays the best countermove for black and so on until it reaches the maximum depth. White tries to make the board value positive and black negative.

Code for the java bot can be found here.

Board evaluation

For the algorithm to work, it needs a function that determines a value for a board. 0 is neutral, positive is good for white and negative is good for black.

The board evaluation consists of more than one value that are summed using weights in the end:

  • Matrix evaluation
  • Movement evaluation: counts the possible moves for each side
  • Piece value evaluation: sums the values of each piece on the board
  • Kings evaluation: how far the king has come to the opponents baseline

Matrix evaluation

"Matrix" because the board squares form a matrix. Each square gets a value and all are summed. The value for each square is made up of these:

  • which piece has occupied the square
  • how much white threats it has
  • how much black threats it has
  • weight

The weight is 1 in most cases. When the king moves forward, the squares ahead from him will get higher weights so rushing to the baseline is prevented.

When calculating the threats by a king, the king gets a range of TWO because it can move double as fast as any other piece (freeze). This has proven to make the bot play a lot better.

Pruning

I'm using alpha-beta pruning. Please search for your own, there are great tutorials.

The pruning works better if better moves are calculated first. Good move ordering can do wonders here. Still needs improvement.

If you know any other good pruning methods, take a look at the current implementations :)

Current development

There are two bot implementations at the moment:

Kotlin/Java (Classic Bot)

The default bot which is shipped in the client. It is capable of searching with depth 4 on PCs and 3 on mobile devices. 5 is possible but slow.

The Classic bot has a pretty good evaluation and has no problems with the rules/wrong moves afaik. Unfortunately it is slow because it creates lots of objects during each evaluation.

It clones the board when going deeper.

D (Neo Bot)

Alternative bot written in D. It is capable of searching with depth 5 on PCs. 6 is possible but slow.

The Neo bot can achieve a higher depth but plays weaker because there are things wrong!

It does not clone boards but does the moves and undos them afterwards.

Wrong things:

  1. something is wrong with the pruning. if I reverse the order of the moves, the result is different. This is not possible if implemented correctly.
  2. the flanger has rays that overlap. Threatened squares are taken into account twice. This is not too bad but results in a different matrix evaluation.