Skip to content

Instantly share code, notes, and snippets.

@z5h
Created December 6, 2023 06:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save z5h/f43f2bd6987e99e242aecfb08683bc23 to your computer and use it in GitHub Desktop.
Save z5h/f43f2bd6987e99e242aecfb08683bc23 to your computer and use it in GitHub Desktop.
"Monte-Carlo amb" in Prolog, proof of concept
amb_example(BestGuess) :-
run_with_monte_carlo_amb(1000,
( amb(BestGuess, [2,3,4,5,6,7,8,9,10,11,12]),
guess_the_dice_total(BestGuess)
)).
guess_the_dice_total(Total) :-
random_member(Dice1, [1,2,3,4,5,6]),
random_member(Dice2, [1,2,3,4,5,6]),
(Total =\= Dice1 + Dice2 -> amb(fail); true).
make_pair(A, B, A-B).
zip(L1, L2, L3) :-
maplist(make_pair, L1, L2, L3).
run_with_monte_carlo_amb(Count, Goal) :-
Count > 0,
reset(Goal, Term, Cont),
(Cont == 0 ->
true
;
Term = amb(Choice, List) ->
maplist(run_n_trials(Count, Cont, Choice), List, Results),
zip(Results, List, ResultsAndList),
sort(ResultsAndList, Sorted),
last(Sorted, _-Choice),
run_with_monte_carlo_amb(Count, Cont)
;
% fail is for feedback. If we encounter it here, it means that the oracle has failed to find a good/lucky choice, but this is not necessarily "failure" in a logical sense. So we will continue with the computation.
Term = amb(fail) ->
run_with_monte_carlo_amb(Count, Cont)
).
amb(Choice, List) :-
var(Choice)
->
shift(amb(Choice, List))
;
member(Choice, List).
run_n_trials(0, _, _, _, 0).
run_n_trials(N, Goal, Choice, Item, TotalWins) :-
N > 0,
N1 is N - 1,
run_n_trials(N1, Goal, Choice, Item, Wins),
(\+ \+ (Choice = Item, run_with_amb_fail(Goal))
->
TotalWins is Wins + 1
;
TotalWins is Wins
).
run_with_amb_fail(Goal) :-
reset(Goal, Term, Cont),
(Cont == 0 ->
true
;
Term = amb(Choice, List) ->
random_member(Choice, List),
run_with_amb_fail(Cont)
;
Term = amb(fail) ->
fail
).
amb(fail) :-
shift(amb(fail)).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment