what is the best algorithm for this game?

Question

I want to make a bot for this game:

The game is played with 8 cards, numbered 1 to 8. At the start of the game , these cards are all on the table (desk), faced up. Quoted from the instructions:

The goal of the game is that you reach the sum of 15 with 3 cards in your hand. The first person to reach this goal in a maximum of 30 turns is the winner.

Each time at your turn, you are supposed to take one card from the desk.
When you have 3 cards in your hand, you should swap one of your cards in your hand with a card on the desk.

All cards are visible to both players at all times.

What is the best algorithm to win the game?

Answer 1

I would suggest creating a minimax algorithm, which is (like @PaulHankin's answer) creating a game tree. The difference is that the states are discovered as moves are played.

This question grabbed my interest, and so I had some fun in creating an interactive snippet in JavaScript. It shows you which moves are available, and whether they lead to a win, a loss or a draw. In the case of a win or loss, it tells you how many half-moves (plies) you are away from that fate (with optimal play).

Enjoy:

class Node {
    constructor(id) {
        this.id = id;
        this.neighbors = []; // List of Node instances that can be reached with one move
    }
    cardOwner(card) {
        return (this.id >> (2*card-2)) & 3; // Decode binary representation
    }
    * generateMoves() { // Yield the moves that player 1 can make
        let hands = [[], [], []];
        // Translate id to sets of cards
        for (let card = 1; card <= 8; card++) hands[this.cardOwner(card)].push(card);
        let [desk, myHand, otherHand] = hands;
        if (otherHand.length < 3 || otherHand.reduce((a, b) => a + b, 0) !== 15) {
            if (myHand.length < 3) {
                for (let card of desk) yield this.getTargetId(card);
            } else {
                for (let discard of myHand) {
                    for (let replace of desk) yield this.getTargetId(discard, replace);
                }
            }
        }
    }
    getTargetId(...cards) {
        let id = this.id;
        for (let card of cards) id ^= 1 << (card*2-2);
        // Toggle owner, as in each state we consider player 1 as the player to move
        for (let mask = 3; mask < 0x10000; mask <<= 2) {
            if (id & mask) id ^= mask;
        }
        return id;
    }
    compare(next) {
        let id = this.id;
        let nextId = next.id;
        let diff = { replace: 0, discard: 0 };
        for (let card = 1; card <= 8; card++) {
            if ((id & 3) && !(nextId & 3)) diff.discard = card;
            else if (!(id & 3) && (nextId & 3)) diff.replace = card;
            id >>= 2;
            nextId >>= 2;
        }
        return diff;
    }
}

class Game {
    constructor() {
        this.hist = []; // Previous states (after moves have been made)
        this.node = new Node(0); // 0 is the initial state where all 8 cards are on desk
        this.visited = new Map; // Evaluated states; Node instances keyed by their identifier
    }
    move(target) {
        this.hist.push(this.node);
        this.node = target;
    }
    undo() {
        this.node = this.hist.pop();
    }
    minimax() {
        if (this.node.value !== undefined) return; // Already visited
        // Generate neighbors for this Node
        this.node.neighbors = Array.from(this.node.generateMoves(), targetId => {
            let target = this.visited.get(targetId); // Get a Node instance
            if (!target) this.visited.set(targetId, target = new Node(targetId));
            return target;
        });
        if (!this.node.neighbors.length) { // Game over!
            this.node.value = 100;
            return;
        }
        // Assign temporary value while depth-first search is ongoing.
        // This will ensure that a revisit is considered a draw (repetition of moves)
        this.node.value = 0; // 0 indicates a draw
        let bestValue = -Infinity;
        for (let target of this.node.neighbors) {
            this.move(target);
            this.minimax();
            bestValue = Math.max(bestValue, this.node.value);
            this.undo();
        }
        // Definite value: reduce its absolute value, so to favour quick wins over slow wins
        this.node.value = bestValue && (Math.abs(bestValue) - 1) * Math.sign(-bestValue);
    }
}

let game = new Game;
game.minimax();  // Create the full game tree rooted at the initial state

// I/O management

let state = document.getElementById("state");
let moves = document.getElementById("moves");
let undo = document.getElementById("undo");
let message = document.getElementById("message");

function display() {
    let turn = game.hist.length % 2;
    let mapper = [1, turn*2, 2 - turn*2];
    for (let card = 1; card <= 8; card++) {
        let owner = game.node.cardOwner(card);
        let ownerRow = state.rows[mapper[owner]];
        for (let row of state.rows) {
            row.cells[card].textContent = row === ownerRow ? card : "";
        }
    }
    state.rows[0].classList.toggle("turn", !turn);
    state.rows[2].classList.toggle("turn", turn);
    message.textContent = game.node.neighbors.length ? `Player ${turn + 1} to play. Make your choice:` : `Player ${2 - turn} won!`;
    undo.disabled = !game.hist.length;
    moves.innerHTML = "";
    for (let target of game.node.neighbors) {
        let { discard, replace } = game.node.compare(target);
        let button = document.createElement("button");
        button.textContent = `${discard ? `Replace ${discard} with` : "Select"} ${replace} ${
            target.value < 0 ? `(lose in ${101+target.value})` : 
            target.value > 0 ? `(win in ${101-target.value})` : "(draw)"
        }`;
        moves.appendChild(button);
    }
}

moves.addEventListener("click", function (e) {
    let moveIndex = [...moves.children].indexOf(e.target);
    if (moveIndex >= 0) game.move(game.node.neighbors[moveIndex]);
    display();
});

undo.addEventListener("click", function() {
    game.undo();
    display();
});

display();

td { border: 1px solid; background: yellow; min-width: 1em; text-align: center }
td:empty, td:first-child { border-color: transparent; background: none }
tr:nth-child(odd) { background: lightblue } 
tr.turn { background: orange }
#moves > * { display: block }

<table id="state">
    <tr>
        <td>Player 1: </td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td>
    </tr>
    <tr>
        <td>Desk: </td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td>
    </tr>
    <tr>
        <td>Player 2: </td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td>
    </tr>
</table>

<div id="message"></div>
<button id="undo">Undo last move</button><br>
<div id="moves"></div>

Remarks

The game is a draw when both players play optimally. The first player has a bit of an advantage if we consider that the second player has to be more careful in the first phase of the game not to make a mistake.

When the first player picks either card 6 or 8, the second player must take card 5 or they will lose (with optimal play). The game tree widens quickly, but there are other states where there is only one good move.

The number of distinct states that are discovered, including the root state, is 1713. The algorithm does not take the 30-move limit into account, as it is a "boring" rule. The nice thing of not having this limit is that the algorithm needs to be smart enough to detect repetitions. With the 30-move limit, such cycle check does not need to be implemented.

Python

The same implementation (interacting on console) can be found on repl.it