Recursive nested loop c#

Question

I am trying to improve myself on probabilities with a task but couldn't figure it out: On a backgammon game, I have four (dynamic) rows of placements.

So lets say row 5,7,11,13. I am throwing dynamic number of dice. I am trying to find the probabilities of each gameplay. As an example:

I have thrown 4 dice and result is 1,3,4,6

So

I can play from the 5. row-1,3,4,6 dice

I can play from the 5. row-1,3,4 dice and from the 7. row-6 dice

I can play from the 5. row-3,1 dice and from the 11. row-6 dice and from the 13. row-4 dice etc etc.

The dice have to be dynamic, the rows have to be dynamic, the dice can be played mixed like 1,3,4,6 or 6,1,4,3 or 3,1,6,4. And it has to calculate all the possibilities of different variations of dice spread on the rows.

Simply I am trying to calculate the possibilities of play on a backgammon with unlimited dice. The method I am trying to use it to have a resizable possible moves class and inside of this class, there are the resizable rows class. Inside the rows class, there is resizable List moves variable. I am adding one move for each variation. This is the codes for non dynamic 4 dice.

public   List<int> dice;
public   List<int> places;

[System.Serializable]
public class arrayData
{
    public List<arrayData2> places = new List<arrayData2>();
    }

    public List<arrayData> pos = new List<arrayData>();

    [System.Serializable]
    public class arrayData2
    {
        public List<int> moves = new List<int> {};
    }

    void Start()
    {
        vs();
    }

    void vs()
    {
        for (int i = 0; i < places.Count; i++)
        {
            for (int a = 0; a < dice.Count; a++)
            {
                for (int b = 0; b < dice.Count; b++)
                {
                    for (int c = 0; c < dice.Count; c++)
                    {
                        for (int d = 0; d < dice.Count; d++)
                        {
                            if (a == b || a == c || a == d || b == c || b == d || c == d)
                            {
                                continue;
                            }

                            pos.Add(new arrayData());

                            for (int s = 0; s < places.Count; s++)
                            {
                                pos[pos.Count - 1].places.Add(new arrayData2());
                            }

                            pos[pos.Count - 1].places[i].moves.Add(dice[a]);
                            pos[pos.Count - 1].places[i].moves.Add(dice[b]);
                            pos[pos.Count - 1].places[i].moves.Add(dice[c]);
                            pos[pos.Count - 1].places[i].moves.Add(dice[d]);
                        }
                    }
                }
            }
        }
    }

What I couldn't figure out:

-Firstly, I tried to make it a recursive loop but I couldn't figure out the structure

-Second, the output is giving me missing values for the variation of spread between rows: It gives such values: 5. row-1,3,4,6 dices but not such values: 5. row-3,1 dices and from the 11. row-6 dice and from the 13. row-4 dice

I know it is a big question to ask but any kind of pointing out the mistake or correct direction leading would be so appreciated.

Thanks

By the way the singular and plural for dice is .... dice... no such word as dices — BLoB
– BLoB, Commented Jul 23, 2014 at 10:41
@PaulZahra Singular for dice is die, if you want to be picky. — Mwigs
– Mwigs, Commented Jul 23, 2014 at 10:48
@MarcusWigert Afraid not old chap... many moons ago it used to be, but now in modern English it is Dice... oxforddictionaries.com/definition/english/dice — BLoB
– BLoB, Commented Jul 23, 2014 at 10:51

Corbin March · Accepted Answer · 2014-12-11 20:06:03Z

It might be useful to think about your moves as part of a game tree. The basic idea is that all games start in a particular state. We'll call it x. A move then changes the state of the game to x1, the next move to x2, and so on. Most moves involve a choice and, depending on the choice made, each move pushes the game into a different state. From the starting state, all possible moves form a gigantic tree. This is handy because we can use tree traversal algorithms to explore our tree. That's where the recursion comes in.

Backgammon is conceptually a little trickier than a game like chess or checkers because you have to account for the randomness of the dice as well as the behavior of your opponent. That adds even more choices during a move. In pseudo-code, I might tackle the problem like this:

function get_next_move (current_state):
    dice = roll_dice()
    possible_states = an empty collection
    get_possible_states (dice, current_state, possible_states)
    return decide_best_state (possible_states)

function get_possible_states (dice, state, possible_states):

    // If we've exhausted all dice, we're done.
    // Add the state we've reached to our possible outcomes.
    if dice are empty:
        add state to possible_states
        return            

    for each die in dice:
        dice_without_die = remove die from dice
        for each next_state in get_legal_states (state, die):
            // Here's the recursion. Go a level deeper in our tree.
            get_possible_states (dice_without_die , next_state, possible_states)


function get_legal_states (state, die):
    // Here's where you determine legal moves based on the
    // die rolled and the current state of the game.

Put another way, to determine my next move I have to:

Roll the dice.
With each die rolled, generate all of its legal moves (states).
Repeat the process using a new state and without the die already used.
When there are no dice left, add the final state to the list of possible states.
Finally, determine which move is best. Keep in mind that some generated states may be duplicates. There's more than one way to move your pieces to the same locations.

The nice thing about this approach is there are no hard-coded numbers. It can handle any number of legal moves or dice. (Though I'm not sure when Backgammon would use a variable number of dice.) One detail I left out is that you need to know who's turn it is. The legal moves will depend on who's making them.

Collectives™ on Stack Overflow

Recursive nested loop c#

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related