[Beowulf] What can a HS student do with a small Beowulf?

[sNAAPS eLYK]

Forgive my newness, but does Java/Perl have the instructions for assigning
queues and certain work to seperate processors?
That's what I should have asked in the first place...
Thanks!

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