merkrafter / sanjego Goto Github PK

The alpha beta search should sort child nodes in order to produce more cut-offs

There is a new rule set module now.

Due to a miscommunication concerning the requirements, the rule set must be split in 4 (in addition to #5):

• players may move their towers on opposing towers only
• players may move any tower
• players may move any tower that they control by a majority of bricks
• players may move towers to all 8 (instead of 4) surrounding fields

(The current implementations is a rule set that combines all of the above rules)

The move ordering using only the immediate game values does not help on the first move(s) as (almost) all moves are equally good. Unfortunately, this is where most of the branching happens. Hence, some more opening assistance is needed. Two ideas come into mind:

implicit opening "book"

Experience shows that moves in the middle of the board are generally more valuable than moves at the border.

• add/subtract a gaussian-like bias to moves in the middle of the board for the evaluation only

explicit opening book

This needs more investigation, but maybe for sufficiently large boards the first few moves are always the same. In this case they need to be cached and evaluated first for new boards.

• calculate first few move lines for some boards
• compare if they are equal
• save them on the disk
• load and evaluate them first later on

Minimum:

• number of nodes evaluated
• time needed

This method should be a method of the lower tower and also should be renamed to Tower.attach or similar in order to be aligned with Tower.detach

Currently, the main function sets up the game and the test functions set up a game independently. Therefore, the main function could use some configuration that the test cases don't cover. This problem should be tackled by a commonly used factory method.

Is the usage of height and width consistent with x and y?

In order to comply with the new rule sets

• run tests

• check code style

• deploy to container

• automate building the result presentation

• re-create the result presentation after experiments

RuleSet.player_may_move_tower should be independent of the GameField

Find out what exactly has to be done for fulfilling the first milestone.

As the alpha_beta_search spends a lot of time for finding the children of the current game_node, there is room for improvement.

         167128391 function calls (166949794 primitive calls) in 130.114 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000  130.135  130.135 [cProfile internals]
 178598/1    1.412    0.000  130.135  130.135 Searching.py:180(alpha_beta_search)
   178598    0.412    0.000  123.384    0.001 Searching.py:74(children)
   178598    0.811    0.000  122.972    0.001 {built-in method builtins.sorted}
   422744   27.432    0.000  122.111    0.000 Searching.py:39(_children)

One problem is that the game field is represented densely (as a list). This means that all game_field positions must be considered in every call to _children which leads to a lot of overhead, especially in the end game where many positions are empty. A much more efficient way could be to represent the game field as a dict and only iterate over existing towers.

A Move is a wrapper around a from_pos and a to_pos in the first place and thus improves readability of the program, but has some more advantages:

• can be taken back and avoid copying the board in each step of the alpha beta search
• allow rating moves in addition to boards alone
• can be propagated up the search tree and reveal the best move line(s)

It should create a GameField.setup_field call that is as simple as possible

The user can supply the value and it is passed to the GameNode constructor, but it is never passed to the actual alpha_beta_search call.

especially with respect to the many different constructor behaviors

for comparison reasons

The effectiveness of the _children method is defined as the ratio of generated useful positions to all generated positions. In the current implementation, for any from_pos all the to_pos in a 3*3 block around it are generated and then need to be checked whether they are allowed.

In the following, to make things simple, only the maximum effectiveness with a NESW neighbourhood is considered.

Imagine an m*n sized game field. Then there are (m-1)n connections between adjacent towers along one axis and (n-1)m connections in the orthogonal direction, making it at most num_useful_pos = 2*[(m-1)n + (n-1)m] if all towers can be moved by a player on top of all their neighbours.
On the other hand, there are num_total_pos = 9*mn positions generated by the current implementation, hence the maximum_effectiveness(m,n) = num_useful_pos / num_total_pos.
By simplifying this, one gets maximum_effectiveness(m,n) = (4 - 2/m - 2/n)/9 and it becomes obvious that this method will never be able to even cross the 50% mark.

This flaw scales directly with the size of the game field. It might be rewarding to tackle this problem.

Typically, there is more than one way to play the game optimally.
Therefore, the test cases for the move lists should not test for specific move lines (unless there is only a very small number of variations) but for consistency instead, that is: is this move sequence legal and does the value of the game field after all the moves matches the value returned by the alpha beta search?