This kata explores writing an AI for a two player, turn based game called *NIM*.

The Board
--------------

The board starts out with several piles of straw.  Each pile has a random number of straws.

```
Pile 0: ||||

Pile 1: ||

Pile 2: |||||

Pile 3: |

Pile 4: ||||||

...or more concisely: [4,2,5,1,6]
```

The Rules
--------------

- The players take turns picking a pile, and removing any number of straws from the pile they pick
- A player must pick at least one straw
- If a player picks the last straw, she wins!

The Task
------------

In this kata, you have to write an AI to play the straw picking game.

You have to encode an AI in a function `choose_move` (or `chooseMove`, or `choose-move`) that takes a board, represented as a list of positive integers, and returns

```python
(pile_index, number_of_straws)
```

Which refers to an index of a pile on the board, and some none-zero number of straws to draw from that pile.

The test suite is written so that your AI is expected to play 50 games and win every game it plays.

Difficulty: MEDIUM_HARD
Tags: Game theory

Mathematics

Ad-hoc

Starter code:
def choose_move(game_state):
	

Solutions:
from operator import xor

def choose_move(game_state):
	x = reduce(xor, game_state)
	for (i, amt) in enumerate(game_state):
		if amt ^ x < amt:
			return (i, amt - (amt ^ x))


from itertools import zip_longest
import random

def choose_move(game_state):

	def is_nim_sum_zero(nums):
		to_add = []
		for num in nums:
			to_add.append(list(bin(num)[2:]))
		to_transpose = [b[::-1] for b in to_add]
		cols = [col for col in zip_longest(*to_transpose, fillvalue=0)]
		sum = 0
		for col in cols:
			if col.count('1') % 2 != 0:
				return False
		return True
	non_empty_piles = [i for i in range(len(game_state)) if game_state[i] != 0]
	if is_nim_sum_zero(game_state):
		pile = random.choice(non_empty_piles)
		quant = random.choice(list(range(1, game_state[pile])) + 1)
	else:
		next_ply = list(game_state)
		pile_ind = 0
		pile = non_empty_piles[pile_ind]
		quant = 1
		next_ply[pile] = next_ply[pile] - quant
		while not is_nim_sum_zero(next_ply):
			next_ply = list(game_state)
			if quant < next_ply[pile]:
				quant += 1
			else:
				pile_ind += 1
				pile = non_empty_piles[pile_ind]
				quant = 1
			next_ply[pile] = next_ply[pile] - quant
	return (pile, quant)


def choose_move(game_state):
	nim = reduce(lambda x, y: x ^ y, game_state, 0)
	return [(i, x - (x ^ nim)) for (i, x) in enumerate(game_state) if x ^ nim < x][0]


from operator import xor
from functools import reduce

def choose_move(game_state):
	nim_sum = reduce(xor, game_state)
	to_take = (s - (s ^ nim_sum) for s in game_state)
	return next(((i, t) for (i, t) in enumerate(to_take) if t > 0))


from operator import xor
from functools import reduce

def choose_move(game_state):
	diffs = [amount ^ reduce(xor, game_state) for amount in game_state]
	offsets = [pile - diff for (pile, diff) in zip(game_state, diffs)]
	amount_of_straws = max(offsets)
	return (offsets.index(amount_of_straws), amount_of_straws)


def choose_move(game_state):
	value = reduce(lambda x, y: x ^ y, game_state)
	(i, v) = [(i, v) for (i, v) in enumerate(game_state) if v ^ value < v][0]
	return (i, v - (v ^ value))


import operator

def choose_move(heaps):
	x = reduce(operator.xor, heaps)
	return next(((i, h - (x ^ h)) for (i, h) in enumerate(heaps) if x ^ h < h))


from functools import reduce

def choose_move(game_state):
	cond = reduce(lambda x, y: x ^ y, game_state)
	for (idx, val) in enumerate(game_state):
		if val ^ cond < val:
			return (idx, val - (val ^ cond))