implementing Othello for embedded system

[Guest]

Archived from groups: comp.ai.games (More info?)

Hi,

I've been working on an Othello game for an embedded system. Currently
it features:

- Negascout Search
- Mobility + Potential Mobility
- Edge + 2X Pattern Table
- Hashtables (2tables x 16k x 8bytes)
- End Search
- Searches about 2-3kn/s on a DSP (about 1Mn/s when compiled and run
on a P4)
- Capped at 9 plys (16plys end) at maximum difficulty

The problem I'm facing with now is I need to cut down from 340kB of
RAM usage down to 64kB

This is a real pain because the edge table already requires 59049
values and currently takes up twice that number of bytes. I could drop
the edge+2x table to use an edge tables and negative weights for
X-squares, but I don't really want to do that because it seems to
severely affects the playing strength of the game. Using black/white
symmetry and 3 patterns per word I can reduce it to about 36k.

I will have to drop hashtables too, and similarly reduce the lookup
tables for mobility and potential mobility by half.

Are there any possibilities to reduce RAM usage, or possibilities to
strengthen the game or make it faster without using much additional
RAM?

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Gerald Tan <woefulwabbit@gmail.com> wrote:

> This is a real pain because the edge table already requires 59049
> values and currently takes up twice that number of bytes. I could drop
> the edge+2x table to use an edge tables and negative weights for
> X-squares, but I don't really want to do that because it seems to
> severely affects the playing strength of the game. Using black/white
> symmetry and 3 patterns per word I can reduce it to about 36k.

u can try use two symetries

a) natural

X-OXXX-- == --XXXO-X

b) black/white symetrie

X-OXXX-- == (-) --OOOX-O

now only 14884 values on 8 bits = 15Kb

good results see

http://perso.wanadoo.fr/othello

a+

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Bruno Causse wrote:

>>This is a real pain because the edge table already requires 59049
>>values and currently takes up twice that number of bytes. I could drop
>>the edge+2x table to use an edge tables and negative weights for
>>X-squares, but I don't really want to do that because it seems to
>>severely affects the playing strength of the game. Using black/white
>>symmetry and 3 patterns per word I can reduce it to about 36k.
> u can try use two symetries
> a) natural
>
> X-OXXX-- == --XXXO-X
>
> b) black/white symetrie
>
> X-OXXX-- == (-) --OOOX-O
>
> now only 14884 values on 8 bits = 15Kb

Hi, thanks for your reply.
I have considered taking advantage of symmetries before, but I could not
find a way to map edge configurations to an index.

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Gerald Tan <woefulwabbit@gmail.com> wrote:

> Hi, thanks for your reply.
> I have considered taking advantage of symmetries before, but I could not
> find a way to map edge configurations to an index.

yes you right, sorry

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Bruno Causse wrote:

>>Hi, thanks for your reply.
>>I have considered taking advantage of symmetries before, but I could not
>>find a way to map edge configurations to an index.
> yes you right, sorry

I guess Cyrano unpacks the table from applet into memory?

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Gerald Tan <woefulwabbit@gmail.com> wrote:

> I guess Cyrano unpacks the table from applet into memory?

yes, you right
--
bruno Causse
http://perso.wanadoo.fr/othello