# modifying expectimax algorithm

Page 1 of 1

## 4 Replies - 3506 Views - Last Post: 20 September 2012 - 02:51 PM

### #1 asuna

Reputation: 0
• Posts: 2
• Joined: 09-September 12

# modifying expectimax algorithm

Posted 09 September 2012 - 01:34 AM

Hi guys, I'm trying to modify the basic expectimax and star1 algorithm by making the search process parallel. I'm just not sure what part should I start doing the parallel process. I'm going to use multi-threading. Thanks
Is This A Good Question/Topic? 0

## Replies To: modifying expectimax algorithm

### #2 darek9576

• D.I.C Lover

Reputation: 203
• Posts: 1,717
• Joined: 13-March 10

## Re: modifying expectimax algorithm

Posted 09 September 2012 - 01:37 AM

Shows us the code.

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11787
• Posts: 44,294
• Joined: 27-December 08

## Re: modifying expectimax algorithm

Posted 09 September 2012 - 09:04 PM

A lot of paralellization comes down to either finding the same task that is being done multiple times or finding multiple tasks that generally don't conflict with or depend on each other.

I'm not personally familiar with either of those algorithms. If you could post more about your goal here and your work thusfar, I'm sure we could get you going in a better direction though!

### #4 asuna

Reputation: 0
• Posts: 2
• Joined: 09-September 12

## Re: modifying expectimax algorithm

Posted 11 September 2012 - 03:22 AM

darek9576, on 09 September 2012 - 01:37 AM, said:

Shows us the code.

The algorithm is actually a general one for AI's in games involving chances (i.e. dice roles). It creates a game tree to evaluate the possible moves and choose the best from it. I have the game with the AI i'm trying to make parallel but i'm not sure If I can post it since it will be quite big. The pseudo code can be seen here: http://jveness.info/...ions/thesis.pdf

macosxnerd101, on 09 September 2012 - 09:04 PM, said:

A lot of paralellization comes down to either finding the same task that is being done multiple times or finding multiple tasks that generally don't conflict with or depend on each other.

I'm not personally familiar with either of those algorithms. If you could post more about your goal here and your work thusfar, I'm sure we could get you going in a better direction though!

I'm trying to speed up the existing algorithm. The algorithm involves a task that is really done several times (it involves recursion). I'm not sure if i can post the code here because it will be very huge since it's a game but if you really want to see it, I can put the whole project here (it's in java). There's a pseudocode though, it's in here http://jveness.info/...ions/thesis.pdf

Minimax- Game tree
Minimax with Alpha-beta pruning- Cutting off search nodes in the Minimax tree
Expectimax- Game tree with chance nodes
Star1- Expectimax with alpha-beta pruning

Hmm..

### #5 cfoley

• Cabbage

Reputation: 2338
• Posts: 4,889
• Joined: 11-December 07

## Re: modifying expectimax algorithm

Posted 20 September 2012 - 02:51 PM

If you are searching through a game tree then that's a potential for threading right there. Limit the number of threads to something sensible like 2, 4 or 10000 if you are on a supercomputer. Each thread gets its own subtree to search.