Questions tagged [monte-carlo]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
33 views

Question about what exponentially small probability of success means in randomized algorithms

I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and ...
user avatar
1 vote
0 answers
14 views

How exactly are non-leaves in Monte Carlo tree search chosen?

I play around with Monte Carlo tree search and tic-tac-toe. For now I have followed the Wikipedia article. There is one place, where I am stuck, the selection phase. The given procedure is the ...
user avatar
2 votes
0 answers
52 views

Decision problem solution monte carlo

I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
user avatar
0 votes
0 answers
14 views

Can Thompson sampling performs better than ucb1 in a Monte Carlo tree search

I made a Monte Carlo tree search (MCTS) algorithm for the travelling salesman problem inspired by this paper which uses UCB1. When I was digging to see where does the UCB1 formula comes from, I read ...
user avatar
  • 101
4 votes
1 answer
377 views

Is there some kind of expected error margin for my Monte Carlo algorithm?

My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
user avatar
1 vote
0 answers
62 views

How to design an unbounded Monte Carlo algorithm for SAT(Boolean Satisfiability Problem) problem?

I want the algorithm to be in polynomial time and the correct answer rate is 0.5 or more. (True / false judgment is polynomial time) All the methods I think of take exponential time(2^n). Can anyone ...
user avatar
  • 23
3 votes
1 answer
63 views

Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$

