Il "sì" e "no" a questo punto non serve a niente, la risposta aleatoria annulla tutto e rende inutile il significato della risposta.

A questo punto credo che il trucco stia nel fare una domanda dove può o non può rispondere (senza dare importanza al fatto che dica sì o no), ad esempio potremmo premettere un periodo ipotetico alla domanda in modo tale che se la premessa è vera può rispondere alla domanda, se è falsa non può rispondere.

La premessa sarà utile alla soluzione se è legata al valore delle carte che appunto lei conosce e io no, quindi chiederei "Se questa carta è la Luna nera, è vero che...?". Al posto dei puntini chiediamo qualsiasi domanda banale. In questo modo, se quella carta è la Luna nera la zingara risponderà in maniera aleatoria, se invece non lo è la zingara non potrà rispondere perché qualsiasi risposta sarebbe una menzogna dal momento che quella carta non è Luna nera. Quindi dalla risposta capiamo se la carta che abbiamo indicato è o non è la Luna nera, se lo è ne scegliamo una delle due rimanenti avendo la certezza di trovare una Luna rossa, se non lo è allora scegliamo proprio quella sapendo che sarà per forza una Luna rossa.

Un esempio di domanda è:
"Se questa carta è la Luna nera, è vero che le altre due sono uguali?"