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

#1 asuna  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • Posts: 1,688
  • Joined: 13-March 10

Re: modifying expectimax algorithm

Posted 09 September 2012 - 01:37 AM

Shows us the code.
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10464
  • View blog
  • Posts: 38,783
  • 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!
Was This Post Helpful? 0
  • +
  • -

#4 asuna  Icon User is offline

  • New D.I.C Head

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

Re: modifying expectimax algorithm

Posted 11 September 2012 - 03:22 AM

View Postdarek9576, 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


View Postmacosxnerd101, 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..
Was This Post Helpful? 0
  • +
  • -

#5 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,049
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1