Forgive my newness, but does Java/Perl have the instructions for assigning queues and certain work to seperate processors?<br>
That's what I should have asked in the first place...<br>
Thanks!<br><br><div><span class="gmail_quote">On 5/23/06, <b class="gmail_sendername">Jim Lux</b> <<a href="mailto:James.P.Lux@jpl.nasa.gov">James.P.Lux@jpl.nasa.gov</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
At 07:00 PM 5/23/2006, sNAAPS eLYK wrote:<br>> >Many game playing algorithms lend themselves to parallelism to explore<br>> >the move tree (Chess is iconic, as is Checkers)<br>>I actually did some of that with Java last year: Knight's Tour and Towers
<br>>of Hanoi etc...<br>>Is it possible that someone with only limited coding experience as myself<br>>could learn to/effectively write code to utilize the paralellism of the<br>>beowulf cluster to compute challenges such as those? That is to say, learn
<br>>how to do it with perhaps just Java or Perl ?<br><br>Why not? The state space search algorithm is pretty simple. Think about<br>this.<br>At any given point, you have some N possible moves. Then you go forward<br>
and investigate the M(i), i=1,N possible moves after that, etc. So, you<br>assign each of the N moves to a separate processor. (or, if you have lots<br>of processors, you assign sum(M(i),i=1,N) processors, one to each of the
<br>second tiers.<br><br>Most search algorithms have a "search termination" criteria that stops<br>searching down unproductive paths (look up alpha-beta pruning). Most also<br>have a process that takes a given game state (board configuration in chess
<br>or checkers) and generates all possible states that can be created from<br>that (i.e. what moves are possible). Then each of those states is<br>evaluated against some "evaluation function" to decide which ones are worth
<br>pursing.<br><br>So, you could set up a queue of "next move to check", and when you go to a<br>particular game state, and you generate the next set of moves, you fling<br>them all onto the queue. The next free processor picks up the next move in
<br>the queue, etc.<br><br>You could do this as a "one master/many slaves" kind of thing, where only<br>one processor generates the new states, and all the worker bees do the<br>evaluation. or, you can let any processor do the move generation. Either
<br>way, it's an interesting exercise in queuing and process dispatching, not<br>to mention feeding back the data to the ultimate starting point to decide<br>"which is my next move".<br><br>Another interesting puzzle to solve (which has a very broad game tree, but
<br>simple rules, so the coding is not too complex) is the "8 puzzle" or "15<br>puzzle" where you have a 3x3 or 4x4 grid with tiles that slide, numbered<br>from 1:n-1. You can use a variety of evaluation functions (and look at how
<br>well the program works to find the solution) such as "sum of how many tile<br>spaces away from the final configuration each tile is" or "how many<br>vertical and horizontal moves are needed", etc.<br>
<br>I wouldn't do chess, because the move generation process is so<br>diverse. Pick something where the game is simple, and you can spend your<br>time solving the distributed computing problems.<br><br>Another one is to load in a city bus/train schedule, and have it determine
<br>optimal routes between points. A more challenging one is the "travelling<br>salesman" problem (minimizing the length of total trip to traverse all<br>nodes of a graph).<br><br><br>James Lux, P.E.<br>Spacecraft Radio Frequency Subsystems Group
<br>Flight Communications Systems Section<br>Jet Propulsion Laboratory, Mail Stop 161-213<br>4800 Oak Grove Drive<br>Pasadena CA 91109<br>tel: (818)354-2075<br>fax: (818)393-6875<br><br><br></blockquote></div><br>