oggy22 / boardgames Goto Github PK

First implement hash function: Board->int64 which should be fast and with low likelihood of collision.
Secondly make the algorithm make use of it. Note, it doesn't make sense to check tables at depth<3.

See https://en.wikipedia.org/wiki/Transposition_table#Related_techniques

MNK can also have FENs, for example O3/1XXX/1X1O/O2O should represent this board:
|O| | | |
| |X|X|X|
| |X| |O|
|O| | |O|

See https://www.chess.com/terms/fen-chess

Implement array sum game where each player can take either the most-left or most-right element. The winner is the one whose sum of picks is higher.

Write several tests for minmax algorithm asking it to solve a chess puzzle mate in 1,2,3,4 moves.

Helper function may help:

void FindCheck(string pgn, string expected_fen, int moves)

Write an MD file on the experiment running 1000 random games. Include stats and few games.

https://www.chess.com/terms/en-passant

Possible implementation:

• Keep en_passant_opportunity square variable pointing to the square of the pawn which was moved 2 pieces. And keep it "empty" if no such a move was made in the previous turn.

Implement checkers to a reasonable level. Try sharing implementation with chess.

Couple of ideas for tests:

• Test where each player plays a random move. Quite after ~500 moves.
• Test: Random vs minmax(2), minmax is expected to win
• Test: minmax(2) vs minmax(4), minmax(4) is expected to win
• etc.

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

For castling move to be valid check, in this order:

• King is in its initial position
• Rook is in its initial position
• Squares in between are empty
• King is not checked
• Kind is not checked after castling
  It would be nice to check if king and rook have moved before as well.

Implement PNG for chess https://www.chess.com/terms/chess-pgn

This will facilitate looking through generated games using https://www.chess.com/analysis?tab=analysis

Tests:

• minmax(10) - draw
• 3/1XO/3 - X wins, check all 4 rotations
• 3/1X1/2O - draw, check all 4 rotations
• one move to win, check all 4 rotations
• fork and then win, check all 4 rotations

Depends on #1

Implement a function like this which will work for any board.

template <Board B, Move m>
static Move random_move(Board& B);

ChessPosition(string PNG) { }

Implement incremental minmax algorithm. For example if depth=10, the algorithm runs for depth=2 first, then 4, 6, 8 and finally 10. Each run will have killer moves initialized for the next run, thus it will speed up the search. Note that killer moves are stored per depth, so running the algorithm for depth=2 will initialize killer moves for depth=1,2, running it for depth=4 will initialize depth=1,2,3,4 etc.

This depends on #2

Using templates and if const implement something like following:

template <
int material=1,
int almost_promoted=0,
int king_protection=0,
int coverage=0
int legal_moves=0>
>
int evaluate()
{
  int ret = 0;
  if const (material > 0) ret+= material * evaluate_material();
  if const (almost_promoted) ret+= almost_promoted * almost_promoted_evaluate();
  if const (king_protection) ret+= king_protection * king_protection_evaluate();
  if const (coverage) ret+= coverage * coverage_evaluate();
}

Perform a fixed number of random chess games, for example 100. Random chess game is a game where both players take random move out of all legal moves available in each position. Get the following calculations/stats:

• How often white/back wins?
• How often is a draw? Two kings left vs stalemate.
• Average game for each category,

Perform the experiment multiple times and make sure the results are consistent.

Get minmax algorithm work reasonably well with chess, MNK and Connect4. Include alpha-beta cutting.