/board-m-n-k

Tic Tac Toe generalization board game

Primary LanguageScalaMIT LicenseMIT

m-n-k board

Codacy Badge Build Status codecov Codacy Badge Quality Gate Status Bugs Code Smells Coverage Duplicated Lines (%) Lines of Code Maintainability Rating Reliability Rating Security Rating Technical Debt Vulnerabilities Known Vulnerabilities

Special case is (3,3,3) that is tic-tac-toe

Tic-tac-toe

It includes an easter egg.

Generalized M,N,K game

  • 2 players
  • p players (MNKP)

Connect 4

  • define the basic rules and write tests

Connect 5

  • generalize 4-in-a-row to 5

Connect K

  • proportionally defining the board size
  • accepting also N,M for the board size
  • generalize in connect N

Minimax

  • done

Negamax

  • done

Alpha-Beta

  • done

Basic score function

return just 1, 0, -1.

depth optimization score function

combined with a less depth solution to gain a higher score, it reduces the search space even more when pruning.

score + (Signum(score) * (1.0 / (depth + 1.0) ))

Probably does not improve. [Double check from AlphaBeta and above for improvements, benchmark]

Transposition Table

basic hash function flattening the board of string value statuses.

improved hashing function

  • ???

Zobrist Hashing

  • implement
  • bitmap?

improved game dynamics

As a the board get bigger, performances start to be an issue. Here some techniques designed/reviewed to speed-up the game-dynamics

endgame

  • can be ended only when at least 2k-1 moves are done, so avoid to check if depth is lower than 2k-1 and just return false or do not check at all.

  • keep a counter of empty cells, each time and modifying accordingly when do/undo a move check directly if the counter is equal zero to determine end game.

Board status look up

  • considering delta changes in the board, keeping the previous check board value (no winners) and check only around the move done instead of all the board.

moves generations

  • detect quickly if next move would be a winner, so put it as first one in moves generation Possible with counters for rows,cols and diags when reach K-1 value, the first move is the one that make the score in the generations.

  • So check if player can win in this turn and than do that move only. all others can be pruned directly.

  • if the next turn the opponent can win, generate only that move and all other can pruned directly.

  • Order for moves could be by max symbols for row, cols, diags in case of tie, otherwise sort descending. So it should end up quickly and start pruning more. It is important to be very fast in the ordering and pruning enough.

Board representation

from 2D array to 1D.

  • replace with 1D array and compute the moves as i*n+j for the exact index position
  • simplify the checking of end game looking around the value and moving trough the array.
  • simplify hashing.
  • consider to use a bit board for each player to represent the game.

BitBoards

  • only TicTacToe 2 players (represent with 18 bit => 32 (Int32/Short x64))

Principal Variation

MTD-f

Best_Node_Search

Monte Carlo Tree Search

  • basic implementation
  • Pruning
  • RAVE
  • Transpositions
  • multi threading

AlphaZero

  • Reinforcement Learning
  • Residual CNN (?)
  • GAN
  • Q Learning
  • DQN
  • Save/Load Model(s)
  • game state encoders

Network

  • pooling
  • softmax

Loss function

  • MSE
  • cross-entropy

Game State Encoders

  • basic
  • byte Array
  • bit boards
  • connected/related to TranspositionTable

Genetic Algorithm

Results

references