////////// Exercice 1 ////////// // Initial state for a game of tic-tac-toe let initialState = [ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ]; // Other possibility to initialize the array // let initialState = Array.from({length: 9}, () => ' '); console.log(`An initial state :\n${stateToString(initialState)}`); let aState = [ 'x', ' ', 'o', 'x', 'o', ' ', 'x', ' ', ' ' ]; console.log(`A state :\n${stateToString(aState)}`); // Given a state `aState` of the tic-tac-toe game, list all the empty // slots and returns the array of their indices. function stateEmptySlots(aState) { const allIndices = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]; // Other possibility to initialize the indices // const allIndices = Array.from({length: 9}, (_, id) => id); return allIndices.filter((id) => aState[id] === ' '); } // Given a state `aState` and a player `aPlayer`, returns the list of // all possible moves for this player from this state. function stateNexts(aState, aPlayer) { return stateEmptySlots(aState).map((id) => { let aStateCopy = [...aState]; // copy array aStateCopy[id] = aPlayer; return aStateCopy; }); } console.log(`A move for 'x' :\n${stateToString(stateNexts(initialState, 'x')[2])}`); console.log(`List of moves : ${stateEmptySlots(aState)}`); // Build a tree of all possible positions from a position `aState` for // a player `aPlayer` up to a certain depth `aDepth` function stateDepth(aState, aPlayer, aDepth) { if (aDepth === 0) { return node(aState, []); } else { const children = stateNexts(aState, aPlayer).map((aNextState) => stateDepth(aNextState, otherPlayer(aPlayer), aDepth-1)); return node(aState, children); } } let aTree = stateDepth(initialState, 'x', 3); console.log(`Root of the tree :\n${stateToString(val(aTree))}`); console.log(`Number of children :${children(aTree).length}`); treeDisp()(aTree); ////////// Exercice 2 ////////// // Builds a finite integer tree function makeFiniteIntegerTree(val, depth) { if (depth === 0) return node(val, []); else { const children = [ makeFiniteIntegerTree(2*val, depth-1), makeFiniteIntegerTree(2*val+1, depth-1) ]; return node(val, children); } } console.logA(makeFiniteIntegerTree(1, 3)); // Builds an 'infinite' integer tree (but lazily) // Note that there is no need for a `depth` parameter anymore function makeInfiniteIntegerTree(val) { let frozenChildren = () => [ makeInfiniteIntegerTree(2*val), makeInfiniteIntegerTree(2*val+1) ]; return node(val, frozenChildren); } let integerTree = makeInfiniteIntegerTree(1); for (let i = 0; i<4; i++) { treeThawAtDepth(integerTree, i); console.logA(integerTree); } ////////// Exercice 3 ////////// // Builds an 'infinite' integer tree (but lazily) function makeInfiniteIntegerTree(val) { let frozenChildren = freeze(() => [ makeInfiniteIntegerTree(2*val), makeInfiniteIntegerTree(2*val+1) ]); return node(val, frozenChildren); } let integerTree = makeInfiniteIntegerTree(1); for (let i = 0; i<4; i++) { treeThawAtDepth(integerTree, i); console.logA(integerTree); } ////////// Exercice 4 ////////// // Builds an infinite and frozen game tree, from an initial state // `initState` and a starting player `startPlayer` function makeGameTree(initState, startPlayer) { let frozenChildren = freeze(() => stateNexts(initState, startPlayer) .map((aState) => makeGameTree(aState, otherPlayer(startPlayer)))); return node(initState, frozenChildren); } let gameTree = makeGameTree(initialState, 'x'); treeDisp(stateToString)(gameTree); treeThawAtDepth(gameTree, 1); treeDisp(stateToString)(gameTree); // Unfolds an entire game at random inside the tree `t` function playRandomGameLazy(t) { if (stateIsFinal(t.val)) { t.winner = stateWinner(t.val); return; } else { if (isFrozen(t)) nodeThaw(t); let anIndex = generateRandomInt({ low: 0, high: t.children.result.length }); let aChild = t.children.result[anIndex]; playRandomGameLazy(aChild); } } gameTree = makeGameTree(initialState, 'x'); treeDisp(stateToString)(gameTree); // The tree is frozen playRandomGameLazy(gameTree); // Play one game treeDisp(stateToString)(gameTree); // The tree is less frozen playRandomGameLazy(gameTree); // Play another game treeDisp(stateToString)(gameTree); // The tree contains two full games