search.cc

Revision 169, 29.4 kB (checked in by ug, 3 years ago)
Misc. changes

Line
1	// File: search.cc
2
3	// Copyright (C) 2001-4 Ulrich Goertz (u@g0ertz.de)
4
5	// This file is part of Kombilo 0.6, a go database program.
6
7	// This program is free software; you can redistribute it and/or modify
8	// it under the terms of the GNU General Public License as published by
9	// the Free Software Foundation; either version 2 of the License, or
10	// (at your option) any later version.
11
12	// This program is distributed in the hope that it will be useful,
13	// but WITHOUT ANY WARRANTY; without even the implied warranty of
14	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15	// GNU General Public License for more details.
16
17	// You should have received a copy of the GNU General Public License
18	// along with this program (see doc/license.txt); if not, write to the Free Software
19	// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20	// The GNU GPL is also currently available at
21	// http://www.gnu.org/copyleft/gpl.html
22
23	// --------------------------------------------------------------------------
24
25
26	SGFDatabase::SGFDatabase(int bs, PyObject* pBar) {
27	boardsize = bs;
28	progBar = pBar;
29
30	datap1 = "";
31	datap2 = 0;
32	sgfpath = "";
33	disabled = 1;
34	algos = 1;
35	}
36
37
38	void SGFDatabase::clear() {
39	namelist.clear();
40	current.clear();
41	results.clear();
42	}
43
44
45	pair<char, int> SGFDatabase::getFilename(int* index) {
46	int gameNumber;
47	s = self.namelist[index][0];
48	if (find(s, '[') != -1) {
49	s, s2 = split(s, '[');
50	gameNumber = int(strip(s2)[:-1]);
51	}
52	else gameNumber = 0;
53
54	if (s[-1] == '.') filename = s[:-1];
55	else if (s[-2:] == '.m') filename = s + 'gt';
56	else filename = s + '.sgf';
57
58	XXX return strip(os.path.join(self.sgfpath, filename)), gameNumber;
59	}
60
61
62	void SGFDatabase::process(char* dbpath, pair<char, int> datap, int* Algos, PyObject* flist,
63	PyObject* messages, PyObject gamelist,
64	int sloppySGF, int duplicateCheck,
65	int strictDuplicateCheck, int processVariations) {
66
67	int currentTime = time(0);
68	if (progBar) progBar.clear();
69	XXX messages.insert('end', 'Processing ' + dbpath + ' ...\n');
70
71	vector<Algorithm> algolist;
72	algos \|= 1; // add Algo_finalpos
73	for(int i = 0; i < NUM_OF_ALGOS; i++)
74	if (algos & ALGOS[i])
75	algolist.push_back(ALL_ALGOS[i](boardsize));
76
77	vector<char*> Namelist;
78	Namelist.push_back("kombilo06");
79	Namelist.push_back(itao(algos));
80
81	vector<char*> siglist;
82
83	int oa = (int) 'a';
84
85	vector<char*> filelist;
86	XXX // ... build filelist from flist
87	filelist.sort();
88
89	for(algo in algolist)
90	algo.initialize_process(filelist.size());
91
92	int total = filelist.size();
93	int gameCtr = 0; // counts games which are added to the new database
94	int fileCtr = 0; // counts files which are processed
95
96	XXX for(f in filelist) {
97	XXX if (progBar && fileCtr % 10 == 0)
98	XXX progBar.redraw(fileCtr*1.0/total);
99	fileCtr++;
100
101	// if self.stopAddDBVar.get() == 1: // FIXME?!
102	// showinfo('Stop processing', 'Processing will be stopped after this database has been finished.\n')
103	// self.stopAddDBVar.set(2)
104
105	if (find(f, '\|%') != -1 \|\| find(f, '[') != -1) {
106	XXX messages.insert('end', 'Invalid characters in filename ' + f + ', skipped.\n');
107	continue;
108	}
109
110	try {
111	XXX file = open(f);
112	XXX s = file.read();
113	XXX file.close();
114	}
115	catch(IOError) {
116	XXX messages.insert('end', 'I/O Error: Cannot read file ' + f + ', skipped.\n');
117	continue;
118	}
119
120	try {
121	cursor = Cursor(s, sloppySGF);
122	}
123	catch {
124	XXX messages.insert('end', 'Error in SGF file '+f+': Skipped.\n');
125	continue;
126	}
127
128	int collection = 0;
129	if (cursor.root.numChildren > 1) {
130	collection = 1;
131	XXX messages.insert('end', 'Warning: ' + f + ' is a collection;' +\
132	XXX ' for performance reasons it would be better to' + \
133	XXX ' split it into files with single game records.\n');
134	}
135	if (!cursor.root.numChildren) {
136	XXX messages.insert('end', 'File '+f+' does not contain a game record. Skipped.\n');
137	continue;
138	}
139
140	for(int indexColl=0; indexColl < cursor.root.numChildren; indexColl++) {
141	char* iColl;
142	XXX if (collection) iColl = '[' + `indexColl` + ']';
143	XXX else iColl = '';
144
145	try
146	XXX cursor.game(indexColl);
147	XXX catch SGFError {
148	XXX messages.insert('end', 'SGF Error in game ' + iColl + ' of file ' + f + ', skipped.\n');
149	continue;
150	}
151
152	try {
153	if (cursor.currentNode().has_key('SZ') && strip(cursor.currentNode()['SZ'][0]) != `self.boardsize`)
154	messages.insert('end', 'SGF file '+ f + iColl +\
155	' does not contain a %sx%s game. Skipped.\n' \
156	% (`self.boardsize`, `self.boardsize`));
157	continue;
158
159	char playerB[];
160	char playerW[];
161	char result;
162	char date[11];
163
164	if (cursor.currentNode().has_key('PB')) {
165	playerB = replace(cursor.currentNode()['PB'][0], '\|%', ' ');
166	playerB = replace(playerB, '\r', ' ');
167	playerB = replace(playerB, '\n', ' ');
168	}
169	else playerB = '?';
170
171	if (cursor.currentNode().has_key('PW')) {
172	playerW = replace(cursor.currentNode()['PW'][0], '\|%', ' ');
173	playerW = replace(playerW, '\r', ' ');
174	playerW = replace(playerW, '\n', ' ');
175	}
176	else playerW = '?';
177
178	if (cursor.currentNode().has_key('RE') && strip(cursor.currentNode()['RE'][0]))
179	result = strip(cursor.currentNode()['RE'][0])[0];
180	else result = '-';
181
182	if (cursor.currentNode().has_key('DT') && cursor.currentNode()['DT'][0]) {
183	date_str = cursor.currentNode()['DT'][0];
184
185	m = re.search('(^\|[^\d])(\d\d\d\d-\d\d-\d\d)($\|[^\d])', date_str);
186
187	try
188	date = m.group(2);
189	catch (AttributeError, ValueError) {
190	m = re.search('(^\|[^\d])(\d\d\d\d-\d\d)($\|[^\d])', date_str);
191	try
192	date = m.group(2);
193	catch (AttributeError, ValueError) {
194	m = re.search('(^\|[^\d])(\d\d\d\d)($\|[^\d])', date_str);
195	try
196	date = m.group(2);
197	catch (AttributeError, ValueError)
198	date = '';
199	// else FIXME
200	// date = ''
201	}
202	}
203	}
204
205	char signature1[];
206	char signature2[];
207	}
208	catch {
209	messages.insert('end', 'SGF Error in root node of game ' + iColl + \
210	', file ' + f + ', skipped.\n');
211	continue;
212	}
213
214	int counter = -1;
215
216	try {
217
218	for(algo in algolist) algo.newgame_process();
219
220	b = abstractBoard();
221	vector<> branchpoints;
222
223	while(1) {
224	counter++;
225
226	try {
227	if (cursor.currentNode().has_key('B') \|\| cursor.currentNode().has_key('W')) {
228	if (cursor.currentNode().has_key('B')) co = 'B';
229	else co = 'W';
230
231	char* p = cursor.currentNode()[co][0];
232	if (strlen(p) != 2)
233	if (!strlen(p)) {
234	messages.insert('end', 'SGF Error in file ' + f + '\n');
235	break;
236	}
237	assert len(p) == 2;
238
239	int x = p[0] - oa;
240	int y = p[1] - oa;
241
242	if (0 <= x && x < self.boardsize && 0 <= y && y < self.boardsize) {
243	if (!b.play((x, y), co)) {
244	messages.insert('end', 'Illegal move in file ' + f \
245	+ ' (' + `counter+1` + ')\n');
246	break;
247	}
248	}
249	else
250	if (x != 19 \|\| y != 19) {
251	messages.insert('end', 'Invalid move in file '+f+
252	' (' + `counter+1` + ')\n');
253	break;
254	}
255
256	assert 0 <= x < self.boardsize and 0 <= y < self.boardsize;
257
258	if (b.undostack.size())
259	captures = b.undostack[len(b.undostack)-1][2];
260	else assert 0; // FIXME?
261
262	if (counter+1 in [20, 40, 60]) signature1 = signature1 + chr(x + oa) + chr(y + oa);
263	if (counter+1 in [31, 51, 71]) signature2 = signature2 + chr(x + oa) + chr(y + oa);
264
265	for(algo in algolist)
266	if (co == 'B') algo.B_process(x, y, captures);
267	else algo.W_process(x, y, captures);
268	}
269	else {
270	if (cursor.currentNode().has_key('AB'))
271	for (p in cursor.currentNode()['AB']) {
272	if (strlen(p) != 2) continue;
273	int x = ord(p[0])-oa;
274	int y = ord(p[1])-oa;
275	if (!(0 <= x && x < self.boardsize && 0 <= y && y < self.boardsize))
276	messages.insert('end', 'Invalid position in AE tag, in file ' + f + '\n');
277
278	assert 0 <= x < self.boardsize and 0 <= y < self.boardsize;
279	b.play((x, y), 'black');
280	for(algo in algolist) algo.AB_process(x, y);
281	}
282
283	if (cursor.currentNode().has_key('AW'))
284	for (p in cursor.currentNode()['AW']) {
285	if (strlen(p) != 2) continue;
286	int x = ord(p[0])-oa;
287	int y = ord(p[1])-oa;
288	if (!(0 <= x && x < self.boardsize && 0 <= y && y < self.boardsize))
289	messages.insert('end', 'Invalid position in AE tag, in file ' + f + '\n');
290
291	assert 0 <= x < self.boardsize and 0 <= y < self.boardsize;
292	b.play((x, y), 'white');
293	for (algo in algolist) algo.AW_process(x, y);
294	}
295
296	if (cursor.currentNode().has_key('AE'))
297	for(p in cursor.currentNode()['AE']) {
298	if (strlen(p) != 2) continue;
299	int x = ord(p[0])-oa;
300	int y = ord(p[1])-oa;
301	if (!(0 <= x && x < self.boardsize && 0 <= y && y < self.boardsize))
302	messages.insert('end', 'Invalid position in AE tag, in file ' + f + '\n');
303
304	assert 0 <= x < self.boardsize and 0 <= y < self.boardsize;
305	assert b.status.has_key((x,y));
306
307	if (b.status[(x,y)] == 'black') removed = 'B';
308	elif (b.status[(x,y)] == 'white') removed = 'W';
309	b.remove((x, y));
310	for(algo in algolist) algo.AE_process(x, y, removed);
311	}
312	}
313	}
314	catch AssertionError
315	pass;
316
317	for(algo in algolist) algo.endOfNode_process();
318
319	if (processVariations && cursor.noChildren() > 1) {
320	for (algo in algolist) algo.branchpoint_process();
321	self.branchpoints.append((cursor.currentN, b.copy(), 0));
322	}
323
324	if (!cursor.atEnd()) cursor.next();
325	else if (self.branchpoints) {
326	for (algo in algolist) algo.endOfVariation_process();
327
328	cursor.currentN, b, whichVar = self.branchpoints.pop();
329	if (whichVar+2 < cursor.noChildren()) {
330	for (algo in algolist) algo.branchpoint_process();
331	self.branchpoints.append((cursor.currentN, b.copy(), whichVar+1));
332	}
333	cursor.next(whichVar+1);
334	}
335	else break;
336	}
337	}
338
339	catch SGFError {
340	messages.insert('end', 'File ' + f +iColl + ': SGF error in node ' + `counter+3` + '.\n');
341	}
342	catch (*) {
343	messages.insert('end', 'File ' + f + iColl + ': Error in node ' + `counter+3` + '.\n');
344	}
345
346	try {
347	XXX while (strlen(signature1) < 6) signature1 += "??";
348	XXX while (strlen(signature2) < 6) signature2 += "??";
349	XXX signature = signature1 + signature2;
350	signature = symmetrizeSig(signature);
351
352	// if (duplicateCheck && (counter > 20 \|\| (counter > 5 && strictDuplicateCheck))) {
353	// duplist = [];
354	// for (sli in range(len(siglist)))
355	// if (siglist[sli] == signature &&
356	// (not strictDuplicateCheck \|\| algolist[0].duplicateCheck(sli)))
357	// duplist.append(split(Namelist[sli], '\|%')[0]);
358	//
359	// if (gamelist) { // FIXME
360	// for (db in gamelist.DBlist[bsize]) {
361	// if (db.disabled) continue;
362	// for (i in range(len(db.namelist))) {
363	// g = db.namelist[i];
364	// if (signature == g[4])
365	// if (!strictDuplicateCheck)
366	// duplist.append(os.path.join(db.sgfpath, g[0]));
367	// else
368	// if (algolist[0].duplicateCheck(i, db.datapath))
369	// duplist.append(os.path.join(db.sgfpath, g[0]));
370	// }
371	// }
372	// }
373	//
374	// if (strictDuplicateCheck)
375	// char dupText = " is the same as ";*
376	// else
377	// char dupText = " is probably the same as "; // do we have to delete this? FIXME*
378	//
379	// if (duplist.size()) {
380	// ff = join(duplist, ', ');
381	// if (duplicateCheck == 1)
382	// messages.insert('end', 'Duplicate: ' + os.path.split(f)[1] +iColl+ dupText + ff + '.\n');
383	// else if (duplicateCheck == 3) {
384	// messages.insert('end', 'Duplicate: '+os.path.split(f)[1]+iColl+\
385	// dupText + ff + ', omitted.\n');
386	// continue;
387	// }
388	// else if (duplicateCheck == 2) {
389	// if (askyesno('Duplicate', 'File ' +os.path.split(f)[1]+iColl\
390	// + ' is the same as ' + ff + '. Include it?'))
391	// messages.insert('end', 'Duplicate: ' + os.path.split(f)[1]+iColl\
392	// + dupText + ff + '\n');
393	// else {
394	// messages.insert('end', 'Duplicate: ' + os.path.split(f)[1]\
395	// + dupText + ff + ', omitted.\n');
396	// continue;
397	// }
398	// }
399	// }
400	// }
401
402	siglist.append(signature);
403	}
404
405	XXX catch (*) {
406	XXX messages.insert('end', 'File ' + f +iColl + ': Error computing the Dyer signature.\n');
407	signature = "????????????";
408	}
409
410	for (algo in algolist) algo.endgame_process();
411
412	if (os.path.split(f)[1][-4:] == '.sgf') filenameDB = os.path.split(f)[1][:-4];
413	else if (os.path.split(f)[1][-4:] == '.mgt') filenameDB = os.path.split(f)[1][:-2];
414	else filenameDB = os.path.split(f)[1] + '.';
415
416	Namelist.append(filenameDB + iColl + '\|%' + playerB + '\|%' + playerW + '\|%' \
417	+ result + '\|%' + signature + '\|%' + date);
418
419	gameCtr++;
420	}
421	}
422
423	if (gameCtr) {
424	try {
425	for (algo in algolist) algo.finalize_process(datap);
426	}
427	catch IOError {
428	messages.insert("end", "I/O Error: Could not write database files (Directory write-protected?).\n");
429	return;
430	}
431
432	try {
433	XXX file = open(os.path.join(datap[0], "namelist" + datap[1] + ".db"), "w");
434	XXX for (s in Namelist)
435	XXX file.write(s+'\n');
436	XXX file.close();
437	}
438	catch IOError
439	XXX messages.insert('end', 'I/O Error: Could not write namelist.db file.\n');
440
441	// if (progBar) {
442	// progBar.redraw(1);
443	// progBar.write('%1.1f seconds' % (time.time() - currentTime));
444	// }
445
446	XXX messages.insert('end', '%1.1f seconds' % (time.time() - currentTime));
447	XXX messages.insert('end', '... finished.\n');
448
449	datapath = datap;
450	sgfpath = dbpath;
451	algos = Algos;
452	XXX namelist = [split(x[:-1], '\|%') for x in Namelist[2:]];
453	disabled = 0;
454	XXX current = array('L', range(len(namelist)-2));
455	results = [];
456	}
457	}
458
459
460	int SGFDatabase::validNamelist(vector<> namelist) {
461	if (namelist[0][:-1]=='kombilo06' && typeof(namelist[1][:-1]) == int &&
462	filename, PB, PW, res, sig, date = split(namelist[2][:-1], '\|%')) FIXME
463	return 1;
464	else return 0;
465	}
466
467
468	void SGFDatabase::loadDB(char* sgfpth, char* datapth aufpassen (eigtl tupel?), int disabled) {
469
470	if not datapath is None: self.datapath = datapath
471	if not sgfpath is None: self.sgfpath = sgfpath
472
473	self.namelist= []
474	self.disabled = disabled
475
476	try:
477	file = open(os.path.join(self.datapath[0], 'namelist' + self.datapath[1] + '.db'))
478	namelist = file.readlines()
479	file.close()
480	except:
481	return -2
482
483	try:
484	assert self.validNamelist(namelist)
485	algos = int(namelist[1][:-1])
486	except:
487	return -1
488
489	try:
490	self.namelist = [split(x[:-1], '\|%') for x in namelist[2:]]
491	if not disabled:
492	self.current = array('L', range(len(namelist)-2))
493	self.results = []
494	else:
495	self.current = array('L')
496	self.results = []
497	self.algos = algos
498	except: return -3
499
500	return 1
501	}
502
503
504	int SGFDatabase::start() {
505
506	if len(self.current) and not self.disabled:
507	self.currentIndexWithinCurrent = 0
508	self.newCurrent = array('L')
509	try: self.oldMatchlists = self.matchlists
510	except AttributeError: pass
511	self.matchlists = []
512	self.results = []
513	return self.current[0]
514	}
515
516	int SGFDatabase::next() {
517	self.currentIndexWithinCurrent += 1
518	if self.currentIndexWithinCurrent >= len(self.current):
519	self.current = self.newCurrent
520	return None
521
522	return self.current[self.currentIndexWithinCurrent]
523	}
524
525
526	void SGFDatabase::makeCurrentCandidate(matchList) {
527	self.newCurrent.append(self.current[self.currentIndexWithinCurrent])
528	self.matchlists.append(matchList)
529	}
530
531	void SGFDatabase::makeCurrentHit(results) {
532	win = self.getCurrentWinner()
533	self.newCurrent.append(self.current[self.currentIndexWithinCurrent])
534	self.results.append(results)
535	}
536
537	void SGFDatabase::discardCurrent() {
538	}
539
540
541	SGFDatabase::getCurrentMatchlist() {
542	try: return self.oldMatchlists[self.currentIndexWithinCurrent]
543	except: return []
544	}
545
546	SGFDatabase::getCurrentWinner() {
547	currentWithinDB = self.current[self.currentIndexWithinCurrent]
548	return self.namelist[currentWithinDB][3]
549	}
550
551
552	// -------------- class hashTable ------------------------------------------------
553
554
555	hashTable(int noOfGames, char* filename) {
556	self.data = array('l', [0](2130*noOfGames))
557	self.currentCtr = -1
558	self.dataIndex = 0
559	self.filename = filename
560	}
561
562	void hashtable::newCtr(ctr) {
563	if ctr == self.currentCtr:
564	while self.dataIndex > 0 and self.data[self.dataIndex-1] == ctr:
565	self.dataIndex -= 2
566	self.currentCtr = ctr
567	self.currentCtrL = []
568	}
569
570	void hashTable::append(int i) {
571
572	ctr = self.currentCtr
573
574	if i not in self.currentCtrL:
575	if self.dataIndex >= len(self.data)-1:
576	self.data.extend(array('l', [0]*1000))
577	self.data[self.dataIndex] = i
578	self.dataIndex += 1
579	self.data[self.dataIndex] = ctr
580	self.dataIndex += 1
581	self.currentCtrL.append(i)
582	}
583
584
585	void hashTable::swap(int l, int r) {
586	help1 = self.data[2*l]
587	help2 = self.data[2*l+1]
588	self.data[2l] = self.data[2r]
589	self.data[2l+1] = self.data[2r+1]
590	self.data[2*r] = help1
591	self.data[2*r+1] = help2
592	}
593
594
595	void hashTable::sort() {
596
597	l = 0
598	r = self.dataIndex/2 - 1
599	stack = [(l, r)]
600
601	while stack:
602	if r > l:
603	if r-l == 1:
604	if self.data[2l] > self.data[2r]:
605	self.swap(l,r)
606	l, r = stack.pop()
607	else:
608	li = [(self.data[2l], l), (self.data[2r], r), (self.data[2*((r+l)/2)], (r+l)/2)]
609	li.sort()
610
611	self.swap(li[1][1], r)
612	help1 = self.data[2*r]
613
614	left = l
615	right = r-1
616
617	while 1:
618	while self.data[2*left] < help1: left += 1
619	while self.data[2*right] > help1: right -= 1
620
621	if right <= left: break
622
623	self.swap(left, right)
624
625	left += 1
626	right -= 1
627
628	self.swap(left, r)
629
630	if left-l > r-left:
631	stack.append((l, left-1))
632	l = left+1
633	else:
634	stack.append((left+1, r))
635	r = left-1
636	else:
637	l, r = stack.pop()
638	}
639
640
641	hashTable::sortedOutput(char* path) {
642	self.sort()
643
644	dataX = array('l')
645	data1X = array('B')
646
647	currentCode = self.data[0] - 1
648	currentValues = []
649
650	for i in xrange(self.dataIndex/2):
651	if self.data[2*i] != currentCode:
652	currentValues.sort()
653	for v in currentValues:
654	data1X.append(v/256)
655	data1X.append(v%256)
656	currentValues = []
657	currentCode = self.data[2*i]
658	dataX.append(currentCode)
659	dataX.append(len(data1X))
660
661	currentValues.append(self.data[2*i+1])
662
663	currentValues.sort()
664	for v in currentValues:
665	data1X.append(v/256)
666	data1X.append(v%256)
667
668	file = open(os.path.join(path[0], self.filename + 'T' + path[1] + '.db'), 'wb')
669	dataX.tofile(file)
670	file.close()
671	file = open(os.path.join(path[0], self.filename + path[1] + '.db'), 'wb')
672	data1X.tofile(file)
673	file.close()
674	}
675
676	hash_value = {
677	( 0 , 0 ): 9149491, ( 0 , 1 ): 4143844, ( 0 , 2 ): 8452911,
678	( 0 , 3 ): 3100691, ( 0 , 4 ): 3196613, ( 0 , 5 ): 7210416,
679	( 0 , 6 ): 6086509, ( 0 , 7 ): 7957641, ( 0 , 8 ): 131916,
680	( 0 , 9 ): 6918136, ( 0 , 10 ): 3016410, ( 0 , 11 ): 3288711,
681	( 0 , 12 ): 8539380, ( 0 , 13 ): 758094, ( 0 , 14 ): 7179238,
682	( 0 , 15 ): 7718041, ( 0 , 16 ): 5204153, ( 0 , 17 ): 6711869,
683	( 0 , 18 ): 8411491, ( 1 , 0 ): 2434388, ( 1 , 1 ): 1162683,
684	( 1 , 2 ): 927102, ( 1 , 3 ): 197419, ( 1 , 4 ): 9435893,
685	( 1 , 5 ): 2149216, ( 1 , 6 ): 2967038, ( 1 , 7 ): 5557593,
686	( 1 , 8 ): 4044723, ( 1 , 9 ): 4077413, ( 1 , 10 ): 8810194,
687	( 1 , 11 ): 7673830, ( 1 , 12 ): 1290402, ( 1 , 13 ): 704914,
688	( 1 , 14 ): 2782252, ( 1 , 15 ): 6972890, ( 1 , 16 ): 2649162,
689	( 1 , 17 ): 8444272, ( 1 , 18 ): 5863711, ( 2 , 0 ): 8701652,
690	( 2 , 1 ): 9073146, ( 2 , 2 ): 796709, ( 2 , 3 ): 3071327,
691	( 2 , 4 ): 81078, ( 2 , 5 ): 413463, ( 2 , 6 ): 9899215,
692	( 2 , 7 ): 3900485, ( 2 , 8 ): 4258038, ( 2 , 9 ): 9853936,
693	( 2 , 10 ): 5479882, ( 2 , 11 ): 4613169, ( 2 , 12 ): 7404562,
694	( 2 , 13 ): 5251570, ( 2 , 14 ): 1932628, ( 2 , 15 ): 9394001,
695	( 2 , 16 ): 6022071, ( 2 , 17 ): 216105, ( 2 , 18 ): 4278005,
696	( 3 , 0 ): 7136853, ( 3 , 1 ): 2500566, ( 3 , 2 ): 4107671,
697	( 3 , 3 ): 4081838, ( 3 , 4 ): 1785699, ( 3 , 5 ): 1424534,
698	( 3 , 6 ): 3024969, ( 3 , 7 ): 5734282, ( 3 , 8 ): 4175470,
699	( 3 , 9 ): 9404994, ( 3 , 10 ): 8430123, ( 3 , 11 ): 1255451,
700	( 3 , 12 ): 5986866, ( 3 , 13 ): 7055240, ( 3 , 14 ): 6371620,
701	( 3 , 15 ): 9283568, ( 3 , 16 ): 7313682, ( 3 , 17 ): 7717289,
702	( 3 , 18 ): 2299204, ( 4 , 0 ): 6500542, ( 4 , 1 ): 1976702,
703	( 4 , 2 ): 7553422, ( 4 , 3 ): 5187929, ( 4 , 4 ): 3201058,
704	( 4 , 5 ): 2222174, ( 4 , 6 ): 3817451, ( 4 , 7 ): 7344416,
705	( 4 , 8 ): 4960530, ( 4 , 9 ): 6786163, ( 4 , 10 ): 8006227,
706	( 4 , 11 ): 442411, ( 4 , 12 ): 4688575, ( 4 , 13 ): 5012537,
707	( 4 , 14 ): 3651243, ( 4 , 15 ): 7062230, ( 4 , 16 ): 6716660,
708	( 4 , 17 ): 4891547, ( 4 , 18 ): 5702153, ( 5 , 0 ): 8827952,
709	( 5 , 1 ): 7097129, ( 5 , 2 ): 9410525, ( 5 , 3 ): 1319909,
710	( 5 , 4 ): 6697319, ( 5 , 5 ): 6008737, ( 5 , 6 ): 9209372,
711	( 5 , 7 ): 1708104, ( 5 , 8 ): 8930801, ( 5 , 9 ): 3357765,
712	( 5 , 10 ): 4158639, ( 5 , 11 ): 8563534, ( 5 , 12 ): 1000997,
713	( 5 , 13 ): 4582316, ( 5 , 14 ): 6276028, ( 5 , 15 ): 9658685,
714	( 5 , 16 ): 4453094, ( 5 , 17 ): 9081939, ( 5 , 18 ): 6565077,