pwyq / fill-game Goto Github PK

Report: https://www.overleaf.com/project/6415484545139c791848c71b

• Problem Statement
• Overview
• Background
  • Fill-Game
  • Assignment 1 results
• Methods
  • Algorithms
    • Minimax
    • Negamax
    • Proof-Number Search
    • Depth-First Proof Number Search
    • Monte Carlo Tree Search
  • Algorithm Improvements and Optimizations
    • Alpha-Beta Pruning
    • Transposition Tables
    • Memory Optimizations
  • Other Improvements
    • Graphical User Interface
    • Local Area Network Play
• Experiments
  • Hardware and software setup
  • Evaluation
    • Standard tests
    • Peak Memory Usage
    • Run Time
    • Node Count
  • Algorithms and Improvements
  • Other Optimizations
    • 1D vs 2D
• Discussion
  • Algorithms
  • Improvements and Optimizations
• Future Work
  • Resource Constraints
  • Algorithms
  • Improvements and Optimizations
• Authorship Statement
• Conclusion

Just found we can try this

https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning_and_transposition_tables

https://stackoverflow.com/a/68139743/10620764

When configurationProvider is set to ms-vscode.cmake-tools in c_cpp_properties.json, VS Code uses the include information defined in the CMakeLists.txt instead of reading the includePath configs in VS Code.

A workaround is to set(IS_BUILD_GUI ON) in the CMakeLists.txt to enable Building with Qt GUI....

Can't believe I wasted almost two hours on this bullshit.

Also remove local /build, and build with VS Code's cmake

• node creation and deletion at proper timing

https://github.com/michaelbzms/MonteCarloTreeSearch

• two player
• winning condition

.*.*. should be (1, 0) 1, and ... should be (0,1) 1

• fix DFPN @Stalfoes (need to uncomment out the test cases in dfpn_test.h)
• fix minimax (all 3) @pwyq
• fix negamax (all 3) @pwyq
• fix MCTS (has abortion error right now) @Samarium150 (need to uncomment out the test cases in mcts_test.h)

Yanqing — Today at 6:05 PM
for unimportant position, if we return {1,2,3} instead of {1,2,3,4}, the time drops from 18000ms to 12000ms and still pass all current test cases
Luke — Today at 6:07 PM
How
Yanqing — Today at 6:07 PM
I think we can mark a position with different level of importance, if it's totally unimportant (e.g. the nearest important cell is 2 blocks away), then we return {1,2} possible move, it it's medium unimportant (e.g. the nearest important cell is 1 block away), then we return {1,2,3}; for important cell we keep the same
Luke — Today at 6:07 PM
How does that work
What if we just sort moves by importance
Yanqing — Today at 6:08 PM
I was trying to only return {1} or {1,2}, but those fails one to two cases
Yanqing — Today at 6:08 PM
that's also a good idea
we can have a uint to label the importance instead of the bool we are using
I'll look into this once I'm done agent-fighting

https://stackoverflow.com/questions/32185411/break-in-x-axis-of-matplotlib

ualberta: Scalable Parallel DFPN Searc

• negamax
• negamax and alpha-beta prunning

Currently, our constraint.h only works on Unix-like systems because of #include <sys/resource.h>

https://www.chessprogramming.org/Proof-Number_Search

https://minimax.dev/docs/ultimate/pn-search/

Unlike the search algorithms in the minimax family, PN search is aimed exclusively at exhaustively searching a game node to solve it, which is to say to prove that the position is a forced win for one side (or a forced draw with optimal play by both players). It can be thought of a best-first search algorithm over the game tree, examining nodes based on an estimate of their promise towards contribuing to a solution to the overall node.

Other than init pn = dn = 1, we can init pn = dn = num. of moves

https://stackoverflow.com/questions/669438/how-to-get-memory-usage-at-runtime-using-c/14927379

algorithms to test:

• PNS
• DFPN
• minimax
• minimax + ab
• minimax + ab+ tt
• negamax
• negamax + ab
• negamax + ab + tt

ab = alpha-beta pruning, tt = transposition table

https://github.com/google/googletest/blob/main/docs/advanced.md#sharing-resources-between-tests-in-the-same-test-suite

• cell colors based on who played
• accept keyboard input to select cell
• info panel
  • show two player + whose turn
  • countdown timer (for now, use timer per turn)

A useful evaluation metric might be to keep track of how many nodes were opened up / evaluated in each algorithm.

Weird bug

This function parse gtest name to integer index, e.g. SIMPLE_16 becomes 16.

Not working for the following:

this involves optimization of the Game class

this probably involves optimization of the Game class

Algorithms without transposition doesn't need to waste memory on a string id and the convertion between board ang game-string (id).

• Minimax #15
• alpha-beta #23
• Negamax #24
• #30
• minimax alphabeta transposition table #34
• move-ordering #25
• board symmetry #26
• #36
• #43
• #39
• #46

others

• MCTS solver
• df-pn variants?
• Neural Networks

The GUI is frozen when AI takes long time to search. We need a separate thread.

• solve forzen GUI
• play by AI and play by human option switch in menu

I will work on this.
#14

https://stackoverflow.com/questions/5839132/c-how-to-make-two-programs-communicate

https://stackoverflow.com/questions/32324199/best-way-for-communication-between-applications-to-one-application

• Time constraint and Memory constraint on all agents @Samarium150
• update best-move method when constraint is applied @pwyq

https://stackoverflow.com/questions/29578354/qt-raise-segmentation-fault-core-dumped-when-qapplication-exit

For better extendability and easier maintenance

test between totally different IPs
test between two windows machines
test between unix and windows machines

right now the performance is very bad across very different IPs; only work within house IPs

• investigate 2d vs 1d performance (time and memory usage)
• report data (in release mode), better averaged over multiple runs

optional:

• let cmake build the test (under /test/other_tests/)
• auto the test to run multiple times

I find this is a pretty good example.
https://github.com/davda54/pn-search/blob/master/Gomoku/pn_node.h