Here is my solution: 1) For 1 or 2 piles, it is easy to figure out the solution. 2) Win only if the opponent can not figure out how to win for all possible moves. 3) A depth-first seach for each combinition. 4) Minor optimizations.

import static org.junit.Assert.assertEquals;

import java.util.LinkedList; import java.util.List;

import org.junit.Test;

public class MisereNim {

private static boolean firstMove = true;
private static Boolean res = null;

public static String misereNim(List<Integer> s) {
    firstMove = true;
    LinkedList<Integer> sList = new LinkedList<>(s);
    for (int i = 0; i < s.size(); ++i) {
        if (sList.get(i) <= 0) {
            sList.remove(i);
        }
    }
    sList.sort((Integer i, Integer j)-> (i < j)? +1 : ((i == j)? 0 : -1));
    move(sList, true);
    if (!res)
        firstMove = !firstMove;
    return firstMove? "First" : "Second";       
}

private static void win(final LinkedList<Integer> sList) {
    /*
    For one or two piles, find the optimal solution
     */
    switch (sList.size()) {
        case 1:
            res = sList.get(0) > 1;
            break;
        case 2:
            if ((sList.get(0) == 1) || (sList.get(1) == 1))
                res = true;
            else if (sList.get(0) == 2) 
                res = sList.get(1) != 2;
            else if (sList.get(1) == 2) 
                res = sList.get(0) != 2;
            else
                res = ((sList.get(0) - 2 + sList.get(1) - 2) % 2) == 1;
            break;
        default:
            res = null;
            break;
    }
}

private static void move(final LinkedList<Integer> sList, boolean first) {
    /*
    win only if the opponent can not figure out how to win for all possible moves.
    depth-first search, for optimal move.

    The constraint of 1 <= s[i] <= 10^9 means that the approach has to be optimized: to reduce either as 1, 2 or as 3.
    If there is even number of piles each with 1 stone, the first will win.
    If there is one pile with more than 1 stone, the first will win.

    timed out
    */
    firstMove = first;
    win(sList);
    if (res != null)
        return;
    int prev = 0;
    for (int i = 0; i < sList.size(); ++i) {
        if (prev == sList.get(i))
            continue;
        prev = sList.get(i);
        LinkedList<Integer> sSub = new LinkedList<>(sList);
        sSub.remove(i);
        firstMove = !first;
        win(sSub);
        if ((res != null) && (res == false))
            return;
        if (res == null) {
            move(sSub, !first);
        }
        if ((res == false) && (first != firstMove)) {
            return;
        } 
        for (int j = 1; (j < sList.get(i)) && (j <= 3); j++) {
            sSub = new LinkedList<>(sList);
            sSub.set(i, j);
            firstMove = !first;
            win(sSub);
            if (res == null) {
                move(sSub, !first);
            }
            if ((res == false) && (first != firstMove)) {
                return;
            } 
        }
    }
    firstMove = first;
    res = false;
    return;

}

@Test
public void testOne_direct() {
    assertEquals("Second", misereNim(List.of(1)));
    assertEquals("First",  misereNim(List.of(1,1)));      // ->[1]
}

@Test
public void testOne() {
    assertEquals("Second", misereNim(List.of(1,1,1))); // ->[1,1]
}

@Test
public void testTwo_direct() {
    assertEquals("First",  misereNim(List.of(2)));             // ->[1]
    assertEquals("First",  misereNim(List.of(1,2)));        // ->[1]
    assertEquals("Second", misereNim(List.of(2,2)));        // ->[1,2], [2]
}

@Test
public void testTwo() {
    assertEquals("First",  misereNim(List.of(1,1,2)));   // ->[1,1,1]
    assertEquals("First",  misereNim(List.of(1,2,2)));   // ->[2,2]
    assertEquals("First",  misereNim(List.of(2,2,2)));   // ->[2,2]
}

@Test
public void testThree_direct() {
    assertEquals("First",  misereNim(List.of(3)));             // ->[1]
    assertEquals("First",  misereNim(List.of(1,3)));        // ->[1]
    assertEquals("First",  misereNim(List.of(2,3)));        // ->[2,2]       
    assertEquals("Second", misereNim(List.of(3,3)));        // ->[2,3], [1,3], [3]
}

@Test
public void testThree() {
    assertEquals("First",  misereNim(List.of(1,1,3)));   // ->[1,1,1]
    assertEquals("Second", misereNim(List.of(1,2,3)));   // ->[2,3], [1,1,3],[1,3],[1,2],[1,2,1],[1,2,2]
    assertEquals("First", misereNim(List.of(1,3,3)));   // ->[3,3]
    assertEquals("First", misereNim(List.of(2,2,3)));   // ->[1,2,3]
    assertEquals("First", misereNim(List.of(2,3,3)));   // ->[3,3]
    assertEquals("First", misereNim(List.of(3,3,3)));   // ->[3,3]
}

@Test
public void testSample() {
    assertEquals("First",  misereNim(List.of(9,8,4,4,7)));
}

}