[SOLVED] what is the best algorithm for this game?

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):

class Node:
    def __init__(self, id):
        self.id = id;
        self.neighbors = []; # List of Node instances that can be reached with one move
        self.value = None
    
    def cardOwner(self, card):
        return (self.id >> (2*card-2)) & 3 # Decode binary representation
    
    def generateMoves(self): # Yield the moves that player 1 can make
        hands = [[], [], []]
        # Translate id to sets of cards
        for card in range(1, 9):
            hands[self.cardOwner(card)].append(card)
        desk, myHand, otherHand = hands
        if len(otherHand) < 3 or sum(otherHand) != 15:
            if len(myHand) < 3:
                for card in desk:
                    yield self.getTargetId(card)
            else:
                for discard in myHand:
                    for replace in desk: 
                        yield self.getTargetId(discard, replace)

    def getTargetId(self, *cards):
        id = self.id
        for card in cards:
            id ^= 1 << (card*2-2)
        # Toggle owner, as in each state we consider player 1 as the player to move
        mask = 3
        while mask < 0x10000:
            if id & mask:
                id ^= mask
            mask <<= 2
        return id

    def compare(self, next):
        id = self.id
        nextId = next.id
        replace = 0
        discard = 0
        for card in range(1, 9):
            if (id & 3) and not (nextId & 3):
                discard = card
            elif not (id & 3) and (nextId & 3):         
                replace = card
            id >>= 2;
            nextId >>= 2;
        return discard, replace
    

class Game:
    def __init__(self):
        self.hist = []  # Previous states (after moves have been made)
        self.node = Node(0)  # 0 is the initial state where all 8 cards are on desk
        self.visited = {}  # Evaluated states; Node instances keyed by their identifier
    
    def reset(self):
        if self.hist:
            self.node = self.hist[0]
            self.hist = []

    def move(self, target):
        self.hist.append(self.node)
        self.node = target
    
    def undo(self):
        self.node = self.hist.pop()
    
    def minimax(self):
        if self.node.value is not None: 
            return  # Already visited
        # Generate neighbors for this Node
        self.node.neighbors = [
            self.visited.setdefault(targetId, Node(targetId)) 
            for targetId in self.node.generateMoves()
        ]
        if not self.node.neighbors:  # Game over!
            self.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)
        self.node.value = 0  # 0 indicates a draw
        bestValue = -200
        for target in self.node.neighbors:
            self.move(target)
            self.minimax()
            bestValue = max(bestValue, self.node.value)
            self.undo()
        
        # Definite value: reduce its absolute value, so to favour quick wins over slow wins
        self.node.value = -(bestValue and bestValue + (-1 if bestValue > 0 else 1))

game = Game()
game.minimax()  # Create the full game tree rooted at the initial state

# I/O management

from functools import partial

def display():
    turn = len(game.hist) % 2
    owners = [(card, game.node.cardOwner(card)) for card in range(1, 9)]
    hands = [(1+turn, "Player 1"), (0, "    Desk"), (2-turn, "Player 2")]
    for hand, name in hands:
        print(name, end=": ")
        for card, owner in owners:
            print(card if owner == hand else ".", end=" ")
        print()
    print()

    if game.node.neighbors:
         print(f"Player {turn + 1} to play. Make your choice:")
    else:
        print(f"Player {2 - turn} won!")

    options = {
        "9": game.reset,
        "Q": lambda: None
    }
    if game.hist:
        print("0. Undo")
        options["0"] = game.undo

    for target in game.node.neighbors:
        discard, replace = game.node.compare(target)
        code = str(discard*10+replace)
        options[code] = partial(game.move, target)
        if discard:
            print(f"{code}. Replace {discard} with {replace}", end=" ")
        else:
            print(f"{code}. Select {replace}", end=" ")
        if target.value < 0:
            print(f"(lose in {101+target.value})")
        elif target.value > 0:
            print(f"(win in {101-target.value})")
        else:
            print("(draw)")
    print("9. New game")
    print("Q. Quit")

    choice = input("Your choice: ").upper()
    while choice not in options:
        print("Not a valid choice.")
        choice = input("Your choice: ").upper()
    options[choice]()
    return choice != "Q"

import os
while display():
    os.system('cls' if os.name == 'nt' else 'clear')