Given alphabet $\{0,1\}$, we want to uniformly sample $x,y \in \{0,1\}^n$ such that $ed(x,y)=k$, where $ed$ denotes the Levenstein distance, i.e., the minimum number of edit operations (insert, delete,...
user avatar
2 votes
2 answers
181 views

Describe a Monte Carlo algorithm for the Triangle Packing problem

Book: Parameterized Algorithms by Marek Cygan (free to download legally) Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19: Describe a Monte Carlo $2^{3k}n^{O(...
user avatar
  • 73
1 vote
0 answers
93 views

How to avoid division by zero in UCT formula in Monte Carlo tree search?

In step 2 (expansion) of the Monte Carlo tree search algorithm, one or more child nodes are created, and one node named C is chosen among them. The simulation step is applied to C giving it a score of ...
user avatar
1 vote
0 answers
22 views

What problem is this application of simulated annealing trying to solve?

I was reading about simulated annealing on its Wikipedia page, and was drawn to a particular example illustrating the annealing schedule. Below is the picture and its description: Example ...
user avatar
0 votes
0 answers
92 views

Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set

I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start. Also, I want to devise a Mont Carlo algorithm for this problem. I would appreciate any help....
user avatar
1 vote
1 answer
38 views

MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?

Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a ...
user avatar
2 votes
1 answer
82 views

Algorithm to sample high-dimensional parameter space of expensive cost function

I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to ...
user avatar
8 votes
1 answer
1k views

What is the optimal algorithm for playing the hangman word game?

Suppose we are playing the game hangman. My opponent and I both have access to the dictionary during the game. My opponent picks a word from the dictionary with knowledge of the algorithm which I will ...
user avatar
2 votes
1 answer
211 views

What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?

I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the ...
user avatar
  • 143
1 vote
0 answers
218 views

Combining TWO Monte Carlo algorithms to get a Las Vegas algorithm that solves the same problem

I came across a problem that I have no clue how to solve. Consider two Monte Carlo algorithms, called A and B that both solve the same problem. A is true-biased and t-correct, while B is false-...
user avatar
  • 11
1 vote
2 answers
463 views

Pandemic board game - find all possible next 4 actions

I hope I am asking this on the right community. I am building an Artificial Intelligence to play the board game Pandemic. The AI uses a Monte Carlo algorithm. After implementing the game rules and ...
user avatar
  • 113
1 vote
1 answer
819 views

UCT (Upper Confidence bounds applied to Trees)

For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ? Besides, I do not quite understand how UCT deals with the flaw of ...
user avatar
  • 111
1 vote
1 answer
189 views

Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
user avatar
  • 153
2 votes
2 answers
1k views

How to find the best exploration parameter in a Monte Carlo tree search?

I've developed a Monte Carlo tree search algorithm in checkers. Here is my question. What should be the value of $C$, the exploration parameter in the following formula described in Monte Carlo Tree ...
user avatar
1 vote
0 answers
171 views

Is MCTS an appropriate method for this problem size (large action/state space)?

I'm doing a research on a finite horizon decision problem with $t=1,\dots,40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in state $s(t)...
user avatar
  • 21
1 vote
1 answer
110 views

How to decrease the confidence of a Monte Carlo algorithm in its answer?

Recall that a Monte Carlo algorithm is $p$-correct if it outputs a correct answer with probability at least $p$. In the case of decision problems, where the answer is binary, repeating the MC ...
user avatar
2 votes
1 answer
162 views

Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?

I started reading on Probabilistic algorithms and Monte-Carlo algorithms. Since a Monte-Carlo can only give a certain answer for either True or False, I was wondering if it's conceivable that for the ...
user avatar
  • 43
2 votes
1 answer
47 views

Randomly construct linear combination that is within bounds over two basis

Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that: $0 \le x_{j} \le 1$ $0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$ Matrix $A$ is about 10 x 15. I want to ...
user avatar
  • 168
0 votes
1 answer
520 views

Understanding On-policy First Visit Monte Carlo Control algorithm

I am going through the Monte Carlo methods, and it's going fine until now. However, I am actually studying the On-Policy First Visit Monte Carlo control for epsilon soft policies, which allows us to ...
user avatar
  • 125
1 vote
1 answer
95 views

Pi approximation with Montecarlo: Why not just evenly distributed points?

With the randomised algorithm for Pi approximation (see https://www.geeksforgeeks.org/estimating-value-pi-using-monte-carlo/ ), I keep wondering why just using points with an even distance should'n ...
user avatar
  • 111
3 votes
1 answer
373 views

Generate a random magic square on a large field

If consecutive natural numbers 1 .. n^2 are placed in a n*n grid so that sum of numbers in each column and in each row is a constant then we call it a magic square. I would like to generate magic ...
user avatar
  • 131
3 votes
1 answer
82 views

How do you protect an AI from a human doing "illogical" moves?

Using a monte carlo approach and evalutation function. Some moves will deemed to be more advantageous than others. As a computer plays itself, it will generally go for the best moves possible. And ...
user avatar
  • 263
4 votes
2 answers
3k views

What is the difference between Simulated Annealing and Monte-Carlo Simulations?

What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?
user avatar
  • 457
1 vote
1 answer
137 views

Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path

I am studying Nested Monte Carlo Algorithm addressing the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order ...
user avatar
3 votes
1 answer
441 views

How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

Admittedly, homework. For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this ...
user avatar
  • 179
2 votes
1 answer
378 views

What is partial expansion in Monte Carlo Tree Search?

I'm trying to understand the modification to the MCTS algorithm called Partial Expansion. From what I've been reading it enables one to not require all child nodes to have been expanded before ...
user avatar
1 vote
2 answers
5k views

Monte Carlo: what is a seed?

I have reached a chapter in the notes I am following where a program written in C++ is using a Monte Carlo method to estimate $\pi$. It mentions a 'seed', but does not say what this is. I have tried ...
user avatar
  • 123
2 votes
0 answers
41 views

Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
user avatar
1 vote
2 answers
279 views

Monte Carlo algorithm: Element in array

Design a Monte Carlo algorithm that checks in constant time if a given element $x$ is in a $n$-dimensional vector $V$. Calculate the probability for a correct answer. Then suppose $n=10$, how many ...
user avatar
2 votes
0 answers
40 views

Not grasping Bayesian Monte Carlo

I've read several sources of information that describe the process of Bayesian Monte Carlo Quadrature but am just not understanding the details enough to be able to implement it. For instance two ...
user avatar
  • 1,320
5 votes
1 answer
2k views

Generating values from a probability density function

If I have a probability density function, some f(x) which is >= 0 everywhere and integrates to 1, is there a method to generate random numbers using that PDF? I know there is the box-muller transform ...
user avatar
  • 1,320
5 votes
1 answer
151 views

Monte Carlo Tree Search in connect 5 tree design

I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm: The initial state, S0 is the board state where the ...
user avatar
1 vote
1 answer
984 views

How does MCTS handle games with large numbers of poor moves?

I am trying to understand how pure Monte Carlo tree search (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) handles games where random playout will likely result in a loss easily avoided by ...
user avatar
4 votes
2 answers
230 views

UCT1 Algorithm: What does "total number of simulations" mean?

When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula. $$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$ Wikipedia, this guy, and this guy all ...
user avatar
  • 323
3 votes
1 answer
389 views

How does the Monte Carlo Tree Search Algorithm Decide When to Expand?

I understand that the MCTS algorithm expands its tree after it has selected the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse ...
user avatar
  • 323
1 vote
0 answers
262 views

What did Dijkstra think about Monte Carlo algorithms? [closed]

In A Discipline of Programming, Dijkstra wrote: Two circumstances have changed the scene since then.* The one is the insight that, even in the case of fully deterministic machines, program testing ...
user avatar
  • 145
3 votes
1 answer
4k views

How can we get a Las Vegas algorithm from a Monte Carlo one?

I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills. Here is the exercise: Exercise 1.3: ...
user avatar
  • 970
1 vote
1 answer
757 views

How do multiple branches from one node occur with the Monte Carlo Tree Search?

I think I understand the Monte Carlo Tree search. It goes through the tree until it reaches a leaf node, where it branches (creates a child node). However, the branching only occurs at the leaf nodes (...
user avatar
  • 323
1 vote
0 answers
16 views

What use does the predictor stage in a particle filter have?

Im a bit confused about the particle filter. I understand the generic particle filter algorithm but in some literature say particle filter has predictor stage which is not mentioned in the generic ...
user avatar
2 votes
1 answer
21 views

What is a proper way of solving a multibody nonlinear problem?

I encountered some system of ~5000 random nodes connected by ~8000 non-hookean springs, with ~1300 nodes at the boundary fixed as the "wall", the potential of the springs are of the form $dx*e^{(dx/a)}...
user avatar
4 votes
1 answer
846 views

Approximate Bayesian Computation VS Monte Carlo Simulation

I am a little confused about the differences between Approximation Bayesian Computation (ABC) and Monte Carlo Methods (MCM). Citing from wikipedia: Approximate Bayesian computation (ABC) constitutes ...
user avatar
  • 195
1 vote
1 answer
75 views

How to simulate this randomized "finite" sum? [closed]

Consider the the Geometric Brownian motion $\qquad dX_t=\mu X_t dt+\sigma X_t dW_t$, with $X_0=1$, $\mu=0.2$, and $\sigma=0.30$. for each $n=1,2,3,..$ let $h_n=1/n$, and let $X^n_n$ be the final ...
user avatar
  • 111
4 votes
2 answers
336 views

Adversarial Monte Carlo Tree Search Asymmetry

Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth, growing promising subtrees more than non-promising ones. But in a 2-player adversarial game, when a win at one node is a ...
user avatar
  • 506
1 vote
1 answer
538 views

Minimizing total distance to a point from a set of points

I've read about a problem: There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal. I've written a Monte-Carlo algorithm, ...
user avatar
  • 113