Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve the max turn Algorithm #41

Open
k0vl opened this issue Mar 16, 2018 · 0 comments
Open

Improve the max turn Algorithm #41

k0vl opened this issue Mar 16, 2018 · 0 comments

Comments

@k0vl
Copy link
Contributor

k0vl commented Mar 16, 2018

At F17, this project uses a naïve estimation of maxTurn, which is modified from http://unixpapa.com/floodit/, that does a linear scaling using a baseline of 25 turn with 14x14 board and 6 color.
maxclick= Math.floor(25*((nrows+ncols)*ncolors)/((14+14)*6));
This implementation generates unplayable board at small size, and overly easy board at large size.

We have since reworked the algorithm to perform random simulation before each game, and taking the average of the top simulations as the max turn. However it is still easy at large size.

Consider implementing a greedy algorithm that maximizes cells flooded each turn, and using it as the baseline.
point estimation: 200

Consider implementing a greedy algorithm that looks ahead several turns, which would overcome certain edge cases*.
point estimation: 400

Consider implementing a neural network.
point estimation: 700

*reference: https://kunigami.blog/2012/09/16/flood-it-an-exact-approach/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant