Revision f079bf77
Added by Leszek Koltunski about 1 year ago
src/main/java/org/distorted/objectlib/tablebases/PruningTable.java | ||
---|---|---|
13 | 13 |
|
14 | 14 |
class PruningTable |
15 | 15 |
{ |
16 |
private static final int HEADER_SIZE = 5; |
|
16 |
static final int[] SUPPORTED = {4,8,12,16,20,24}; |
|
17 |
|
|
18 |
private static final int HEADER_SIZE = 6; |
|
17 | 19 |
private byte[] mData; |
18 | 20 |
private int mNumBits; |
19 | 21 |
private int mBucketBytes; |
... | ... | |
49 | 51 |
mData[0] = (byte)mLevel; |
50 | 52 |
mData[1] = (byte)mBucketBytes; |
51 | 53 |
mData[2] = (byte)mNumBits; |
52 |
mData[3] = (byte)(mNumBuckets/256); |
|
53 |
mData[4] = (byte)(mNumBuckets%256); |
|
54 |
mData[3] = (byte)(mNumBuckets>>>16); |
|
55 |
mData[4] = (byte)(mNumBuckets>>> 8); |
|
56 |
mData[5] = (byte)(mNumBuckets&0xff); |
|
54 | 57 |
} |
55 | 58 |
|
56 | 59 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
... | ... | |
102 | 105 |
break; |
103 | 106 |
case 8: ret = (mData[bytes]&0xff); |
104 | 107 |
break; |
105 |
case 12: ret = (bits%8)!=0 ? ((mData[bytes]&0xf)*256 + (mData[bytes+1]&0xff)) : ( (mData[bytes]&0xff)*16 + ((mData[bytes+1]>>>4)&0xf)); |
|
108 |
case 12: ret = (bits%8)!=0 ? (((mData[bytes]&0xf)<<8) + (mData[bytes+1]&0xff)) : (((mData[bytes]&0xff)<<4) + ((mData[bytes+1]>>>4)&0xf)); |
|
109 |
break; |
|
110 |
case 16: ret = ((mData[bytes]&0xff)<<8) + (mData[bytes+1]&0xff); |
|
111 |
break; |
|
112 |
case 20: if( (bits%8) !=0 ) ret = (((mData[bytes]&0x0f)<<16) + ((mData[bytes+1]&0xff)<<8) + ( mData[bytes+2] &0xff)); |
|
113 |
else ret = (((mData[bytes]&0xff)<<12) + ((mData[bytes+1]&0xff)<<4) + ((mData[bytes+2]>>>4)&0x0f)); |
|
106 | 114 |
break; |
107 |
case 16: ret = (mData[bytes]&0xff)*256 + (mData[bytes+1]&0xff);
|
|
115 |
case 24: ret = ((mData[bytes]&0xff)<<16) + ((mData[bytes+1]&0xff)<<8) + (mData[bytes+2]&0xff);
|
|
108 | 116 |
break; |
109 | 117 |
} |
110 | 118 |
|
... | ... | |
133 | 141 |
else |
134 | 142 |
{ |
135 | 143 |
mData[bytes] = (byte)(value>>>4); |
136 |
mData[bytes+1]= (byte)((byte)(value<<4) + (mData[bytes+1]&( 0xf)));
|
|
144 |
mData[bytes+1]= (byte)((byte)(value<<4) + (mData[bytes+1]&0xf));
|
|
137 | 145 |
} |
138 | 146 |
break; |
139 | 147 |
case 16: mData[bytes] = (byte)(value>>>8); |
140 | 148 |
mData[bytes+1] = (byte)(value&(0xff)); |
149 |
break; |
|
150 |
case 20: if( (bits%8) !=0 ) |
|
151 |
{ |
|
152 |
mData[bytes] = (byte)((mData[bytes]&(~0xf)) + (value>>>16)); |
|
153 |
mData[bytes+1]= (byte)(value>>>8); |
|
154 |
mData[bytes+2]= (byte)(value&(0xff)); |
|
155 |
} |
|
156 |
else |
|
157 |
{ |
|
158 |
mData[bytes] = (byte)(value>>>12); |
|
159 |
mData[bytes+1]= (byte)(value>>>4); |
|
160 |
mData[bytes+2]= (byte)((byte)(value<<4) + (mData[bytes+2]&0xf)); |
|
161 |
} |
|
162 |
break; |
|
163 |
case 24: mData[bytes] = (byte)(value>>>16); |
|
164 |
mData[bytes+1] = (byte)(value>>>8); |
|
165 |
mData[bytes+2] = (byte)(value&(0xff)); |
|
166 |
break; |
|
141 | 167 |
} |
142 | 168 |
} |
143 | 169 |
|
... | ... | |
240 | 266 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
241 | 267 |
// PUBLIC API |
242 | 268 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
243 |
// only numBits = 4,8,12,16 actually supported |
|
269 |
// only numBits = 4,8,12,16,20,24 actually supported
|
|
244 | 270 |
|
245 | 271 |
PruningTable(Tablebase table, int level, int numBits) |
246 | 272 |
{ |
... | ... | |
251 | 277 |
|
252 | 278 |
PruningTable(Tablebase table, int level) |
253 | 279 |
{ |
254 |
int[] supported = {4,8,12,16}; |
|
255 | 280 |
int minimum = 0, chosen = 0; |
256 | 281 |
int size = retNumPositions(table,level); |
257 | 282 |
int tableSize = table.getSize(); |
258 | 283 |
|
259 | 284 |
android.util.Log.e("D", "----- PRUNING TABLE LEVEL "+level+" ------"); |
260 | 285 |
|
261 |
for(int i=0; i<supported.length; i++)
|
|
286 |
for(int i=0; i<SUPPORTED.length; i++)
|
|
262 | 287 |
{ |
263 |
int approx = computeApproximateSize( tableSize, size, supported[i]);
|
|
288 |
int approx = computeApproximateSize( tableSize, size, SUPPORTED[i]);
|
|
264 | 289 |
|
265 | 290 |
if( i==0 || approx<minimum ) |
266 | 291 |
{ |
... | ... | |
268 | 293 |
chosen = i; |
269 | 294 |
} |
270 | 295 |
|
271 |
android.util.Log.e("D", "trying numBits: "+supported[i]+" approx size: "+approx);
|
|
296 |
android.util.Log.e("D", "trying numBits: "+SUPPORTED[i]+" approx size: "+approx);
|
|
272 | 297 |
} |
273 | 298 |
|
274 |
construct(table,level,supported[chosen]);
|
|
299 |
construct(table,level,SUPPORTED[chosen]);
|
|
275 | 300 |
} |
276 | 301 |
|
277 | 302 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
... | ... | |
283 | 308 |
mLevel = ((int)mData[0])&0xff; |
284 | 309 |
mBucketBytes = ((int)mData[1])&0xff; |
285 | 310 |
mNumBits = ((int)mData[2])&0xff; |
286 |
mNumBuckets =(((int)mData[3])&0xff)*256 + ((int)mData[4])&0xff;
|
|
311 |
mNumBuckets =((((int)mData[3])&0xff)<<16) + ((((int)mData[4])&0xff)<<8) + ((int)mData[5])&0xff;
|
|
287 | 312 |
} |
288 | 313 |
|
289 | 314 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
src/main/java/org/distorted/objectlib/tablebases/TablebasesAbstract.java | ||
---|---|---|
548 | 548 |
|
549 | 549 |
public void testPruning(int level) |
550 | 550 |
{ |
551 |
PruningTable table = new PruningTable(mTablebase,level); |
|
552 |
int size = mTablebase.getSize(); |
|
551 |
for( int supp : PruningTable.SUPPORTED ) |
|
552 |
{ |
|
553 |
PruningTable table = new PruningTable(mTablebase, level, supp); |
|
554 |
int size = mTablebase.getSize(); |
|
553 | 555 |
|
554 |
StringBuilder sb = new StringBuilder(); |
|
555 |
int num=0;
|
|
556 |
StringBuilder sb = new StringBuilder();
|
|
557 |
int num = 0;
|
|
556 | 558 |
|
557 |
for(int i=0; i<size; i++) |
|
558 |
{ |
|
559 |
if( table.belongs(i) ) |
|
559 |
for(int i=0; i<size; i++) |
|
560 | 560 |
{ |
561 |
if( (num%10)==0 ) sb.append("\n"); |
|
562 |
num++; |
|
563 |
sb.append(i); |
|
564 |
sb.append(' '); |
|
561 |
if (table.belongs(i)) |
|
562 |
{ |
|
563 |
if ((num % 10) == 0) sb.append("\n"); |
|
564 |
num++; |
|
565 |
sb.append(i); |
|
566 |
sb.append(' '); |
|
567 |
} |
|
565 | 568 |
} |
566 |
} |
|
567 | 569 |
|
568 |
android.util.Log.e("D", "numbers: "+sb); |
|
570 |
android.util.Log.e("D", "numbers: " + sb); |
|
571 |
} |
|
569 | 572 |
} |
570 | 573 |
} |
src/main/java/org/distorted/objectlib/tablebases/TablebasesCube2.java | ||
---|---|---|
18 | 18 |
|
19 | 19 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
20 | 20 |
|
21 |
public class TablebasesCube2 extends TablebasesMITM
|
|
21 |
public class TablebasesCube2 extends TablebasesPruning
|
|
22 | 22 |
{ |
23 | 23 |
private static final int[][] P = |
24 | 24 |
{ |
... | ... | |
73 | 73 |
|
74 | 74 |
public TablebasesCube2(Resources res) |
75 | 75 |
{ |
76 |
super(res, new int[] {R.raw.cube_2_pruning5,R.raw.cube_2_pruning11} );
|
|
76 |
super(res, new int[] {R.raw.cube_2_pruning5}, new int[] {R.raw.cube_2_pruning11} );
|
|
77 | 77 |
} |
78 | 78 |
|
79 | 79 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
... | ... | |
146 | 146 |
|
147 | 147 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
148 | 148 |
|
149 |
int[] getPruningLevels() |
|
149 |
int[] getMidPruningLevels()
|
|
150 | 150 |
{ |
151 |
return new int[] {5,11}; |
|
151 |
return new int[] {4,5}; |
|
152 |
} |
|
153 |
|
|
154 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
155 |
|
|
156 |
int[] getHighPruningLevels() |
|
157 |
{ |
|
158 |
return null;//new int[] {11}; |
|
159 |
} |
|
160 |
|
|
161 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
162 |
|
|
163 |
int getGodsNumber() |
|
164 |
{ |
|
165 |
return 11; |
|
152 | 166 |
} |
153 | 167 |
|
154 | 168 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
src/main/java/org/distorted/objectlib/tablebases/TablebasesMITM.java | ||
---|---|---|
1 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
2 |
// Copyright 2023 Leszek Koltunski // |
|
3 |
// // |
|
4 |
// This file is part of Magic Cube. // |
|
5 |
// // |
|
6 |
// Magic Cube is proprietary software licensed under an EULA which you should have received // |
|
7 |
// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html // |
|
8 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
9 |
|
|
10 |
package org.distorted.objectlib.tablebases; |
|
11 |
|
|
12 |
import android.content.res.Resources; |
|
13 |
|
|
14 |
import java.io.ByteArrayOutputStream; |
|
15 |
import java.io.IOException; |
|
16 |
import java.io.InputStream; |
|
17 |
|
|
18 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
19 |
|
|
20 |
public abstract class TablebasesMITM extends TablebasesAbstract |
|
21 |
{ |
|
22 |
private PruningTable[] mTables; |
|
23 |
private boolean mInitialized; |
|
24 |
private int[] mLevels; |
|
25 |
|
|
26 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
27 |
|
|
28 |
abstract int[] getPruningLevels(); |
|
29 |
|
|
30 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
31 |
|
|
32 |
private void createPruningTable(Resources res, int id, int index) |
|
33 |
{ |
|
34 |
InputStream stream = res.openRawResource(id); |
|
35 |
ByteArrayOutputStream buffer = new ByteArrayOutputStream(); |
|
36 |
|
|
37 |
int nRead; |
|
38 |
byte[] tmp = new byte[16384]; |
|
39 |
|
|
40 |
try |
|
41 |
{ |
|
42 |
while ((nRead = stream.read(tmp, 0, tmp.length)) != -1) |
|
43 |
{ |
|
44 |
buffer.write(tmp, 0, nRead); |
|
45 |
} |
|
46 |
stream.close(); |
|
47 |
byte[] data = buffer.toByteArray(); |
|
48 |
buffer.close(); |
|
49 |
mTables[index] = new PruningTable(data); |
|
50 |
mLevels[index] = mTables[index].getLevel(); |
|
51 |
} |
|
52 |
catch(IOException ex) |
|
53 |
{ |
|
54 |
mInitialized = false; |
|
55 |
} |
|
56 |
} |
|
57 |
|
|
58 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
59 |
|
|
60 |
public TablebasesMITM() |
|
61 |
{ |
|
62 |
super(); |
|
63 |
mInitialized = false; |
|
64 |
} |
|
65 |
|
|
66 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
67 |
|
|
68 |
public TablebasesMITM(Resources res, int[] resourceIDs) |
|
69 |
{ |
|
70 |
super(); |
|
71 |
|
|
72 |
int numOfIDs = resourceIDs.length; |
|
73 |
mTables = new PruningTable[numOfIDs]; |
|
74 |
mLevels = new int[numOfIDs]; |
|
75 |
mInitialized = true; |
|
76 |
|
|
77 |
for(int i=0; i<numOfIDs; i++) createPruningTable(res,resourceIDs[i],i); |
|
78 |
} |
|
79 |
|
|
80 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
81 |
|
|
82 |
public byte[][] getPacked() |
|
83 |
{ |
|
84 |
if( !mInitialized ) |
|
85 |
{ |
|
86 |
int[] levels = getPruningLevels(); |
|
87 |
int numLevels= levels.length; |
|
88 |
int maxLevel = 0; |
|
89 |
|
|
90 |
for( int l : levels ) |
|
91 |
if( l>maxLevel ) maxLevel = l; |
|
92 |
|
|
93 |
createTablebase(maxLevel); |
|
94 |
mTables = new PruningTable[numLevels]; |
|
95 |
mLevels = new int[numLevels]; |
|
96 |
|
|
97 |
for(int i=0; i<numLevels; i++) |
|
98 |
{ |
|
99 |
mTables[i] = new PruningTable(mTablebase,levels[i]); |
|
100 |
mLevels[i] = mTables[i].getLevel(); |
|
101 |
} |
|
102 |
|
|
103 |
mInitialized = true; |
|
104 |
} |
|
105 |
|
|
106 |
int num = mTables.length; |
|
107 |
byte[][] data = new byte[num][]; |
|
108 |
for(int i=0; i<num; i++) data[i] = mTables[i].getPacked(); |
|
109 |
|
|
110 |
return data; |
|
111 |
} |
|
112 |
|
|
113 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
114 |
|
|
115 |
public int[][] solution(int index, int[] extra) |
|
116 |
{ |
|
117 |
return null; |
|
118 |
} |
|
119 |
} |
src/main/java/org/distorted/objectlib/tablebases/TablebasesPruning.java | ||
---|---|---|
1 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
2 |
// Copyright 2023 Leszek Koltunski // |
|
3 |
// // |
|
4 |
// This file is part of Magic Cube. // |
|
5 |
// // |
|
6 |
// Magic Cube is proprietary software licensed under an EULA which you should have received // |
|
7 |
// along with the code. If not, check https://distorted.org/magic/License-Magic-Cube.html // |
|
8 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
9 |
|
|
10 |
package org.distorted.objectlib.tablebases; |
|
11 |
|
|
12 |
import android.content.res.Resources; |
|
13 |
|
|
14 |
import java.io.ByteArrayOutputStream; |
|
15 |
import java.io.IOException; |
|
16 |
import java.io.InputStream; |
|
17 |
|
|
18 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
19 |
|
|
20 |
public abstract class TablebasesPruning extends TablebasesAbstract |
|
21 |
{ |
|
22 |
private boolean mInitialized; |
|
23 |
private PruningTable[] mHighTables; |
|
24 |
private PruningTable[] mMidTables; |
|
25 |
private int mGodsNumber, mLowestHigh, mHighestMid, mLowestMid; |
|
26 |
|
|
27 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
28 |
|
|
29 |
abstract int[] getMidPruningLevels(); |
|
30 |
abstract int[] getHighPruningLevels(); |
|
31 |
abstract int getGodsNumber(); |
|
32 |
|
|
33 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
34 |
|
|
35 |
private PruningTable createPruningTable(Resources res, int id) |
|
36 |
{ |
|
37 |
InputStream stream = res.openRawResource(id); |
|
38 |
ByteArrayOutputStream buffer = new ByteArrayOutputStream(); |
|
39 |
|
|
40 |
int nRead; |
|
41 |
byte[] tmp = new byte[16384]; |
|
42 |
|
|
43 |
try |
|
44 |
{ |
|
45 |
while ((nRead = stream.read(tmp, 0, tmp.length)) != -1) |
|
46 |
{ |
|
47 |
buffer.write(tmp, 0, nRead); |
|
48 |
} |
|
49 |
stream.close(); |
|
50 |
byte[] data = buffer.toByteArray(); |
|
51 |
buffer.close(); |
|
52 |
return new PruningTable(data); |
|
53 |
} |
|
54 |
catch(IOException ex) |
|
55 |
{ |
|
56 |
mInitialized = false; |
|
57 |
return null; |
|
58 |
} |
|
59 |
} |
|
60 |
|
|
61 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
62 |
|
|
63 |
public TablebasesPruning() |
|
64 |
{ |
|
65 |
super(); |
|
66 |
mGodsNumber = getGodsNumber(); |
|
67 |
mInitialized = false; |
|
68 |
} |
|
69 |
|
|
70 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
71 |
|
|
72 |
public TablebasesPruning(Resources res, int[] midIDs, int[] highIDs) |
|
73 |
{ |
|
74 |
super(); |
|
75 |
|
|
76 |
int mid = midIDs !=null ? midIDs.length : 0; |
|
77 |
int high= highIDs!=null ? highIDs.length : 0; |
|
78 |
|
|
79 |
mMidTables = mid >0 ? new PruningTable[mid] : null; |
|
80 |
mHighTables= high>0 ? new PruningTable[high]: null; |
|
81 |
mGodsNumber = getGodsNumber(); |
|
82 |
mInitialized = true; |
|
83 |
|
|
84 |
for(int i=0; i<mid ; i++) mMidTables[i] = createPruningTable(res,midIDs[i] ); |
|
85 |
for(int i=0; i<high; i++) mHighTables[i]= createPruningTable(res,highIDs[i]); |
|
86 |
} |
|
87 |
|
|
88 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
89 |
|
|
90 |
public byte[][] getPacked() |
|
91 |
{ |
|
92 |
if( !mInitialized ) |
|
93 |
{ |
|
94 |
int[] midLevels = getMidPruningLevels(); |
|
95 |
int numMidLevels= midLevels!=null ? midLevels.length : 0; |
|
96 |
int[] highLevels = getHighPruningLevels(); |
|
97 |
int numHighLevels= highLevels!=null ? highLevels.length : 0; |
|
98 |
int maxLevel = 0; |
|
99 |
|
|
100 |
if( highLevels!=null ) |
|
101 |
{ |
|
102 |
for( int l : highLevels ) |
|
103 |
if( l>maxLevel ) maxLevel = l; |
|
104 |
} |
|
105 |
else |
|
106 |
{ |
|
107 |
if( midLevels!=null ) |
|
108 |
for( int l : midLevels ) |
|
109 |
if( l>maxLevel ) maxLevel = l; |
|
110 |
} |
|
111 |
|
|
112 |
createTablebase(maxLevel); |
|
113 |
mMidTables = numMidLevels >0 ? new PruningTable[numMidLevels ] : null; |
|
114 |
mHighTables= numHighLevels>0 ? new PruningTable[numHighLevels] : null; |
|
115 |
|
|
116 |
for(int i=0; i<numMidLevels; i++) |
|
117 |
mMidTables[i] = new PruningTable(mTablebase,midLevels[i]); |
|
118 |
for(int i=0; i<numHighLevels; i++) |
|
119 |
mHighTables[i] = new PruningTable(mTablebase,highLevels[i]); |
|
120 |
|
|
121 |
mInitialized = true; |
|
122 |
} |
|
123 |
|
|
124 |
int midNum = mMidTables !=null ? mMidTables.length : 0; |
|
125 |
int highNum = mHighTables!=null ? mHighTables.length : 0; |
|
126 |
byte[][] data = new byte[midNum+highNum][]; |
|
127 |
|
|
128 |
for(int i=0; i<midNum ; i++) data[i ] = mMidTables[i].getPacked(); |
|
129 |
for(int i=0; i<highNum; i++) data[i+midNum] = mHighTables[i].getPacked(); |
|
130 |
|
|
131 |
return data; |
|
132 |
} |
|
133 |
|
|
134 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
135 |
|
|
136 |
public int[][] solution(int index, int[] extra) |
|
137 |
{ |
|
138 |
return null; |
|
139 |
} |
|
140 |
} |
Also available in: Unified diff
PruningTables now support numBits=20,24.
Progress with TablebasesPruning.