RL_Qtable_sym_0.1.py

"""
Discrete Q table that does not need deep learning, with dihedral symmetry of the board
State = Board vector / equivalence class = {-1,0,1}^9 / ~ = 765
Further reduced to non-ending states = 627
* size of original Q-table was 3^9 * 9 = 177,147, versus 627 * 9 = 5643;  shrinked ~31 times

This version does not work because the actions have not been transformed
while the boards are.  Next version should solve this problem by transforming
every (s,a) pair.
"""

import random
import numpy as np

class ReplayBuffer:
	def __init__(self, capacity):
		self.capacity = capacity
		self.buffer = []
		self.position = 0

	def push(self, state, action, reward, next_state, done):
		if len(self.buffer) < self.capacity:
			self.buffer.append(None)
		self.buffer[self.position] = (state, action, reward, next_state, done)
		self.position = (self.position + 1) % self.capacity

	def last_reward(self):
		return self.buffer[self.position -1][2]

	def sample(self, batch_size):
		# **** Old method: random sample
		# batch = random.sample(self.buffer, batch_size)
		# New method uses the latest data, seems to converge a bit faster
		# initially, but overall performance is similar to old method
		if self.position >= batch_size:
			batch = self.buffer[self.position - batch_size : self.position]
		else:
			batch = self.buffer[: self.position] + self.buffer[-(batch_size - self.position) :]
		assert len(batch) == batch_size, "batch size incorrect"

		states, actions, rewards, next_states, dones = \
			map(np.stack, zip(*batch)) # stack for each element
		'''
		the * serves as unpack: sum(a,b) <=> batch=(a,b), sum(*batch) ;
		zip: a=[1,2], b=[2,3], zip(a,b) => [(1, 2), (2, 3)] ;
		the map serves as mapping the function on each list element: map(square, [2,3]) => [4,9] ;
		np.stack((1,2)) => array([1, 2])
		'''
		# print("sampled state=", state)
		# print("sampled action=", action)
		return states, actions, rewards, next_states, dones

	def __len__(self):
		return len(self.buffer)

