markzh / genetic_chess Goto Github PK

Instead of modifying the source code when running different simulations (especially in gene pool runs), create a method for reading from a text file for parameters like number of pools, game time limits, interbreeding intervals, etc.

And respond accordingly (e.g., if san is rejected, send coordinate moves (see issue #29), etc.).

Commentary should be held by the player and then queried after the game is done for writing the PGN file. This should have much simpler logic than keeping everything in the board (one less mutable data member, too).

I.e.,

if(this == &other)
{
   return *this;
}

Currently, after a draw kill, one player is left intact and the other is replaced by the offspring of the intact one, meaning an entire organism is deleted, which is a harsher penalty for those genes than losing. The offspring should replace the parent, so that some of those genes persist.

Currently, if A and B draw, the gene representation looks like this (assuming A is randomly chosen as the winner):

Before:
A: 1.0
B: 1.0

After:
A: 1.5 (1 for the intact copy and 0.5 for the offspring after mating with a random Genetic_AI)
B: 0 (just killed off. If this had been a win/loss game, it would have 0.5 representation)

Should be:

After:
A: 1.0 (left alone, but no reward for genes)
B: 0.5 (replaced with offspring, but some genes persist)

Use

isOctave = exist('OCTAVE_VERSION', 'builtin') ~= 0;

so scripts can be run with MATLAB or GNU Octave.

Line from: http://stackoverflow.com/questions/2246579/how-do-i-detect-if-im-running-matlab-or-octave

Also need a shortcut if the move does not start with an uppercase letter (e.g., "e2e4").

Keep running total of positions examined and time spent thinking and output result in destructor. Compare with genetically determined speed.

class Genetic_AI
{
    static std::ofstream speed_record;
    ~Genetic_AI() { speed_record << get_id() << total_nodes_visited << time_taken << nodes_visited/time_taken << '\n'; }
    size_t total_nodes_visited;
   double time_taken;

    GAI::choose_move(...)
    {
        ...
        nodes_visited += nodes_this_move;
        time_taken += (time_start - time_end);
        ...
    }
}

std::ofstream Genetic_AI::speed_record("speed_record.txt");

Something like:

Game_Tree_Result game_tree_search(...)
{
    // ...
    auto best_result = ...; // first move
    if(alpha.corrected_score(perspective) == Math::win_score && alpha.depth <= depth)
    {
        return alpha;
    }
    // ...
}

An enhancement for Genetic_AI:

Save the comments from the last move. Then, when examining the next move, if a move matches the commentary from the last move, move that move to the front of the list. Perhaps as follows:

Complete_Move Genetic_AI::choose_move(const Board& board, ...)
{
    // ...
    auto previous_commentary = String::split(this->previous_comment);
    auto result = game_tree_search(board, ..., previous_commentary);
    this->previous_comment = result.comment;
    return result.move;
}

Game_Tree_Search_Result Genetic_AI::game_tree_search(const Board& board,
                                                     ... ,
                                                     const int depth,
                                                     ... ,
                                                     const std::vector<std::string>& previous_commentary)
{
    auto all_legal_moves = board.all_legal_moves();
    if(previous_commentary.size() >= depth + 2 && previous_commentary[depth + 1] == board.get_game_record().back())
    {
        for(size_t i = 0; i < all_legal_moves.size(); ++i)
        {
            if(all_legal_moves[i].game_record_item(board, ...) == previous_commentary[depth + 2])
            {
                std::swap(all_legal_moves[0], all_legal_moves[i]);
                break;
            }
        }
    }
    // continue with searching and pass on unaltered previous_commentary to recursive calls
}

CECP: https://www.gnu.org/software/xboard/engine-intf.html#10

Officially, CECP does not accept Nc3-style notation, but b1c3. In Board, create a member std::string last_move_coordinates and in Board::submit_move() assign it by last_move_coordinates = move->game_record_item_coordinate(). The CECP_Mediator should then call send_move(board.last_move_in_coordinates()) or similar.

or some other equivalent build system. Maybe it's finally time to learn CMake ...

Have a static int in the play_game() function in order to assign an ID to each game, especially in a gene pool run to make finding a game record easier.

https://en.wikipedia.org/wiki/Zobrist_hashing

Could be faster than constructing an FEN string for use with the std::map<> repeat_count. Hash changes go in make_move() method.

New gene needed to calculate how well protected the king is--i.e., how surrounded by pieces of the same side.

Perhaps something like: count the number of unguarded squares that, if the correct opponent piece was there, would have the king in check. If a square is guarded/able to be attacked by a friendly piece, then that serves as a disincentive for an opponent to place a piece there.

Right now, the Confinement of King gene sometimes causes the king to walk out into the middle of the board.

Solution idea: get_leaf_score() returns a std::tuple<Complete_Move, double, Color> indicating:

• Complete_Move: the best move,
• double: the score it lead to on the furthest leaf of the game tree, and
• Color: the perspective from which the score was calculated.

The reason for the duplicated code was that choose_move() returned a move while get_leaf_score() returned a score/color pair. The solution is to combine all the return values and let each function pick off what it wants. This way, choose_move() can be reduced to a call to std::get<0>(get_leaf_score(board, ...))

In the overloaded methods of the derived classes of Move, Move::is_legal() needs to be first in order to make sure that the starting and ending squares are inside_board().

Probably want to break up the code in Move::is_legal() into the following:

• inside_board(start/end square)
• piece_and_move_compatible(start square, move)
• not_blocked(start square, end square)
• not_capturing_own_piece(start square, end square)
• king_not_in_check_afterwards()

so that making sure the king is not in check comes after every other check.

Something like:

// After next_board.submit_move() and after Checkmate/Game_Ending catch blocks
if(alpha.corrected_score(perspective) == Math::win_score && alpha.depth <= depth + 2)
{
    continue; // no better result will be found down this branch
}

This function should be split up into remove_outer_whitespace() and consolidate_inner_whitespace(). In the Config_File class, file names with multiple consecutive spaces are mangled by the remove_extra_whitespace() function.

Commit 4570bbf fixed one problem with the Board::square_attacked_by() method. However, the method needs another fix so that it returns true for when a piece is attacked a square when that square is occupied by a piece of the same color. This is necessary to determine if a piece is guarded by another piece.

The fix is to remove the conditional and always place a Piece of the opposite color on the queried square. Also, move the place_piece() line outside both loops.

Procedure:

1. Generate a list of random Genetic_AIs.
2. Write this list to a file.
3. Pick a random Genetic_AI from the list and write it to another file.
4. Read the same ID Genetic_AI from the list file and write that loaded AI to a third file.
5. Make sure the second and third file are identical.

Two examples:

[White "Genetic AI 18419"]
[Black "Genetic AI 18465"]
[Result "0-1"]

1. e4 e5
2. Qh5 g5
3. Bb5 c6
4. Bc4 d5
5. Be2 dxe4
6. Kf1 Bb4
7. d4 exd3
8. Bf3 e4
9. Bxe4 Bd7
10. Be3 Nf6
11. Qxg5 Nxe4
12. Qxd8+ Kxd8
13. h4 Kc8
14. cxd3 Nd2+
15. Nxd2 Bg4
16. f3 Be6
17. Ne4 Kd8
18. Ne2 c5
19. Nf6 Nc6
20. Bf4 Kc8
21. Rc1 c4
22. g4 Bc5
23. Kg2 c3
24. Rxc3 Bb6
25. d4 Kd8
26. Bd6 Ne7
27. Rd1 Bxa2
28. g5 Be6
29. Kh2 h5
30. Ra1 a5
31. g6 fxg6
32. f4 Bf5
33. Rg1 Ba7
34. Bc7+ Kc8
35. Bb6+ Nc6
36. Bxa7 Rxa7
37. Ra1 Kb8
38. d5 Nb4
39. Nd4 b6
40. Nxf5 gxf5
41. Re1 Rg7
42. Nd7+ Rxd7
43. Rg1 Kb7
44. Rg6 Ka7
45. Rc7+ Rxc7
46. Rg2 Re8
47. d6 Rd7
48. Rd2 Re3
49. b3 Rg7
50. Rf2 Kb8
51. d7 Rxd7
52. Rg2 Kb7
53. Rf2 Rc3
54. Re2 Ka6
55. Rf2 Kb7
56. Re2 Ka6
57. Rf2 Ka7
58. Re2 Kb7
59. Rf2 Rd8
60. Re2 Ka6
61. Rg2 Rd7
62. Re2 Rc8
63. Re8 Rxe8
64. Kg2 Re2+
65. Kf3 Rdd2
66. Kg3 Nc2
67. Kh3 a4
68. Kg3 a3
69. Kh3 a2
70. Kg3 a1=R
71. Kh3 Ra2
72. Kg3 Ra1
73. Kh3 Ra2
74. Kg3 Ra3
75. Kh3 Ra1
76. Kg3 Ra2
77. Kh3 Ra1
78. Kg3 Ra2
79. Kh3 Ra3
80. Kg3 Ra4
81. Kh3 Ra3
82. Kg3 Ra4
83. Kh3 Ra5
84. Kg3 Ra3
85. Kh3 Ra4
86. Kg3 Ra5
87. Kh3 Ra4
88. Kg3 Ra5
89. Kh3 Rb5
90. Kg3 Ka7
91. Kh3 Ka6
92. Kg3 Ka7
93. Kh3 Kb7
94. Kg3 Ra5
95. Kh3 Ra4
96. Kg3 Ra3
97. Kh3 Ra2
98. Kg3 Ra1
99. Kh3 Ra2
100. Kg3 Ra1
101. Kh3 Ra3
102. Kg3 Ra2
103. Kh3 Ra1
104. Kg3 Ra2
105. Kh3 Ra1
106. Kg3 Ra3
107. Kh3 Ra4
108. Kg3 Ra5
109. Kh3 Ra3
110. Kg3 Ra6
111. Kh3 Ra5
112. Kg3 Ra6
113. Kh3 Ra5
114. Kg3 Ra7
115. Kh3 Ra6
116. Kg3 Ra7
117. Kh3 Ra6
118. Kg3 Ra8
119. b4 Ra7
120. b5 Ra5
121. Kh3 Ra4
122. Kg3 Ra3#	0-1


{ Initial time: 300 }
{ Moves to reset clocks: 0 }
{ Time left: White: 0.156967 }
{            Black: 7.10659 }

Black should have mated with 75. ... Rxb3# (on several occasions), or 119. Ra3# (which it finally found on the last move).

Another example:

[White "Genetic AI 18374"]
[Black "Genetic AI 18468"]
[Result "1-0"]

1. e4 e5
2. Qh5 g5
3. Bb5 c6
4. Bc4 d5
5. exd5 Bf5
6. d6 Qxd6
7. Qxf7+ Kd8
8. Qxf5 Bg7
9. Qxg5+ Ne7
10. Qxg7 Re8
11. d3 Qb4+
12. Nc3 Nd5
13. Bg5+ Kc8
14. Bxd5 cxd5
15. Kf1 Qg4
16. Nxd5 Na6
17. Nb6+ axb6
18. Qxh7 Qxg5
19. Qh3+ Kd8
20. g3 Nc7
21. Re1 Rxa2
22. Qh7 Rxb2
23. Qf7 Rh8
24. h4 Qg4
25. Qf6+ Kd7
26. Qxh8 Rxc2
27. Qh7+ Ke6
28. Qh6+ Kf7
29. Qh7+ Kf6
30. Qh6+ Qg6
31. Qf8+ Ke6
32. Qc8+ Kf6
33. Qf8+ Ke6
34. Qc8+ Kf6
35. Qd8+ Ke6
36. Rxe5+ Kxe5
37. Nf3+ Ke6
38. Nd4+ Kf7
39. Nxc2 Ne6
40. Qd7+ Kf6
41. Ke1 Nf8
42. Qd6+ Ne6
43. Ne3 Qg7
44. Kd2 b5
45. Ra1 b4
46. Qxb4 Qh6
47. Qc3+ Kf7
48. f4 Qh5
49. g4 Qxh4
50. Qc4 Qh2+
51. Kd1 Qh1+
52. Nf1 Qxf1+
53. Kd2 Qxa1
54. g5 Qb2+
55. Ke3 Qd4+
56. Qxd4 Nxd4
57. Kxd4 Ke6
58. g6 Kf6
59. Kd5 Kxg6
60. Ke6 Kg7
61. f5 Kh6
62. Kf6 Kh5
63. Kg7 Kg5
64. f6 Kh5
65. f7 Kh4
66. Kg6 Kh3
67. Kg5 Kh2
68. Kg4 Kh1
69. f8=Q Kg2
70. Qf3+ Kh2
71. Qxb7 Kg1
72. Qb2 Kh1
73. Kf3 Kg1
74. Qa2 Kh1
75. Qb2 Kg1
76. Qa2 Kh1
77. Qc2 Kg1
78. Qb2 Kh1
79. Qa2 Kg1
80. Qb2 Kh1
81. Qa2 Kg1
82. Qc2 Kh1
83. Qd2 Kg1
84. Qc2 Kh1
85. Qd2 Kg1
86. Qe2 Kh1
87. d4 Kg1
88. d5 Kh1
89. d6 Kg1
90. d7 Kh1
91. d8=R Kg1
92. Rc8 Kh1
93. Rb8 Kg1
94. Ra8 Kh1
95. Ra7 Kg1
96. Ra6 Kh1
97. Ra5 Kg1
98. Ra4 Kh1
99. Ra3 Kg1
100. Ra2 Kh1
101. Ra1#	1-0


{ Initial time: 300 }
{ Moves to reset clocks: 0 }
{ Time left: White: 5.67565 }
{            Black: 16.5472 }

White should have mated many times starting at 74. Rf2# or 74. Rg2#.

Small values for poisson probability results in divide by zero or zero/zero return values.

See if there is a performance issue or if the code becomes easier to read.

Specifically the negamax version: https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning

If a population is too homogeneous, evolution grinds to a near halt.

Instead of deciding how many moves to look ahead, decide how many positions to examine (more abstractly, how many nodes in the game tree to examine). Divide this number equally among all legal moves and recurse. If the number of positions to examine is zero, return the board evaluation.

This way, complex positions with lots of legal moves can be explored fully while allowing simpler positions with few legal moves (end games, forced moves from check, etc.) can be examined in depth.

The calculation is something like:
(fraction of time to use)*(time left) = (number of positions to examine)/(positions examined per second)
Resulting in:
(positions examined per second)*(fraction of time to use)*(time left) = (number of positions to examine)
Since (positions examined per second) and (fraction of time to use) are a priori unknown and, by hypothesis, constant, the product of these two values will be the value stored in the Look_Ahead_Gene::look_ahead_constant. The Look_Ahead_Gene::look_ahead() function no longer needs the number of possible moves as input.

Show scores and alternate play lines when replaying games by loading the Genetic_AI id.

Also, allow loading game by Round number for files with multiple games.

Pick a game to replay and have the players write out their analysis of each move to a new file. Analysis should include the predicted final board state for each move and the scores for each.

genetic_chess --analyze_game <game_file>.txt <game_id>

<game_id> can consist of a game number (not implemented yet) or the IDs of the white and black player in order.

Check every piece on board.

If there's a pawn, queen, or rook, game continues.

Draw if only pieces are:

• king vs. king
• king vs king and 1 or more bishops of same color
• king vs king and 1 knight
• king and 1 bishop vs. king and 1 bishop with same color bishops

Continue otherwise.

Inspired by: https://codereview.stackexchange.com/a/94503/56343

Keep a list of all possible moves from all possible squares, instead of considering all possible moves every time. When calling all possible moves, only filter out illegal moves. This will eliminate a lot of legaility checking. Example, a bishop in a corner only has 25% of its possible moves landing on the board. This will also save time for position-specific legality checks (En Passant, Promotion, etc.),

class Piece
{
    ...
    std::vector<std::vector<Complete_Move>> Piece::all_moves_from_all_squares;
    ...
}

std::vector<Complete_Move> Piece::all_legal_moves(board, file, rank) const
{
    return all_moves_from_all_squares[Board::board_index(file, rank)];
}

And for each Piece subtype:

Bishop::Bishop()
{
    ...
    if(Board::inside_board(file_end, rank_end))
    {
        all_moves_from_all_squares[Board::index(file_start, rank_start)].push_back({std::make_unique<Move>(file_change, rank_change), file_start, rank_start});
    }
}

Or something like this. There's a small complication in how the smart pointers should be used.

Pawn promotion is currently seen as simply removing a pawn from the board, lowering the score given to a board. This causes pawns to get stuck on the 7th/2nd rank. There needs to be a promotion bonus method that searches through the board's move history and adds a bonus for promoted pawns (search for "=") weighted by the strength of the resulting promoted piece (from Piece Strength Gene).

Some games end in draws when the Genome::evaluate() should return a positive score for any other move.

All Square functions can be moved elsewhere:

• has_moved() should be a Piece method/property
• the en passant target is a Board property
• the Pieces should be stored in the Board in a std::vector<Piece*>

Outside player takes FEN string from GUI and calls play_game_with_board().

Command line option: -fischerrandom

Very often, the genes that limit look ahead (branch pruning and last minute panic) completely negate any look ahead (e.g., last-miniute panic time > game time). This is especially common with 10-second games.

Possible solution, start with 10-second games to get a decent optimizing of board evaluation genes, and slowly increase game time--say, 1 second per hundred games.

In Genetic_AI::search_game_tree(), have option for using std::async() instead of recursing for parallel game tree searching.

Genetic_AI constructor needs a parameter to say how many processors it can use.