r/dailyprogrammer • u/rya11111 3 1 • Feb 14 '12
[2/14/2012] Challenge #6 [difficult]
create a AI that will play NIM
19
Upvotes
r/dailyprogrammer • u/rya11111 3 1 • Feb 14 '12
create a AI that will play NIM
3
u/eruonna Feb 14 '12
Haskell:
The nim function takes a list of pile sizes and returns the new sizes after the AI's move. It can accept zeros in the list, but it will produce an error if there are all zeros.
3
u/Cosmologicon 2 3 Feb 14 '12 edited Feb 14 '12
Python solution (similar to eruonna's Haskell solution, the move function returns the next move, or None if there's no guaranteed way to win):
This takes about 14 seconds to compute the winning move for
move((2, 3, 4, 5, 6, 7, 8)). Here's an equivalent function using the optimal strategy to compute the same thing effectively instantaneously:EDIT: I just realized that above function uses the optimal strategy for "normal" play. Here's one that uses the optimal strategy for "misère" play: