1
\$\begingroup\$

My task is to select items from a pool to match a specific selection criteria in a browser game.

My Problem: Usually my algorithm can find the desired results after 200–400 iterations. But every once in a while it does not find a result even after 1 000 000 iterations.

I would be very happy to receive optimizations or hints how to solve the problem in a better way.

Conditions: In my pool I have an array of 600 JavaScript objects. All the items have the same structure:

{
  id: 0, // int(0-599)
  name: "name0", //string(name+id)
  position: 'front', // either front, back, left, right
  belongsTo: "class0", // string(class0-19)
  isStar: false, // bool
  isEnemy: false, // bool
  binaryAttribute: 'dangerous' // string('dangerous', 'harmless')
}

Important notice for the attribute isEnemy: the user can input 5 enemies. This attribute checks, if the item is an enemy or not.

Normally the pool comes from a database, but for this example I will just create it by a simple method (createSampleDatabase()).

I need to select 18 items so that they match the following criteria regarding their attributes:

2× position = "back"
4× position = "left"
7× position = "right"
5× position = "front"

3× isStar
3× isEnemy // comes from user input!
3× belongsTo = 'classX' // userSelection
9× !isStar && !isSun && !belongsTo === 'classX'

The criteria can be mixed, but in the end the sample that gets drawn has to match exactly these criteria.

Therefore I created the following algorithm:

var items = createSampleDatabase();
var shouldBelongTo = 'class4';
var enemies = ['name100','name200','name300','name400','name500'];
var selectedItems = selectionAlgorithm(items, shouldBelongTo, enemies);
console.log(selectedItems);

function createSampleDatabase(){
    var items = [];
    positions = ['back', 'left', 'right', 'front'];
    var itemCount = 1;
    var belongsToCount = 1;
    for (var i = 0; i < 600; i++) {
        if(itemCount === 20) {
            belongsToCount++;
            itemCount = 1;
        }
        itemCount++;

        items.push({
            id: i,
            name: 'name' + i,
            belongsTo: 'class' + belongsToCount,
            position: positions[Math.floor(Math.random()*positions.length)],
            isStar: Math.random() < 0.1 ? true : false,
            binaryAttribute: Math.random() < 0.5 ? 'dangerous' : 'harmless',
        })
    }

    return items;
};

function selectionAlgorithm(items, belongsTo, enemies) {
        var selectedItems = [];

        var quotas = {
            byPosition: {
                back: {
                    max: 2,
                    current: 0
                },
                left: {
                    max: 4,
                    current: 0
                },
                right: {
                    max: 7,
                    current: 0
                },
                front: {
                    max: 5,
                    current: 0
                }
            },
            byAttribute: {
                isEnemy: {
                    max: 3,
                    current: 0,
                    check: function (item) {
                        return enemies.indexOf(item.name) > -1;
                    }
                },
                isStar: {
                    max: 3,
                    current: 0,
                    check: function (item) {
                        return item.isStar;
                    }
                },
                belongsTo: {
                    max: 3,
                    current: 0,
                    check: function (player) {
                        return player.belongsTo === belongsTo;
                    }
                },
                other: {
                    max: 9,
                    current: 0,
                    check: function (item) {
                        return !item.isStar && item.belongsTo !== belongsTo && enemies.indexOf(item.name) === -1;
                    }
                }
            }
        };

        var filteredItems = {
            byPosition: _.groupBy(items, function (item) {
                return item.position
            })
        };
        var maxIterations = 1000000;
        var iterations = 0;
        while (true) {
            iterations++;
            for (positionKey in quotas.byPosition) {
                if (quotas.byPosition[positionKey].max > quotas.byPosition[positionKey].current) {
                    var item =
                        filteredItems.byPosition[positionKey][Math.floor(Math.random() *
                            filteredItems.byPosition[positionKey].length)];

                    for (attributeKey in quotas.byAttribute) {
                        if ((quotas.byAttribute[attributeKey].max > quotas.byAttribute[attributeKey].current) &&
                            quotas.byAttribute[attributeKey].check(item)) {
                            
                            selectedItems.push(item);
                            quotas.byAttribute[attributeKey].current++;
                            quotas.byPosition[positionKey].current++;
                            break;
                        }
                    }
                    break;
                }
            }

            if (selectedItems.length === 18) {
                console.log('quotas fulfilled after ', iterations);
                break;
            }

            if(iterations === maxIterations){
                console.warn('maximum iterations reached')
                break;
            }

        }

        return selectedItems;
    }
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.16.4/lodash.min.js"></script>

\$\endgroup\$
2
\$\begingroup\$

I can see three problems with this code.

  1. There might not be any selection of items in the database satisfying all the criteria. The failed search might just be telling you that there is no solution.

  2. The search is not systematic. On each iteration it picks a random item from the database satisfying an unmet position criterion, and considers adding it to the selection. But this does not guarantee that all items are considered for addition to the selection — an unlucky sequence of random numbers might miss some of the items.

    It would be better to ensure that each item is considered, for example by shuffling the items meeting each position criterion and then considering them one at a time in the shuffled order. That way the search will consider all items regardless of the sequence of random numbers.

  3. The search does not backtrack. It only adds items to the selection and never removes them. This means that if it enters a blind alley in the search, it has to start again from the beginning, thus wasting the effort involved in the early part of the search.

    It would be better to backtrack when a blind alley is discovered.

The problem you're trying to solve is a type of constraint satisfaction problem known as EXACT MULTICOVER (a variant of the EXACT COVER problem where the constraints are a multiset). I wrote a series of articles about solving this problem using backtracking search in Python (part I, part II, part III), which you might find helpful.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for your articles, they are very interesting and well written. (1) true. (2) I thought I would be searching systematically because of the pre-grouping. My intend was to limit the pool of options to only those which are applicable for the current quota so that the number of useless picks would decrease. (3) true. I am struggling a bit on how I would calculate, if there are possible solutions left - or if i have to backtrack. Do you have a good approach for my specific problem? \$\endgroup\$ – ManuKaracho Oct 20 '16 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.