class Qtable():
	ILLEGAL = 19682
	WIN = 4918
	LOSE = 5029
	DRAW = 4880
	# The first state {9841} is the "clean board"; following by ILLEGAL, WIN, LOSE, in that order
	eqClasses = [
{9841}, {19682}, {4104, 14348, 12312, 14366, 16416, 14374, 4146, 14392, 4152, 14400, 6210, 4164, 4170, 4176, 16470, 18522, 8282, 4188, 4194, 8300, 12398, 12400, 12404, 8308, 12406, 12408, 6264, 12412, 12414, 8326, 14472, 8334, 18576, 152, 158, 160, 4266, 6324, 10422, 6330, 14526, 6336, 16578, 18630, 6348, 206, 6354, 212, 214, 4320, 224, 6372, 230, 232, 236, 238, 240, 12528, 16632, 14588, 14594, 14596, 14600, 14602, 14604, 6426, 2330, 14618, 8478, 14626, 12582, 16686, 18738, 14644, 314, 14652, 320, 322, 8516, 8524, 6480, 2384, 4436, 8534, 10584, 8542, 4452, 8550, 18792, 2408, 2410, 8560, 368, 374, 8568, 376, 386, 16772, 16774, 392, 4490, 394, 16778, 16780, 398, 16782, 400, 10638, 402, 12690, 16788, 16786, 4514, 4516, 422, 428, 430, 440, 2492, 446, 8640, 448, 452, 454, 456, 12744, 2508, 14796, 464, 466, 470, 4568, 472, 474, 478, 480, 4592, 4594, 14834, 8694, 10746, 14842, 12798, 14852, 16902, 14860, 530, 14868, 536, 538, 14878, 548, 14886, 554, 4652, 556, 10800, 560, 562, 564, 2616, 4668, 16956, 4676, 4678, 584, 4686, 590, 592, 4692, 602, 608, 610, 614, 10854, 616, 8810, 618, 12906, 14958, 4722, 626, 628, 632, 634, 636, 640, 642, 656, 2708, 662, 664, 668, 670, 672, 12960, 2724, 15012, 680, 17064, 682, 2732, 2734, 686, 688, 690, 2742, 694, 696, 2748, 4800, 10952, 10958, 10960, 6866, 10970, 2778, 15068, 6878, 17118, 15076, 8934, 10994, 10996, 15094, 15102, 4868, 15120, 4884, 17172, 4892, 4894, 11040, 2850, 4902, 2856, 4908, 4916, 4918, 4920, 4926, 9026, 4932, 15174, 6990, 9050, 4956, 9052, 4962, 872, 11118, 15228, 13184, 17280, 9096, 13196, 926, 2978, 5034, 7082, 5040, 11186, 2994, 17334, 950, 952, 7094, 11202, 7106, 7108, 7112, 11210, 11212, 9168, 7120, 9174, 3032, 15326, 11234, 11236, 15332, 11238, 15334, 15344, 7152, 3058, 3056, 13308, 5120, 5126, 5128, 15368, 15370, 11274, 3086, 11280, 5138, 1046, 9242, 1050, 5154, 3110, 3112, 9258, 5162, 5164, 9266, 5172, 9268, 15414, 7224, 5178, 3134, 7230, 3136, 3138, 5192, 9290, 9292, 9294, 11352, 13400, 11358, 17504, 5216, 5218, 13412, 17510, 17512, 17516, 17518, 13424, 17520, 13426, 9330, 13430, 5240, 17528, 5242, 17530, 5244, 9336, 15486, 13438, 11394, 15492, 3210, 17552, 17554, 17556, 5270, 3228, 13470, 11426, 3234, 11428, 11436, 5294, 5296, 11442, 17592, 9402, 11450, 11452, 11454, 17598, 9408, 7364, 9414, 5320, 15560, 5322, 11476, 11478, 15576, 15584, 15586, 13542, 13548, 1262, 1266, 11508, 15608, 5370, 11514, 15612, 15610, 11520, 1280, 1284, 17670, 1288, 1290, 17676, 5388, 5394, 9494, 9500, 5406, 9502, 15648, 11556, 5412, 15654, 5418, 17712, 13616, 11586, 11592, 13640, 13642, 13646, 17744, 17746, 17754, 11610, 17760, 13664, 3426, 13666, 13668, 15720, 13672, 17768, 17770, 17772, 15726, 3444, 15732, 3450, 17794, 17796, 3462, 13704, 3468, 3474, 15768, 11672, 7580, 11678, 11680, 17826, 11684, 11686, 11688, 17832, 17838, 7598, 7606, 15800, 5562, 15802, 15810, 13776, 15824, 17874, 15826, 15828, 13782, 5604, 15850, 5610, 15852, 17904, 5622, 17910, 5628, 1536, 5634, 17928, 15882, 5646, 15888, 5652, 1574, 13868, 13874, 13876, 15930, 17984, 1600, 17986, 17988, 17994, 13898, 3662, 3668, 3670, 15960, 18010, 5724, 1628, 18012, 15966, 3680, 13916, 13924, 11880, 15984, 3696, 18036, 1652, 1654, 7796, 3706, 3714, 7814, 3720, 1678, 7822, 1680, 5778, 18066, 3734, 18072, 7832, 7840, 7848, 18090, 16046, 3758, 3760, 16052, 16054, 16058, 16060, 16062, 3784, 3786, 9936, 5840, 1748, 5846, 5848, 1752, 5852, 5854, 5856, 18144, 3812, 3814, 5864, 5866, 1770, 1774, 1776, 5874, 5880, 3836, 3838, 3840, 5890, 5892, 5898, 12042, 5904, 3862, 3864, 5918, 5920, 14114, 14132, 5942, 18230, 5944, 18232, 5946, 18236, 14140, 18238, 18240, 12096, 18244, 14150, 18246, 3912, 14158, 5968, 5970, 14166, 3930, 3936, 8036, 8042, 3948, 5996, 5998, 8044, 10098, 3954, 3960, 16254, 8066, 6022, 6024, 8092, 6048, 10152, 1964, 12204, 1968, 18360, 1982, 1986, 1990, 1992, 6090, 6096, 2004, 2008, 2010, 6108, 2016, 12258, 6114, 10214, 14310, 6120, 10220, 18414, 10222, 10226, 6132, 10228, 10230, 6138}, {8201, 8203, 8205, 14359, 14361, 10265, 10271, 2081, 8227, 8229, 8237, 14385, 8253, 16445, 2125, 2127, 4187, 6243, 14437, 2151, 10343, 14439, 6255, 2161, 2163, 2169, 14463, 8321, 10387, 10389, 16543, 12449, 16545, 14501, 10413, 14517, 16569, 8399, 4311, 2267, 16623, 8443, 8445, 10505, 12561, 2321, 8469, 12573, 18729, 14639, 2375, 4427, 14717, 4481, 10629, 14747, 14753, 14761, 14763, 14771, 2483, 16823, 14787, 4553, 4561, 4579, 2537, 4587, 8685, 6641, 4605, 4643, 16931, 18983, 6695, 18985, 18987, 18991, 18993, 16947, 18999, 19009, 19011, 19017, 6749, 19037, 19039, 19041, 8801, 19045, 19047, 19053, 19063, 19065, 19071, 2699, 14987, 8855, 15003, 19117, 19119, 4787, 19125, 4795, 6857, 4813, 4821, 4839, 15087, 6911, 19199, 19201, 19203, 19207, 19209, 19215, 19225, 19227, 19233, 809, 9017, 15165, 2891, 2893, 2895, 19279, 19281, 2899, 2901, 19287, 2907, 863, 11105, 11113, 17271, 13175, 11131, 11139, 11157, 917, 2969, 7073, 5029, 13229, 5055, 3023, 5077, 5079, 5085, 19441, 19443, 13301, 19449, 13307, 1025, 13319, 13325, 13331, 13343, 13349, 1079, 13391, 11347, 7265, 7267, 7269, 7273, 7275, 11373, 7281, 3185, 15479, 15485, 15491, 15503, 15509, 5281, 15527, 5289, 7343, 5307, 1241, 13535, 13541, 7397, 9451, 13547, 9453, 9459, 13559, 13565, 17663, 17665, 17669, 13583, 17687, 17691, 13631, 13633, 13657, 13659, 15719, 15725, 13683, 15743, 7559, 5515, 13709, 13711, 5523, 1433, 1435, 1437, 1441, 1443, 5541, 13735, 1449, 13737, 13761, 15815, 15817, 13775, 13781, 13789, 15841, 15843, 13799, 1511, 17903, 13815, 1529, 15867, 1535, 13825, 13827, 13833, 15895, 1565, 3619, 3621, 3627, 15921, 11833, 11841, 1607, 1613, 18001, 11859, 15959, 18027, 1643, 1645, 5757, 3713, 1667, 1669, 1671, 3719, 1685, 1693, 1695, 1727, 14021, 14027, 3791, 14033, 14045, 1763, 14051, 1769, 3827, 14069, 3829, 3831, 5897, 3853, 3855, 3879, 12075, 1841, 1847, 7993, 7995, 8001, 16205, 16211, 1883, 1885, 1887, 16229, 3947, 3953, 1909, 1911, 6009, 6013, 6015, 1919, 1935, 8081, 6039, 8087, 14261, 4025, 14267, 14285, 2003, 18389, 18393, 8159, 4069, 8165, 4071, 6131, 4095}, {17568, 1952, 19682, 4448, 15072, 5024, 4608, 13344, 2112, 4556, 13356, 2108, 4880, 14640, 6320, 13200, 14748}, {3280, 9840, 9112, 9832}, {11299, 3523, 9835, 9867, 5467, 9843, 9139, 10075}, {9138, 4738, 3514, 9834}, {9861, 5701, 10077, 11325, 4981, 9141, 4765, 3517}, {4900, 9060, 3436, 4684, 11244, 9996, 9780, 5620}, {5623, 11247, 10023, 4927}, {7836, 5596, 4924, 11004}, {4933, 11013, 4925, 14397, 8565, 17565, 6325, 5597}, {10509, 3437, 4685, 4909, 17805, 6349, 16557, 9069}, {1250, 6882, 17802, 6346, 4442, 4882, 16530, 10266}, {18045, 12453, 6373, 4885, 7125, 18717, 4445, 1277}, {4451, 13443, 6347, 17259, 4883, 17811, 16827, 1979}, {8322, 14370, 4906, 4682, 3410, 6322, 8826, 17562}, {14883, 17571, 15387, 4139, 4907, 4691, 6323, 15099}, {11487, 3463, 4903, 4687, 5647, 9303, 12183, 11967}, {12156, 11724, 4876, 5644, 7116, 1276, 4444, 11484}, {11493, 4453, 18285, 4877, 5645, 13677, 2005, 12885}, {4165, 4901, 10725, 15621, 16341, 11253, 4693, 5621}, {16098, 4450, 13434, 4874, 10698, 11250, 5618, 1978}, {4898, 11010, 4138, 14154, 8538, 4690, 15378, 5594}, {5698, 10050, 11322, 4522, 6954, 1330, 9618, 4954}, {1411, 9699, 7035, 5035, 11403, 5779, 10131, 4603}, {5050, 5026, 1410, 8970, 4842, 3570, 7026, 4602}, {4611, 5027, 5051, 15531, 4299, 4851, 13587, 2139}, {7512, 5032, 1384, 7944, 6792, 5752, 11160, 4600}, {17721, 1385, 14505, 5041, 8241, 6481, 6801, 4601}, {2113, 11169, 4609, 8673, 5033, 13353, 5753, 14073}, {4963, 16611, 10347, 4523, 6427, 1331, 6963, 17883}, {4960, 8160, 6400, 6720, 17640, 4520, 1304, 14424}, {4961, 14721, 6401, 13281, 2033, 4529, 17649, 15153}, {5725, 4957, 11565, 1357, 4525, 12237, 7197, 11805}, {11076, 4996, 5004, 4524, 1356, 5676, 4948, 7188}, {17637, 2085, 4997, 6405, 4949, 5013, 4533, 13749}, {11331, 5699, 2059, 13515, 16179, 4531, 10779, 4955}, {4770, 13506, 4218, 2058, 4970, 4530, 4946, 15450}, {13992, 5672, 4528, 2032, 11088, 8592, 13272, 4952}, {4764, 9132, 4972, 3516}, {4845, 3597, 5053, 9213}, {4836, 5052, 2868, 2652}, {9375, 5703, 4999, 5007, 4975, 11319, 3543, 4767}, {2814, 4974, 4758, 4998}, {5001}, {15693, 4973, 4245, 4773}, {3490, 8898, 11082, 5674, 4978, 7890, 4762, 7674}, {5059, 7971, 4843, 7755, 5755, 3571, 8979, 11163}, {5058, 4834, 1194, 7242, 11154, 2418, 5754, 2842}, {1923, 4835, 5067, 13803, 17715, 6483, 2427, 2843}, {7917, 5677, 11085, 5005}, {3491, 6403, 17643, 8907, 8403, 14451, 4987, 4763}, {17634, 6402, 2762, 2346, 13722, 1842, 4754, 4986}, {4771, 15459, 4219, 5675, 8619, 11091, 4979, 14235}, {3300, 2788, 5700, 9348, 4756, 4980, 11316, 2580}, {4837, 5061, 11397, 2661, 2869, 3381, 5781, 9429}, {2589, 2789, 15909, 4029, 17877, 4757, 6429, 4989}, {11559, 2823, 5727, 5487, 4983, 11535, 4759, 2815}, {9219, 4819, 3595, 9915}, {4576, 9888, 1408, 9216, 3592, 9672, 7032, 4792}, {2137, 13593, 4585, 3593, 16233, 9225, 4793, 10617}, {10374, 4550, 4558, 16206, 7038, 13590, 2134, 1406}, {13599, 16935, 2135, 4559}, {13350, 4582, 14046, 3566, 8430, 4790, 8982, 2110}, {4295, 4583, 14991, 13359, 14775, 15543, 2111, 4799}, {4584, 2664, 13584, 2864, 4784, 15504, 4056, 2136}, {16449, 4577, 7041, 4801, 4321, 1409, 10401, 15777}, {4574, 4294, 1382, 6798, 15534, 14262, 8214, 4798}, {9186, 2658, 9210, 3594, 4810, 4818, 2866, 3354}, {15747, 4323, 2667, 4811, 2867, 4083, 15771, 4827}, {13560, 2424, 4808, 4296, 1896, 15528, 2840, 4824}, {4816, 8976, 7728, 3568}, {8457, 4297, 15537, 4817, 3569, 14289, 8985, 4825}, {4739, 10563, 9147, 4747, 16395, 15699, 4243, 3515}, {3512, 10536, 4712, 13512, 2056, 16152, 9144, 4504}, {2083, 18339, 4715, 9387, 3539, 12723, 13755, 4507}, {12642, 3458, 9306, 4426, 13674, 2002, 18258, 4634}, {4480, 12480, 2080, 7200, 13752, 1352, 18312, 4472}, {4706, 2082, 2810, 17610, 2826, 13746, 6162, 4506}, {15705, 17097, 2057, 4241, 4721, 13521, 16881, 4505}, {4640, 4160, 13440, 16800, 4424, 15624, 1976, 17016}, {16854, 13518, 4478, 2054}, {14694, 15462, 4718, 2030, 13278, 4214, 4502, 14910}, {16314, 15618, 4162, 3434, 9066, 4658, 10482, 4666}, {3461, 18501, 4189, 15861, 4661, 9309, 4669, 12669}, {4642, 4418, 4186, 12426, 18474, 15858, 7122, 1274}, {15627, 4163, 4667, 17043}, {4664, 15384, 4136, 14856}, {4720, 10320, 15696, 1328, 4496, 4240, 16368, 6960}, {15939, 7203, 1355, 4267, 18555, 4499, 4723, 12507}, {3488, 15456, 4736, 14208, 4744, 8904, 8376, 4216}, {14937, 4745, 4217, 15465}, {4002, 2786, 4746, 15690, 4242, 15666, 2586, 4730}, {15933, 4733, 4749, 6189, 4269, 2829, 2813, 17853}, {3541, 12021, 4741, 9381}, {11778, 7194, 9378, 4714, 1354, 4498, 3538, 11994}, {3460, 11940, 4660, 9300}, {4732, 4740, 2820, 2812, 9372, 3540, 5460, 11292}, {1336, 9592, 5224, 6952, 11272, 9816, 9864, 10072}, {5953, 9825, 1345, 10593, 17833, 6953, 9593, 16633}, {16552, 9512, 6872, 5872, 9744, 1264, 10512, 17752}, {9987, 9539, 17995, 5899, 18739, 1267, 12699, 6875}, {5896, 17992, 6632, 12456, 7800, 18712, 7352, 1240}, {13193, 17993, 13913, 8529, 5905, 1969, 12465, 18713}, {13433, 10521, 17753, 16553, 10473, 1993, 16073, 5881}, {13190, 10278, 13886, 16526, 1966, 5878, 17750, 8286}, {17759, 17255, 16839, 13199, 1967, 5879, 14615, 14847}, {16579, 10755, 7115, 1291, 5875, 11699, 17755, 11931}, {17281, 6881, 17761, 10241, 5873, 16305, 1265, 17073}, {16830, 14118, 17254, 6638, 5870, 1238, 8054, 17758}, {9566, 6950, 5926, 14446, 9582, 17590, 8406, 1342}, {14527, 17671, 8487, 6007, 1423, 9647, 7031, 9663}, {6788, 14500, 17668, 7460, 6004, 7476, 1396, 8244}, {17677, 6797, 8189, 14037, 6005, 1397, 14805, 15229}, {13798, 1926, 7022, 1422, 6006, 3102, 8918, 17662}, {8415, 13511, 10311, 14447, 5935, 2071, 17591, 16127}, {5932, 2044, 8172, 13268, 17588, 14420, 13940, 8124}, {15149, 5933, 14669, 14733, 2045, 17597, 14685, 13277}, {3750, 15398, 5934, 17582, 1854, 13718, 2070, 13502}, {5937, 13745, 17585, 2097}, {1369, 5929, 14473, 11753, 8649, 11769, 17593, 7193}, {1368, 5928, 2088, 7184, 13744, 17584, 11024, 5208}, {1343, 15175, 5927, 14967, 16143, 6959, 10295, 17599}, {13956, 5924, 1316, 14724, 15148, 8108, 17596, 6716}, {17830, 1318, 7406, 10350, 5950, 6710, 7638, 16606}, {10431, 7487, 6791, 7719, 16687, 6031, 17911, 1399}, {1158, 6758, 17902, 6030, 3870, 15958, 1398, 6782}, {6057, 6785, 18145, 1401}, {12537, 18793, 7881, 1321, 7433, 6713, 18073, 5977}, {5976, 6704, 1320, 18064}, {5985, 18065, 13265, 2049}, {17831, 5959, 8367, 13967, 13271, 2047, 10359, 16607}, {15878, 5958, 13262, 1806, 2046, 13238, 3798, 17822}, {1319, 8135, 17839, 16911, 17335, 5951, 14199, 6719}, {5952, 6944, 15904, 17824, 3264, 1344, 8864, 4032}, {6033, 17905, 7025, 15985, 3345, 1425, 8945, 4113}, {6947, 1347, 18091, 6219, 18067, 3507, 5979, 8891}, {17825, 13505, 15905, 15425, 5961, 4041, 3993, 2073}, {5955, 17827, 5451, 11051, 1371, 7187, 4275, 15931}, {5305, 7033, 9897, 10153, 1417, 9673, 9945, 11353}, {11110, 1414, 9646, 7966, 7758, 7030, 9654, 5278}, {7767, 11111, 5287, 10383, 16207, 13591, 2143, 7967}, {11108, 7940, 5284, 8196, 13348, 2116, 14020, 7524}, {5285, 14757, 2117, 14085, 13357, 11117, 8669, 14749}, {7238, 5286, 3822, 13582, 15478, 1206, 2142, 11102}, {5279, 1415, 10375, 16215, 11119, 14319, 8695, 7039}, {14076, 6796, 14028, 11116, 1388, 8188, 5276, 8668}, {7486, 6790, 9702, 10126, 1390, 11350, 5302, 7710}, {7513, 11593, 6793, 5329, 7953, 1393, 11889, 12313}, {5328, 11584, 1392, 6784}, {2121, 5337, 11585, 13345}, {13351, 2119, 10127, 9711, 14047, 11351, 8439, 5311}, {13342, 2118, 13318, 11342, 3150, 1878, 9398, 5310}, {10855, 16263, 6799, 1391, 8215, 5303, 11359, 14271}, {3384, 3336, 1416, 11344, 7024, 9424, 8944, 5304}, {11587, 5571, 1419, 8971, 5331, 7027, 3579, 11611}, {5313, 4065, 2145, 3393, 11345, 9425, 13585, 15505}, {5251, 12259, 6955, 10059, 1339, 9619, 12051, 11515}, {9538, 11970, 11434, 1258, 9978, 5170, 12178, 6874}, {1987, 16099, 11435, 13435, 11979, 12179, 10707, 5179}, {11736, 8520, 13192, 11432, 1960, 13912, 12152, 5176}, {15081, 1961, 18297, 12881, 13201, 11441, 14641, 5177}, {12165, 1285, 7117, 11437, 12205, 11725, 5173, 12213}, {6883, 18531, 10267, 12907, 1259, 11443, 5171, 16539}, {5168, 14352, 12880, 11440, 6640, 1232, 8080, 18288}, {5248, 11512, 7872, 1312, 11808, 12232, 7432, 6712}, {11513, 12233, 5257, 13993, 11817, 8601, 13273, 2041}, {5256, 2040, 11504, 13264}, {6721, 5249, 12961, 14433, 11521, 1313, 8161, 18369}, {5250, 6946, 3498, 11530, 11506, 5490, 8890, 1338}, {4227, 13507, 11531, 5259, 11507, 2067, 5499, 15451}, {11557, 5253, 11077, 5733, 11509, 7189, 5685, 1365}, {13513, 11273, 5233, 10545, 2065, 9873, 16153, 10073}, {5152, 10464, 1984, 9792, 9992, 16072, 11192, 13432}, {10019, 5155, 2011, 12651, 13675, 18259, 10035, 11195}, {5153, 13441, 17025, 11201, 10721, 1985, 16801, 16353}, {10694, 1958, 13198, 16110, 11198, 14838, 14614, 5150}, {13510, 7686, 7886, 2062, 16126, 5206, 11030, 10302}, {12489, 7913, 13753, 2089, 18313, 7929, 11033, 5209}, {16855, 8615, 14247, 13519, 2063, 11039, 5207, 16863}, {11036, 8588, 14668, 5204, 14676, 2036, 14004, 13276}, {9630, 8358, 11270, 5230, 13966, 13270, 2038, 10046}, {14919, 14695, 11279, 5231, 2039, 16191, 10775, 13279}, {11264, 9344, 13504, 15424, 5232, 3984, 2064, 3312}, {11267, 3555, 2091, 9371, 17611, 5235, 13747, 6171}, {12003, 11779, 10107, 5227, 11275, 10099, 1363, 7195}, {10018, 5146, 1282, 7114, 10026, 11922, 11698, 11194}, {11203, 1283, 12427, 16587, 18483, 7123, 10747, 5147}, {7912, 11752, 5200, 11760, 11032, 1360, 7920, 7192}, {8641, 11041, 7201, 12481, 5201, 18321, 1361, 14481}, {11266, 5442, 5226, 11050, 3546, 7186, 1362, 9370}, {1337, 5225, 16425, 11281, 10801, 6961, 10321, 16377}, {10720, 11200, 6880, 10240, 16296, 1256, 16344, 5144}, {8614, 16134, 6958, 5198, 14238, 1334, 10294, 11038}, {5222, 8134, 14190, 11278, 10774, 16182, 6718, 1310}, {9762, 9058, 5386, 9994, 11218, 3442, 9786, 9754}, {9059, 6115, 9771, 16555, 17779, 10515, 9755, 3451}, {14368, 9056, 17536, 9728, 3448, 6088, 8328, 9528}, {14371, 5635, 11243, 17563, 8331, 9555, 9971, 6331}, {14344, 7368, 5608, 7784, 11000, 8088, 6328, 17560}, {6337, 17561, 8097, 14345}, {15073, 11009, 17569, 8513, 14649, 13929, 5609, 6329}, {14369, 17537, 15617, 16289, 6097, 10257, 4177, 8337}, {14342, 8070, 6094, 15374, 8094, 4150, 14102, 17534}, {14655, 17543, 14631, 6095, 14831, 4151, 15383, 15071}, {17539, 11715, 6091, 11915, 9299, 3475, 8571, 14395}, {6082, 17538, 10986, 5354, 2738, 8562, 2746, 14394}, {15123, 6083, 17547, 2747}, {10457, 6089, 17545, 9065, 3449, 14889, 15097, 16089}, {6080, 15360, 2720, 14880, 17544, 2504, 3896, 15096}, {3422, 17542, 6086, 13902, 8270, 8822, 14646, 15070}, {2498, 2722, 3194, 16554, 10506, 9042, 17778, 6106}, {2501, 18021, 9285, 2725, 18741, 6133, 3221, 12693}, {18018, 12450, 2698, 18714, 1034, 2258, 6130, 7098}, {10749, 16581, 5381, 2749, 6109, 17781, 2741, 11229}, {17283, 2723, 6107, 2507, 17067, 15603, 3923, 17787}, {17784, 16824, 13416, 17256, 2696, 1736, 6104, 2264}, {6112, 7584, 3424, 10272, 8816, 16528, 17776, 7568}, {7811, 10275, 17803, 5611, 6355, 16531, 7611, 11003}, {18019, 3427, 6139, 7595, 12459, 8819, 7827, 18715}, {6121, 10281, 16529, 17777, 15377, 14129, 8313, 4153}, {14145, 6113, 3425, 16833, 17257, 8297, 8825, 17785}, {11245, 9997, 9789, 5629}, {5602, 7810, 9546, 11242, 5626, 9970, 7602, 11002}, {5605, 7837, 7845, 11005, 12157, 11733, 5653, 11485}, {11011, 5603, 16107, 10699, 11251, 14163, 5627, 8539}, {5600, 11008, 8512, 13920}, {11461, 9061, 5413, 11973, 10005, 12181, 3445, 9781}, {2716, 11964, 11460, 2500, 9276, 12180, 3220, 5404}, {2743, 11463, 12207, 5407}, {2717, 2509, 11469, 12909, 3949, 18525, 5405, 15837}, {2690, 1762, 11466, 5402, 18282, 13650, 12882, 2266}, {11458, 5410, 7818, 7594, 3418, 8818, 11730, 12154}, {8547, 11459, 5419, 14155, 15379, 4147, 11739, 12155}, {5411, 8323, 14379, 11467, 3419, 12883, 18291, 8827}, {15619, 9795, 16315, 9995, 4171, 5395, 11219, 10491}, {15616, 10976, 7808, 16288, 7608, 10248, 4168, 5368}, {10979, 4195, 18475, 7851, 12435, 15859, 5371, 7835}, {5369, 16809, 10985, 15625, 4169, 17017, 14169, 8537}, {10982, 13926, 4142, 14830, 5366, 15382, 8510, 14622}, {5392, 15376, 9968, 8304, 11216, 4144, 14128, 9552}, {10697, 14857, 5393, 14865, 4145, 16113, 15385, 11225}, {10021, 11941, 5389, 11949, 3469, 10029, 11221, 9301}, {10978, 7842, 3466, 11914, 5362, 9298, 7834, 11706}, {18267, 12643, 14403, 10987, 3467, 8563, 5363, 9307}, {2740, 11220, 5380, 10020}, {16323, 10723, 16347, 9067, 5387, 3443, 10483, 11227}, {10984, 9064, 5360, 16080, 3440, 14160, 8536, 10456}, {5378, 10722, 2506, 15594, 3922, 16338, 2714, 11226}, {3416, 5384, 10696, 8296, 16104, 8824, 11224, 14136}, {5440, 9600, 3520, 7680, 11056, 9136, 7888, 9808}, {8409, 9609, 3529, 9137, 14449, 17617, 9809, 6169}, {6160, 2576, 14448, 8880, 17616, 2800, 3248, 8400}, {2657, 6241, 14529, 8961, 17697, 2881, 3329, 8481}, {14502, 2854, 2414, 8238, 6774, 1142, 6238, 17694}, {17703, 2855, 1871, 14799, 13335, 6239, 2423, 15231}, {6240, 2400, 2880, 1920, 13800, 2600, 2648, 17688}, {2819, 8643, 14475, 2827, 5435, 6163, 17619, 11067}, {15177, 3977, 2585, 15441, 6161, 2801, 14961, 17625}, {14718, 2342, 13254, 6158, 15150, 17622, 2774, 1790}, {7622, 8166, 17614, 3502, 7422, 14422, 6166, 8894}, {14425, 11081, 6409, 17641, 8169, 5689, 7865, 7449}, {17632, 11072, 13696, 7136, 6408, 1608, 5688, 888}, {969, 5769, 11153, 13777, 17713, 7217, 1689, 6489}, {1617, 6417, 13697, 17633}, {14503, 6247, 3583, 8975, 7503, 8247, 7703, 17695}, {6246, 8966, 942, 13774, 6974, 17686, 1686, 3582}, {4231, 14183, 17615, 8175, 14423, 8151, 6175, 15455}, {17606, 4230, 13454, 1614, 1590, 15446, 6174, 13694}, {8351, 8903, 14727, 15151, 3503, 6167, 17623, 13983}, {13720, 3048, 9128, 17608, 3528, 1848, 9080, 6168}, {1851, 3075, 17635, 6411, 9323, 11315, 5715, 13723}, {17689, 6249, 13801, 9161, 1929, 3609, 9209, 3129}, {6177, 3777, 4257, 1857, 15641, 15689, 17609, 13721}, {10051, 7683, 11083, 5707, 5683, 9627, 7891, 11323}, {5680, 7440, 11080, 7864}, {5761, 11161, 7521, 7945}, {5760, 7216, 11152, 960}, {11089, 5681, 8593, 14001}, {11074, 3066, 1122, 5706, 9322, 5682, 11314, 7162}, {5763, 11395, 7243, 3147, 9403, 11155, 1203, 5787}, {11075, 6435, 7163, 15883, 1131, 3795, 17875, 5691}, {11137, 9217, 7969, 9889, 5521, 9681, 3601, 7761}, {7968, 2656, 11136, 3328, 5512, 7752, 2872, 8952}, {2665, 5513, 11145, 14313, 8697, 2873, 15513, 4057}, {11142, 5510, 13326, 2846, 1870, 2422, 14070, 8670}, {7518, 7494, 7942, 5518, 8974, 3574, 7702, 11134}, {5527, 7943, 7527, 15535, 4303, 14263, 11135, 8223}, {15526, 966, 7214, 4302, 11126, 5526, 13534, 1662}, {3575, 11143, 14055, 5519, 8431, 14079, 8983, 8671}, {7240, 9160, 5520, 3120, 3600, 1200, 11128, 9208}, {1209, 11129, 7241, 15769, 3849, 4329, 15721, 5529}, {4249, 5449, 7689, 15697, 7889, 11057, 16369, 10329}, {5446, 14182, 11054, 8142, 7862, 7446, 4222, 15454}, {15463, 5447, 14007, 14911, 8591, 14703, 11063, 4223}, {15640, 5448, 11048, 15688, 1128, 3768, 4248, 7160}, {5443, 9379, 11787, 7915, 11059, 7923, 3547, 11995}, {7914, 5434, 2818, 11058}, {5441, 16161, 3521, 14241, 8617, 10537, 11065, 9145}, {15432, 2584, 8616, 2792, 3976, 11064, 14232, 5432}, {8902, 3494, 8590, 13998, 11062, 13974, 8350, 5438}, {11298, 9858, 2794, 3274, 5458, 2578, 10074, 9114}, {9123, 17859, 6187, 3275, 10587, 2579, 2803, 16635}, {2336, 16608, 17856, 1088, 6184, 10344, 2776, 6936}, {10425, 7017, 2857, 2417, 17937, 16689, 1169, 6265}, {2339, 6211, 1115, 7179, 18795, 18099, 12531, 2779}, {13497, 6185, 17865, 2345, 16905, 2777, 1817, 17337}, {4026, 2562, 15906, 6186, 2570, 2802, 2546, 17850}, {2883, 2627, 17931, 6267, 4107, 2643, 15987, 2651}, {2805, 2573, 6213, 18093}, {2659, 5539, 10155, 9195, 3355, 11379, 9939, 2875}, {5536, 7008, 2848, 9696, 11376, 2416, 10128, 1168}, {11619, 2851, 12315, 1195, 11883, 7251, 2419, 5563}, {5537, 11385, 13569, 2849, 16257, 10857, 1897, 2425}, {5538, 2626, 2634, 11370, 9426, 3378, 2650, 2874}, {11613, 2877, 2653, 5565}, {12261, 3301, 5485, 9357, 2797, 12045, 2581, 11541}, {7170, 2338, 12234, 5482, 11538, 2770, 11802, 1114}, {13731, 12963, 18363, 2347, 5483, 2771, 1843, 11547}, {11532, 5484, 2572, 2796}, {10101, 2821, 11301, 5461}, {4003, 16419, 11307, 2795, 15675, 5459, 10803, 2587}, {2344, 11304, 5456, 13488, 2768, 1816, 16176, 10776}, {11296, 10048, 8896, 7648, 9624, 7656, 3496, 5464}, {16609, 8897, 17857, 7649, 6193, 7665, 3505, 10353}, {17848, 15880, 6920, 6192, 1104, 3504, 3792, 8888}, {6273, 1185, 3585, 3873, 8969, 17929, 7001, 15961}, {15881, 1833, 17849, 4233, 13481, 3801, 15449, 6201}, {5545, 9705, 3577, 10129, 11377, 8977, 7729, 7737}, {5544, 8968, 11368, 3576, 3144, 7000, 1176, 9400}, {13561, 15529, 11369, 5553, 1905, 4305, 3153, 9401}, {8899, 11811, 12235, 3499, 11539, 5491, 7675, 7899}, {10049, 5473, 8385, 15457, 11297, 4225, 14209, 9633}, {5472, 1824, 4224, 3072, 9320, 13480, 11288, 15448}, {8377, 14217, 8905, 11305, 3497, 10777, 16185, 5465}, {9346, 11290, 3522, 9130, 3306, 3282, 9106, 5466}, {15907, 4035, 9131, 3531, 3291, 6195, 9107, 17851}, {3309, 11317, 5709, 9349}, {3363, 9187, 11371, 5547, 3387, 9427, 3603, 9211}, {3525, 11533, 5493, 9133}, {5475, 9347, 15691, 4011, 4251, 15667, 3315, 11291}, {3549, 11293, 5469, 9373}, {3289, 15673, 4009, 16393, 9833, 10569, 9849, 9113}, {3046, 9830, 13486, 1822, 10542, 9846, 16150, 9086}, {16231, 9927, 9911, 10623, 9167, 1903, 3127, 13567}, {16228, 13540, 6980, 9668, 9900, 940, 10620, 1660}, {6983, 1687, 12807, 9695, 18415, 943, 13783, 10143}, {13780, 18388, 1684, 7956, 6740, 916, 7508, 12564}, {13543, 967, 1663, 11855, 10863, 7223, 12087, 16255}, {1636, 11844, 964, 8676, 13300, 14068, 7220, 11828}, {18405, 1637, 965, 15237, 14797, 12557, 7229, 13309}, {1661, 17181, 13549, 16461, 6989, 941, 10397, 16957}, {1634, 13306, 10370, 6986, 938, 14770, 14994, 16218}, {14274, 16930, 13546, 16938, 914, 8210, 6746, 1658}, {9884, 9164, 13324, 9684, 1876, 3124, 8436, 14044}, {12071, 8679, 11871, 13327, 1879, 3151, 14071, 9407}, {9173, 16245, 13333, 1877, 14773, 3125, 10613, 14997}, {1868, 14988, 14772, 13332, 2612, 2396, 4052, 15516}, {8930, 3098, 14754, 14058, 8426, 1874, 13330, 14746}, {2398, 16230, 1894, 2606, 9198, 3350, 10614, 13566}, {1921, 9441, 2401, 12801, 18417, 13809, 2609, 3377}, {2374, 1190, 13806, 12558, 1918, 7254, 18390, 2366}, {2399, 13575, 1895, 17175, 15759, 4079, 2615, 16959}, {1892, 13572, 16932, 2372}, {8924, 1900, 16204, 3100, 7724, 10380, 13564, 7740}, {1927, 7751, 13807, 7983, 18391, 12567, 3103, 8927}, {8933, 13573, 16933, 8453, 1901, 16941, 3101, 14301}, {3366, 9158, 15502, 1902, 4062, 13558, 3126, 9182}, {9089, 18337, 13729, 9857, 10089, 3049, 12729, 1849}, {13702, 1606, 10062, 9614, 862, 6902, 12726, 18334}, {1591, 10791, 13703, 12735, 1615, 16175, 13463, 18335}, {13382, 1510, 16094, 18254, 12654, 13622, 10710, 1534}, {1537, 12897, 18281, 13625}, {13220, 13700, 18308, 13988, 1612, 12492, 8604, 1564}, {1609, 13705, 7145, 12969, 11801, 18361, 12249, 889}, {13624, 12168, 18280, 808, 11720, 12888, 7064, 1528}, {1768, 12648, 9008, 18256, 13648, 9776, 2968, 10008}, {18257, 1777, 15569, 10737, 13649, 3697, 16337, 12657}, {9251, 12195, 1771, 18283, 13651, 2995, 12891, 11963}, {2528, 13728, 18336, 3296, 1840, 9360, 2320, 12720}, {18310, 12486, 7902, 8846, 3022, 1846, 7670, 13726}, {18311, 3751, 15407, 14231, 12495, 1855, 8631, 13727}, {1831, 16391, 13487, 10575, 3775, 16151, 10551, 15647}, {13460, 1588, 16148, 10548}, {17109, 16877, 1589, 13469}, {17028, 1508, 16796, 13388}, {16866, 14690, 13466, 13226, 14922, 1586, 16850, 1562}, {16070, 10470, 15566, 3694, 1750, 16310, 13406, 10494}, {13409, 15809, 16097, 18497, 12681, 3721, 10713, 1753}, {3718, 18470, 1726, 13166, 8526, 13910, 12438, 15806}, {13415, 16799, 17031, 1751, 3695, 17039, 15575, 17055}, {16812, 3692, 13172, 15572, 14612, 17012, 14844, 1724}, {3772, 13964, 1804, 16364, 10332, 8364, 15644, 13244}, {18551, 13991, 12519, 8607, 15887, 1807, 3799, 13247}, {14693, 13253, 15653, 3773, 17093, 1805, 14925, 16893}, {13250, 3746, 1802, 14666, 14682, 15410, 14706, 14906}, {8388, 1828, 3748, 10308, 14204, 13484, 15404, 16124}, {14949, 1829, 3749, 16869, 16853, 15413, 13493, 14933}, {13478, 1830, 3774, 4014, 15662, 15638, 3990, 15422}, {1825, 12033, 3073, 10785, 16177, 13489, 9329, 12017}, {12006, 7142, 10782, 16174, 1582, 13462, 886, 11774}, {18567, 16903, 7151, 1583, 887, 17343, 12503, 13471}, {1502, 806, 12422, 13390, 17262, 18486, 16822, 7070}, {13228, 7148, 12476, 18324, 1556, 884, 15156, 14716}, {16096, 9248, 13408, 11936, 1744, 11952, 2992, 10704}, {13417, 9257, 12665, 18513, 1745, 2993, 17265, 16825}, {12638, 9254, 15078, 14638, 2990, 13174, 1718, 18270}, {13990, 1798, 9326, 11790, 3070, 11990, 8598, 13246}, {13255, 1799, 15159, 18351, 12719, 9335, 3071, 14719}, {10559, 9095, 3047, 16879, 17103, 16407, 13495, 1823}, {6908, 860, 16876, 1580, 16380, 10316, 17100, 13468}, {13414, 16326, 17022, 1742, 10478, 9014, 2966, 16798}, {14692, 9092, 13252, 1796, 16164, 3044, 10532, 14916}, {2534, 17094, 16878, 2318, 3998, 13494, 1814, 15678}, {14220, 3020, 16852, 8852, 13492, 8372, 16860, 1820}, {16390, 10566, 6926, 1102, 3766, 9590, 9822, 15646}, {1183, 10647, 3847, 9671, 9903, 15727, 16471, 7007}, {7004, 14284, 3820, 9644, 8460, 1180, 9660, 15484}, {11831, 11847, 14311, 8703, 7247, 3823, 1207, 15487}, {7013, 15493, 15013, 10373, 3821, 15021, 1181, 16221}, {15490, 1154, 3818, 14986, 14778, 14034, 6770, 8186}, {3844, 7716, 1156, 10404, 6764, 15724, 7484, 16444}, {18631, 1159, 6767, 12591, 3871, 7959, 7511, 15967}, {3845, 14277, 1157, 16965, 6773, 15733, 17173, 8213}, {15718, 3846, 3342, 8942, 6998, 4086, 1182, 15742}, {10065, 3793, 18577, 6929, 15889, 1105, 9617, 12753}, {3712, 9984, 18496, 15808, 6848, 1024, 9536, 12672}, {3715, 15811, 1051, 12171, 11723, 7091, 12915, 18523}, {7878, 7430, 15886, 3790, 18550, 1078, 12510, 6686}, {15649, 7169, 16417, 11777, 12009, 1129, 10809, 3769}, {3688, 10728, 15568, 7088, 16336, 11696, 11928, 1048}, {15577, 17065, 3689, 12425, 17289, 7097, 1049, 18489}, {1126, 11750, 3742, 15406, 8622, 11766, 14230, 7166}, {12479, 7175, 1127, 14959, 15183, 15415, 18327, 3743}, {15655, 17127, 3767, 1103, 10319, 6935, 16383, 17119}, {6854, 3686, 17038, 16302, 15574, 10238, 17046, 1022}, {16140, 1100, 6932, 15412, 14932, 10292, 3740, 14940}, {17092, 6692, 15652, 8132, 14196, 3764, 1076, 16884}, {10488, 15592, 9768, 9032, 3208, 9752, 16312, 3928}, {18499, 12675, 9035, 3211, 3955, 9779, 15835, 10011}, {18498, 9282, 2474, 3946, 12666, 2482, 3218, 15834}, {15832, 18472, 7592, 3952, 7824, 3184, 12432, 8792}, {12441, 8553, 18473, 3913, 15833, 14153, 3961, 15353}, {3937, 16313, 15593, 10497}, {3910, 15590, 14126, 10254, 16286, 15350, 8310, 3934}, {14871, 14855, 3911, 16815, 15599, 3935, 17015, 15359}, {14828, 15356, 3908, 14628}, {3931, 3235, 11939, 15595, 10731, 11955, 16339, 9275}, {3904, 11712, 3232, 8544, 15352, 14152, 11912, 9272}, {9281, 3905, 14881, 15361, 18273, 3233, 12641, 15105}, {16329, 3209, 9041, 17041, 15601, 10481, 17049, 3929}, {14854, 3206, 9038, 14862, 3902, 16086, 10454, 15358}, {3920, 15600, 17040, 2480}, {8294, 16806, 8798, 15598, 3182, 17014, 3926, 14142}, {9606, 15430, 3982, 9806, 9110, 3286, 8382, 14206}, {9687, 9191, 3367, 14287, 9887, 8463, 15511, 4063}, {2630, 8454, 14286, 2638, 15510, 4054, 3326, 8958}, {15519, 15015, 2639, 4055}, {7500, 3340, 8220, 15508, 14260, 8948, 7700, 4060}, {14061, 14989, 3341, 4061, 8429, 15517, 8957, 14781}, {15431, 8391, 4015, 3991, 16367, 15671, 10335, 14207}, {14180, 8148, 3988, 15428}, {14709, 14909, 15437, 3989}, {9353, 15433, 3985, 11793, 3313, 11993, 8625, 14233}, {16167, 10535, 14943, 15439, 3983, 14935, 3287, 9119}, {2558, 14934, 15438, 3974}, {8876, 3980, 15436, 14700, 8348, 3260, 13980, 14908}, {4000, 9120, 2560, 10560, 16392, 2552, 3272, 15672}, {3353, 2633, 15753, 4081, 9201, 2641, 10641, 16473}, {7014, 15750, 4078, 1166, 2390, 2614, 10398, 16446}, {7257, 4105, 18633, 1193, 12585, 2617, 15993, 2393}, {4080, 2640, 2624, 15744}, {2563, 3299, 15915, 12747, 9363, 18579, 2555, 4027}, {2312, 15912, 7176, 2536, 4024, 1112, 18552, 12504}, {15681, 4001, 17121, 2561}, {7646, 8870, 4006, 16366, 7662, 15670, 10326, 3262}, {15751, 10407, 7743, 3343, 7727, 4087, 8951, 16447}, {4033, 7905, 3265, 12513, 8873, 15913, 7673, 18553}, {3263, 16887, 17095, 4007, 14223, 8879, 8375, 15679}, {4008, 15664, 9104, 3288}, {4089, 15745, 9185, 3369}, {4017, 15665}, {3361, 9913, 9921, 9193}, {9670, 9894, 9918, 9166, 3118, 1174, 9910, 7006}, {11857, 1201, 10161, 9169, 7249, 3121, 9937, 12081}, {9694, 6982, 934, 11854, 12078, 7222, 10134, 958}, {12321, 961, 11881, 7225}, {12583, 935, 10423, 6991, 18639, 16695, 959, 7231}, {18396, 14508, 12556, 7228, 908, 8236, 956, 6748}, {2392, 1192, 12072, 2608, 11856, 7248, 3376, 9432}, {7974, 7750, 11838, 7246, 1198, 11830, 3094, 8926}, {14535, 8935, 12559, 1199, 3095, 7255, 18399, 8479}, {7009, 9409, 9697, 12097, 12105, 3145, 1177, 10137}, {3142, 12070, 6766, 7950, 11862, 7510, 1150, 9406}, {9415, 3143, 12799, 8239, 14511, 18423, 6775, 1151}, {7015, 16455, 3119, 10639, 9175, 1175, 16479, 10399}, {10396, 932, 16452, 6988}, {14268, 16236, 3116, 9172, 8212, 6772, 10612, 1148}, {7012, 10372, 8932, 8452, 14292, 1172, 3092, 16212}, {2632, 9192, 9912, 3352}, {3379, 12099, 2635, 9435}, {3334, 9190, 9886, 7726, 9678, 8950, 7734, 3358}, {9433, 3385, 3337, 7753, 12073, 7977, 8953, 11865}, {3359, 8455, 3335, 16239, 9199, 14295, 10615, 8959}, {14052, 8428, 3332, 8956}, {3360, 9184}, {10083, 9859, 3307, 9355, 12019, 3283, 9115, 12027}, {1120, 11776, 7168, 10080, 9088, 3040, 9856, 12000}, {1123, 7171, 3067, 12267, 12043, 9331, 12243, 11803}, {880, 11800, 12240, 7144}, {18801, 881, 7153, 12529}, {800, 18720, 12448, 7072}, {9250, 12162, 11722, 2986, 7090, 1042, 11962, 12186}, {12451, 18723, 7099, 9259, 2987, 1043, 12691, 18747}, {1121, 16641, 3041, 18561, 10585, 9097, 7177, 12505}, {16614, 10342, 7150, 878, 12502, 854, 18558, 6910}, {12424, 10504, 1040, 16560, 2960, 18480, 7096, 9016}, {7174, 3014, 8398, 18318, 14454, 8854, 1118, 12478}, {10056, 1096, 6928, 12016, 9328, 9616, 12024, 3064}, {9337, 18585, 12745, 16617, 1097, 10345, 6937, 3065}, {2984, 9256, 6856, 10264, 18504, 12664, 1016, 16536}, {6694, 18342, 12718, 1070, 8158, 9334, 3062, 14430}, {11938, 3202, 9274, 9034, 11946, 10002, 9778, 3226}, {9277, 3229, 12189, 11965}, {9283, 3203, 10507, 18507, 9043, 12667, 16563, 3227}, {12640, 9280, 8800, 8320, 14376, 3176, 18264, 3224}, {3298, 2554, 12018, 9354}, {3304, 9352, 8872, 7672, 11784, 7896, 11992, 3256}, {3257, 3305, 18345, 9361, 8881, 12721, 8401, 14457}, {10561, 3281, 9121, 16401}, {10558, 9094, 1094, 10318, 16398, 6934, 16374, 3038}, {3200, 10480, 9040, 16320}, {10534, 14214, 8878, 16158, 3278, 8374, 3254, 9118}, {9814, 9838, 9598, 7654}, {9815, 9607, 14215, 9839, 10543, 16159, 9847, 8383}, {9604, 8356, 13972, 9812}, {14917, 16165, 8357, 13981, 9605, 14701, 10541, 9821}, {9740, 13900, 10460, 14836, 16084, 8276, 9524, 14620}, {15079, 12647, 13903, 9551, 9983, 8279, 14647, 18271}, {10469, 14837, 14629, 16085}, {14839, 8519, 13927, 11711, 16111, 10703, 11927, 14623}, {17021, 16813, 16301, 13901, 10253, 8285, 14621, 14845}, {8354, 14674, 9578, 13978}, {14059, 14755, 9659, 8435}, {14752, 8192, 7472, 14032}, {14915, 10307, 16139, 8363, 14675, 14707, 14683, 13979}, {14680, 14672, 13952, 8120}, {14681}, {11765, 14677, 8597, 14005}, {14914, 13954, 10298, 14698, 16138, 8114, 7634, 7418}, {8195, 7715, 7499, 10379, 14995, 14035, 14779, 16219}, {7877, 14725, 13957, 12485, 15157, 18325, 8117, 7445}, {16867, 13955, 14923, 14699, 14195, 8147, 16859, 8123}, {9685, 8437, 14053, 9893}, {8194, 14050, 14026, 7498, 9650, 8434, 7706, 9658}, {8677, 8197, 7525, 11845, 14077, 14029, 7949, 11837}, {8359, 10055, 13975, 11791, 13999, 11999, 8599, 9631}, {8518, 13894, 13918, 9550, 11918, 9974, 8278, 11710}, {8521, 13921, 12161, 11737}, {13895, 10279, 13919, 8527, 18479, 16535, 12439, 8287}, {13948, 13996, 11756, 11764, 8596, 8116, 7444, 7868}, {13949, 12493, 13997, 8125, 8173, 18317, 14429, 8605}, {16373, 10333, 13973, 8365}, {16292, 13892, 10252, 8284}, {8122, 16130, 10306, 8362, 14186, 8146, 13970, 13946}, {9766, 9758, 9734, 8302, 16078, 9526, 14134, 10462}, {10463, 16087, 9767, 14863}, {14377, 12649, 8329, 9737, 9785, 10009, 18265, 9529}, {7550, 9542, 12646, 7342, 14350, 8086, 18262, 9982}, {7369, 12169, 14353, 11729, 18289, 7793, 12889, 8089}, {10711, 8071, 16103, 12655, 14351, 14111, 18263, 8095}, {11713, 10465, 8545, 9793, 14161, 10001, 16081, 11921}, {16807, 16327, 8303, 9743, 14143, 10487, 9527, 17023}, {14116, 10244, 16804, 7556, 8060, 7340, 16300, 17020}, {7367, 14119, 16831, 7799, 12431, 17263, 18487, 8063}, {8069, 14117, 17029, 16805}, {11945, 16105, 9553, 10705, 8305, 11953, 9977, 14137}, {7366, 16102, 10702, 14110, 7790, 11702, 11926, 8062}, {10495, 10471, 16295, 14135, 10255, 16079, 8311, 16319}, {8068, 16076, 14108, 10468}, {16156, 8140, 14188, 10540, 7628, 7420, 9596, 9820}, {12727, 8167, 18343, 10063, 7631, 9623, 14431, 7423}, {8164, 7396, 12484, 7876, 7436, 18316, 7388, 14428}, {14509, 7469, 18397, 8245, 12565, 7477, 7957, 7517}, {7709, 9677, 7501, 14269, 16237, 9901, 10621, 8221}, {7490, 8218, 7714, 10378, 7466, 7474, 16210, 14266}, {8219, 16939, 14275, 7475}, {17101, 8141, 16381, 10325, 14197, 16885, 7637, 7421}, {16858, 14194, 7394, 8138}, {11783, 12007, 16183, 8143, 14191, 7871, 7447, 10783}, {8149, 16157, 10549, 14189}, {14212, 7652, 16132, 9572, 9580, 7660, 10300, 8380}, {7661, 16141, 10301, 14941}, {14455, 12487, 9575, 9583, 18319, 7903, 8407, 7679}, {7741, 8461, 10381, 7733, 14293, 16213, 9653, 9661}, {11767, 16135, 7687, 8623, 11759, 7895, 14239, 10303}, {16861, 9581, 14221, 8381}, {8389, 16133, 10309, 14213}, {9601, 12001, 7681, 10081, 9865, 11785, 9817, 7897}, {11704, 7816, 9736, 9520, 11920, 7600, 10000, 9784}, {10027, 7843, 11923, 11707}, {7825, 7601, 9521, 10513, 18481, 12433, 16561, 9745}, {7334, 7558, 18478, 12430, 7798, 10270, 16534, 7358}, {7801, 12457, 7361, 18721}, {12163, 11971, 9547, 7819, 7603, 11731, 12187, 9979}, {7792, 7360, 12160, 11728}, {7817, 10249, 7609, 11705, 10729, 16297, 11929, 16345}, {11782, 10054, 7870, 7438, 7630, 9622, 7414, 11998}, {9703, 7495, 7711, 12079, 7951, 10135, 11863, 7519}, {7948, 7468, 11836, 7516}, {12511, 7639, 7879, 16615, 10351, 7439, 7415, 18559}, {7873, 12241, 7441, 11809}, {11758, 9574, 7894, 7678}, {9655, 11839, 7759, 7975}, {7921, 11761}, {9895, 9679, 9919, 7735}, {9892, 9676, 7492, 7708}, {7717, 16453, 7493, 10405}, {9652, 7732}, {7655, 10567, 9823, 7663, 16399, 10327, 16375, 9599}, {16294, 10246, 9518, 9742, 16318, 10486, 7574, 7582}, {7585, 12673, 10273, 9985, 9545, 7577, 18505, 16537}, {17047, 16303, 10247, 7583}, {7412, 7636, 16372, 10324}, {10057, 7657, 9625, 12025}, {7576, 9976, 9544, 11944}, {9760}, {16321, 9769, 10489, 9761}, {10003, 9787, 11947, 9763}]

	def __init__(
			self,
			action_dim,
			state_dim,
			learning_rate = 3e-4,
			gamma = 0.9 ):
		super(Qtable, self).__init__()

		self.action_dim = action_dim
		self.state_dim = state_dim
		self.lr = learning_rate
		self.gamma = gamma

		# dim of Q-table = 627 * 9
		self.Qtable = np.zeros((627 + 4, action_dim))

		self.replay_buffer = ReplayBuffer(int(1e5))	# originally 1e6

	# convert state-vector into a base-3 number
	def state_num(state):
		if 2 in state:
			return Qtable.ILLEGAL
		s = (((((((					\
			state[0] * 3 + 3 +		\
			state[1]) * 3 + 3 +		\
			state[2]) * 3 + 3 +		\
			state[3]) * 3 + 3 +		\
			state[4]) * 3 + 3 +		\
			state[5]) * 3 + 3 +		\
			state[6]) * 3 + 3 +		\
			state[7]) * 3 + 3 +		\
			state[8]+1
		return s

	def findClass(n):
		j = -1
		# print("len =", len(Qtable.eqClasses))
		for (i,cls) in enumerate(Qtable.eqClasses):
			if n in cls:
				j = i
				break
		assert j != -1, "board state " + str(n) + " not found in equivalence classes"
		return j

	def choose_action(self, state, deterministic=False):
		s = Qtable.state_num(state)
		j = Qtable.findClass(s)
		logits  = self.Qtable[j, :] 		# = Q(s,a)
		probs   = np.exp(logits) / np.exp(logits).sum(axis=0)	# softmax
		# print("logits, probs =", logits, probs)
		action  = np.random.choice([0,1,2,3,4,5,6,7,8], 1, p=probs)[0]
		# action = np.argmax(logits)		# deterministic
		# print("chosen action=", action)
		return action

	def show_board(board):
		for i in [0, 3, 6]:
			for j in range(3):
				x = board[i + j]
				if x == -1:
					c = '❌'
				elif x == 1:
					c = '⭕'
				elif x == 2:
					c = '🟨'
				else:
					c = '  '
				print(c, end='')
			print(end='\n')

	def update(self, batch_size, reward_scale, gamma=0.99):
		alpha = 1.0  # trade-off between exploration (max entropy) and exploitation (max Q)

		states, actions, rewards, next_states, dones = self.replay_buffer.sample(batch_size)
		# print('sample (state, action, reward, next state, done):', states, actions, rewards, next_states, dones)

		# convert state-vector to a base-3 number
		s = (((((((					\
			states[:,0] * 3 + 3 +	\
			states[:,1]) * 3 + 3 +	\
			states[:,2]) * 3 + 3 +	\
			states[:,3]) * 3 + 3 +	\
			states[:,4]) * 3 + 3 +	\
			states[:,5]) * 3 + 3 +	\
			states[:,6]) * 3 + 3 +	\
			states[:,7]) * 3 + 3 +	\
			states[:,8] + 1
		j = list(map(Qtable.findClass, s))

		# for st in next_states:
		#	Qtable.show_board(st)
		#	print('---------------')
		# print("next states =", next_states.shape, next_states)
		k = np.array(list(map(Qtable.findClass, list(map(Qtable.state_num, next_states)))))

		# **** Train Q function, this is just Bellman equation:
		# Q(st,at) += η [ R + γ max_a Q(s_t+1,a) - Q(st,at) ]
		self.Qtable[j, actions] += self.lr *( rewards + self.gamma * np.max(self.Qtable[k, :]) - self.Qtable[j, actions] )
		return

	def visualize_q(self, board):
		# convert board vector to a base-3 number
		s = (((((((					\
			board[0] * 3 + 3 +	\
			board[1]) * 3 + 3 +	\
			board[2]) * 3 + 3 +	\
			board[3]) * 3 + 3 +	\
			board[4]) * 3 + 3 +	\
			board[5]) * 3 + 3 +	\
			board[6]) * 3 + 3 +	\
			board[7]) * 3 + 3 +	\
			board[8] + 1
		j = Qtable.findClass(s)
		logits = self.Qtable[j, :]
		probs  = np.exp(logits) / np.exp(logits).sum(axis=0)	# softmax
		return probs
	
	def net_info(self):
		config = "(627x9)"
		return (config, 627*9)

	def play_random(self, state, action_space):
		# Select an action (0-9) randomly
		# NOTE: random player never chooses occupied squares
		empties = [0,1,2,3,4,5,6,7,8]
		# Find and collect all empty squares
		# scan through board vector
		for i in range(0, 9):
			# 'proposition' is a numpy array[3]
			if state[i] == 1 or state[i] == -1:
				empties.remove(i)
		# Select an available square randomly
		action = random.sample(empties, 1)[0]
		return action

	def save_net(self, fname):
		np.save(fname, self.Qtable)
		print("Q-table saved.")

	def load_net(self, fname):
		self.Qtable = np.load(fname)
		print("Q-table loaded.")