Monte Carlo Method in 7 Minutes

Marchete

13.4K views

GitHub

This is a preview

This playground version isn't public and is work in progress.

Previous: Area Calculation - Subtraction Next: Final Words

Searching Combos in games

In that example we have an hypothetical Scrabble game, with the following rules:

Rules

** Movements **

The basic move for a player consists of 9 letters (from a to z). They can be repeated.

** Turn Limit **

Turn time limit: 100ms

** Base Scoring **

Words starting with a,e,i,o or u scores 6 points.
a to c scores 1 point.
d to o scores 2 points.
p to z scores 3 points.
Words ending with p,q,r,w or z scores 3 points.

** Combos **

ma,or,ed multiplies *2 the base scoring.
nom,omg,lol,afk multiplies *3 the base scoring.

** Super Combo **

The word 'codingame' gives 500 points.

Using Monte Carlo

With Monte Carlo first we need the correct evaluation function. We simply code the rules inside an eval() function, that inputs a move and outputs an score.

Then we just need to randomize a lot of possible moves, evaluate them and keep the best.

Search Combo

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //To enable optimizations in Codingame
#include <bits/stdc++.h> //All main STD libraries
using namespace std;
//{Timer struct
#define TIMEOUT 95000 //95 ms timeout
#define Now() chrono::high_resolution_clock::now()
static struct Stopwatch {
  chrono::high_resolution_clock::time_point c_time,c_timeout;
  void setTimeout(int us){c_timeout=c_time+chrono::microseconds(us);}
  void Start() {c_time=Now(); setTimeout(TIMEOUT);} 
  inline bool Timeout(){return Now()>c_timeout;}
  long long EllapsedMicroseconds(){return chrono::duration_cast<chrono::microseconds>(Now()-c_time).count();}
  long long EllapsedMilliseconds(){return chrono::duration_cast<chrono::milliseconds>(Now()-c_time).count();}
} stopwatch;//} Stopwatch
const int MOVE_SIZE = 9;
/** 
 @brief Evaluate the Score of a given move
 @param move Array of letters
 @return int Resulting Score of that move
*/    
int eval(const string& move){
//Base Score 
 int BaseScore = 0;
 const string vowels = "aeiou";
 if (vowels.find(move[0]) != std::string::npos) BaseScore+=6;
 for (int i=0; i < MOVE_SIZE; ++i)
 {
  if ((uint8_t)(move[i])<=(uint8_t)('c')) BaseScore+=1;
   else if ((uint8_t)(move[i])<=(uint8_t)('o')) BaseScore+=2;
    else BaseScore +=3;
 }
 const string ending = "pqrwz";
 if (ending.find(move[MOVE_SIZE-1]) != std::string::npos) BaseScore+=3;
//Multipliers
 int Multiplier = 1; 
 for (int i=1; i < MOVE_SIZE; ++i)
 {
   if (move[i-1] == 'm' && move[i] == 'a') Multiplier *= 2;
   if (move[i-1] == 'o' && move[i] == 'r') Multiplier *= 2;
   if (move[i-1] == 'e' && move[i] == 'd') Multiplier *= 2;
 }
 for (int i=2; i < MOVE_SIZE; ++i)
 {
   if (move[i-2] == 'n' && move[i-1] == 'o' && move[i] == 'm') Multiplier *= 3;
   if (move[i-2] == 'l' && move[i-1] == 'o' && move[i] == 'l') Multiplier *= 3;
   if (move[i-2] == 'o' && move[i-1] == 'm' && move[i] == 'g') Multiplier *= 3;
   if (move[i-2] == 'a' && move[i-1] == 'f' && move[i] == 'k') Multiplier *= 3;
 }

If you look closely, the Monte Carlo method usually ends up with combos like nomg, because it's both nom and omg combo, and it's just 4 letters.

On the other hand, it's highly unlikely that Monte Carlo retrieves the SuperCombo. The SuperCombo is an exact set of ordered characters. And as Monte Carlo is pure random, the chances of getting a SuperCombo is 1 in 25^9.

Monte Carlo doesn't know anything about creating combos, he just make thousands of random moves and keeps the best.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

This is a preview

7/8 Searching for a combo

Searching Combos in games

Rules

Using Monte Carlo