Project report

I. Different strategies

• 3 different strategies:

1. The first strategy:

• i. Check if any tableau cards can go to the foundations
• ii. Move the stack of cards between tableaus
• iii. Draw card from the deck to the talon
• iv. Check if the top card from the talon can go into any of the foundations
• v. Check if the top card can go into any of the tableaus
• vi. Move the stack of cards between tableaus

2. The second strategy:

• i. Check if any tableau cards can go to the foundations
• ii. Move the stack of cards between tableaus
• iii. Do step ii until can’t move any cards
• iv. Draw card from the deck to the talon
• v. Check if the top card from the talon can go into any of the foundations
• vi. Check if the top card can go to any of the tableaus
• vii. Move the stack of cards between tableaus
• viii. Do step vii until can’t move any cards

3. Third strategy:

• i. Check if any tableau cards can go to the foundations
• ii. Move the stack of cards between tableaus
• iii. Do the first 2 steps (i, ii) until can’t move any cards
• iv. Draw card from the deck to the talon
• v. Check if the top card from the talon can go into any of the foundations
• vi. Check if the top card can go to any of the tableaus
• vii. Move the stack of cards between tableaus
• viii. Do the last 3 steps (v, vi, vii) until can’t move any cards

We compare the performance of 3 strategies by running each: 1750 games and take an average of 3 times. In conclusion, the third strategy results in the best win percentage among the 3 strategies, which is around 24%. Thus, we recommend using the third strategy.

II. Experiment on multiple threads

Steps

1. Fix the number of threads to explore the optimal number of games per thread.
2. Fix the number of games per thread to discover the optimal number of threads.
3. Compare the performance of threads simulation to linear simulation.

Notes

• Compare the performances between simulations base on the number of times (seconds) it takes to run per game.
• We didn’t choose to use the number of moves/second, because the number of moves fluctuates even when we run the same number of games.

Results

1. The result for step 1:

• We run only 44 threads and change the number of games for each thread. Then, we take the average of the time it takes to run a game over 3 runs.
• Observation: The performance didn’t improve above 3080 games which are 70 games per thread. Thus, the optimal number of games per thread is 70 games.

2. The result for step 2:

• We run 70 games per thread and changes the number of thread. The average is calculated by 3 runs of the thread class.
• Observation: The performance didn’t improve above 25 threads. Thus, the optimal number of threads is 25 threads.

3. The result of step 3:
   Observation: Surprisingly, the performance of multi-thread simulation is equal good compare to the performance of linear simulation base on the time it takes to run a game. So, we could examine other criteria.
   We decide to choose threads simulation because it performs slightly better.