蒙特卡洛算法C++代码
时间: 2023-08-27 15:06:53 浏览: 81
以下是一个简单的蒙特卡洛算法的C++代码示例,用于计算圆周率的近似值:
```c++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main()
{
srand(time(0)); // 初始化随机数种子
int n = 1000000; // 模拟次数
int inside = 0; // 圆内点数
for (int i = 0; i < n; i++)
{
double x = (double)rand() / RAND_MAX; // 生成[0,1]之间的随机数
double y = (double)rand() / RAND_MAX;
if (x * x + y * y <= 1) // 判断是否在圆内
{
inside++;
}
}
double pi = (double)inside / n * 4; // 计算圆周率的近似值
cout << "Pi is approximately " << pi << endl;
return 0;
}
```
该代码通过生成随机的点,判断这些点是否在圆内,从而计算出圆周率的近似值。
相关问题
亚马逊棋蒙特卡洛代码c++
以下是一个基于蒙特卡洛树搜索算法的亚马逊棋 AI 代码,使用 C++ 实现:
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 10, M = 100000;
const int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
struct Move {
int x, y, nx, ny, cnt;
};
int n, m, t, a[N][N], f[N][N][N][N], vis[N][N], st[N][N];
int q[N * N][2], hh, tt, dx[M], dy[M], cnt[M];
int dist(int x, int y, int nx, int ny) {
if (x == nx && y == ny) return 0;
if (x == nx || y == ny || abs(x - nx) == abs(y - ny)) return max(abs(x - nx), abs(y - ny));
return 2 * max(abs(x - nx), abs(y - ny));
}
int get(int x, int y) { return x * m + y; }
vector<Move> get_moves(int player) {
vector<Move> res;
memset(vis, 0, sizeof vis);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (a[i][j] == player) {
for (int k = 0; k < 8; ++k) {
int nx = i + dir[k][0], ny = j + dir[k][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny]) continue;
memset(st, 0, sizeof st);
int hh = 0, tt = -1;
q[++tt][0] = i, q[tt][1] = j, st[i][j] = 1;
while (hh <= tt) {
int x = q[hh][0], y = q[hh++][1];
for (int l = 0; l < 8; ++l) {
int nx = x + dir[l][0], ny = y + dir[l][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) continue;
int d = dist(i, j, nx, ny);
if (d >= t) continue;
if (a[nx][ny] == 3 - player) {
tt = -1;
break;
}
q[++tt][0] = nx, q[tt][1] = ny, st[nx][ny] = 1;
}
}
if (tt == -1) continue;
for (int l = 0; l <= tt; ++l)
if (!vis[q[l][0]][q[l][1]]) {
vis[q[l][0]][q[l][1]] = 1;
res.push_back({i, j, q[l][0], q[l][1], tt + 1});
}
}
}
return res;
}
int dfs(int player, int depth) {
if (depth == 0) return 0;
auto moves = get_moves(player);
int res = -1;
for (auto move : moves) {
int x = move.x, y = move.y, nx = move.nx, ny = move.ny, cnt = move.cnt;
a[nx][ny] = player, a[x][y] = 0;
int t = dfs(3 - player, depth - 1);
a[x][y] = player, a[nx][ny] = 0;
if (t == -1) return -1;
res = max(res, cnt - t);
}
return res;
}
void init() {
memset(f, -1, sizeof f);
queue<int> q;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (a[i][j] != 0) {
f[i][j][i][j] = 0;
q.push(get(i, j));
}
while (q.size()) {
int t = q.front();
q.pop();
int x = t / m, y = t % m;
for (int k = 0; k < 8; ++k) {
int nx = x + dir[k][0], ny = y + dir[k][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (f[x][y][nx][ny] == -1) {
f[x][y][nx][ny] = f[x][y][x][y] + 1;
q.push(get(nx, ny));
}
}
}
}
int eval() {
vector<int> p1, p2;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (a[i][j] == 1)
p1.push_back(i * m + j);
else if (a[i][j] == 2)
p2.push_back(i * m + j);
int res = 0;
for (int i = 0; i < p1.size(); ++i)
for (int j = 0; j < p2.size(); ++j)
res += f[p1[i] / m][p1[i] % m][p2[j] / m][p2[j] % m];
return res;
}
int dfs2(int player, int depth, int lf, int rf) {
if (depth == 0) return eval();
auto moves = get_moves(player);
if (moves.empty()) return lf - rf;
int res = -1e9;
vector<int> cnts;
for (auto move : moves) {
int x = move.x, y = move.y, nx = move.nx, ny = move.ny, cnt = move.cnt;
a[nx][ny] = player, a[x][y] = 0;
cnts.push_back(cnt);
res = max(res, -dfs2(3 - player, depth - 1, -rf, -lf));
a[x][y] = player, a[nx][ny] = 0;
lf = max(lf, res - cnt);
if (lf >= rf) break;
}
return res;
}
void MCTS(int player, int depth) {
auto moves = get_moves(player);
if (moves.empty()) return;
int ucnt = moves.size();
int sum = 0;
for (int i = 0; i < ucnt; ++i) {
int x = moves[i].x, y = moves[i].y, nx = moves[i].nx, ny = moves[i].ny, cnt = moves[i].cnt;
a[nx][ny] = player, a[x][y] = 0;
int t = dfs(3 - player, depth - 1);
a[nx][ny] = 0, a[x][y] = player;
if (t != -1) cnts[i] += cnt - t, sum += cnt - t;
}
double mx = -1e9;
int idx = -1;
for (int i = 0; i < ucnt; ++i) {
double val = 1.0 * cnts[i] / sum + sqrt(log(cnt[i]) / cnts[i]);
if (val > mx) mx = val, idx = i;
}
int x = moves[idx].x, y = moves[idx].y, nx = moves[idx].nx, ny = moves[idx].ny;
a[nx][ny] = player, a[x][y] = 0;
}
int main() {
cin >> n >> m >> t;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) cin >> a[i][j];
init();
int depth = 0;
while (1) {
auto moves = get_moves(1);
if (moves.empty()) {
puts("Black loses");
break;
}
if (depth >= 3) {
memset(cnt, 0, sizeof cnt);
for (int i = 0; i < M; ++i) cnt[i] = 1;
for (int i = 0; i < 100; ++i) {
int t = dfs2(1, 3, -1e9, 1e9);
if (t > 0) break;
int idx = rand() % moves.size();
int x = moves[idx].x, y = moves[idx].y, nx = moves[idx].nx, ny = moves[idx].ny;
a[nx][ny] = 1, a[x][y] = 0;
}
} else {
for (int i = 0; i < 10000; ++i) MCTS(1, 5);
int mx = -1e9, idx = -1;
for (int i = 0; i < moves.size(); ++i)
if (cnts[i] > mx) mx = cnts[i], idx = i;
int x = moves[idx].x, y = moves[idx].y, nx = moves[idx].nx, ny = moves[idx].ny;
a[nx][ny] = 1, a[x][y] = 0;
}
++depth;
auto moves2 = get_moves(2);
if (moves2.empty()) {
puts("White loses");
break;
}
int idx = rand() % moves2.size();
int x = moves2[idx].x, y = moves2[idx].y, nx = moves2[idx].nx, ny = moves2[idx].ny;
a[nx][ny] = 2, a[x][y] = 0;
}
return 0;
}
```
该代码实现了亚马逊棋的基本算法,包括:
- 蒙特卡洛树搜索算法;
- 最短路算法;
- 评估函数。
其中,`get_moves` 函数用于获取当前玩家所有合法的移动方式;`dfs` 函数用于在搜索树上搜索指定深度的节点,并返回该节点的得分(如果该节点无法到达终局状态,则返回 -1);`init` 函数用于预处理出最短路;`eval` 函数用于评估当前局面的得分;`dfs2` 函数用于在搜索树上搜索指定深度的节点,并返回该节点的得分;`MCTS` 函数用于执行一次蒙特卡洛树搜索,并更新访问次数和得分。
c++亚马逊棋蒙特卡洛代码
以下是一个简单的 C++ Monte Carlo Tree Search 实现,用于玩亚马逊棋游戏:
```
#include <bits/stdc++.h>
using namespace std;
const int N = 10, INF = 1e9;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m, turn, tot, cnt;
int a[N][N], f[N * N][N * N], pos[N * N][2], val[N * N], vis[N * N], res[N * N];
double c1 = 1.0, c2 = sqrt(2.0);
mt19937 rnd(time(NULL));
inline bool check(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m && !a[x][y];
}
inline int calc(int x) {
int ans = 0;
for(int i = 0; i < 8; i++) {
int nx = pos[x][0] + dx[i], ny = pos[x][1] + dy[i];
while(check(nx, ny)) ans++, nx += dx[i], ny += dy[i];
}
return ans;
}
inline double calcval(int x) {
return 1.0 * val[x] / (vis[x] + 1) + c1 * sqrt(log(tot) / (vis[x] + 1));
}
inline int expand(int x) {
int ans = 0;
for(int i = 0; i < 8; i++) {
int nx = pos[x][0] + dx[i], ny = pos[x][1] + dy[i];
while(check(nx, ny)) {
ans++;
f[x][++cnt] = nx * m + ny;
val[cnt] = calc(cnt);
nx += dx[i], ny += dy[i];
}
}
return ans;
}
inline int getmax() {
int ans = 1;
double mx = -INF;
for(int i = 1; i <= cnt; i++) {
if(!vis[i]) return i;
double val = calcval(i);
if(val > mx) mx = val, ans = i;
}
return ans;
}
inline int simulate(int x) {
int ans = 0;
for(int i = 0; i < 100; i++) {
int nx = pos[x][0], ny = pos[x][1];
while(1) {
int p = rnd() % 8, xx = nx + dx[p], yy = ny + dy[p];
if(check(xx, yy)) {
nx = xx, ny = yy;
break;
}
}
int t = nx * m + ny;
if(vis[t] || t == x) continue;
vis[t] = 1;
int num = expand(t);
ans += num;
}
return ans;
}
inline int getbest(int x) {
int ans = 1;
double mx = -INF;
for(int i = 1; i <= cnt; i++) {
if(!vis[i]) continue;
double val = 1.0 * res[i] / vis[i] + c2 * sqrt(log(tot) / vis[i]);
if(val > mx) mx = val, ans = i;
}
return ans;
}
inline void backpropagate(int x, int v) {
while(x) {
vis[x]++, res[x] += v, v = -v, x = f[x][0];
}
}
inline void mcts() {
int now = 1;
while(1) {
if(!expand(now)) break;
int idx = getmax();
int num = simulate(idx);
backpropagate(idx, num);
turn = -turn;
tot++;
now = getbest(now);
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
if(a[i][j] == 1) pos[++cnt][0] = i, pos[cnt][1] = j;
}
}
mcts();
int ans = 1, mx = -INF;
for(int i = 1; i <= cnt; i++) {
if(!vis[i]) continue;
if(res[i] * turn > mx) mx = res[i] * turn, ans = i;
}
cout << pos[ans][0] << " " << pos[ans][1] << endl;
return 0;
}
```
该代码实现了一个简单的 Monte Carlo Tree Search 算法来玩亚马逊棋游戏。具体来说,它首先根据当前局面扩展一个节点,然后选择一个未被访问的子节点进行模拟,得到一个评估值,最后将评估值回溯到从该节点到根节点的所有节点。根据 MCTS 算法中的公式,每个节点的价值由它的胜率和探索程度决定,这里的实现中使用了 UCB1 公式。