PDA

View Full Version : /\///\/\


Sir Penguin
12-05-2005, 22:15:24
/* filename: sp_nim_game author: Neil MacMillan
* project: Game of Nim modification date: 11.05.05
* description: Game logic for the Game of Nim as implemented in a
* Neverwinter Nights module. There are a few other small scripts that
* actually use this one. They're called sp_nim_*. The sp_nim_reload script
* sets up the game area, although it makes some assumptions about the area
* geometry, but that's a story for another time.
*/

#include "zep_inc_main" // CEP stuff for ToggleTorch()

int NUM_COLS = 16; // the number of torches in a row

/* int GetNimXOR();
* Return the 3-way bitwise exclusive OR of the three row values
* Type: Calculation
* Output: int, the bitwise XOR of the three row values.
*/
int GetNimXOR()
{
int a = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow1Val");
int b = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow2Val");
int c = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow3Val");

return a^b^c;
}

/* int GetNimMove(int a, int b, int c);
* Figure out how many torches to keep lit in the row with value c.
* Type: Calculation
* Input: int a, the value of a safe row; int b, the value of a safe row; int c,
* the value of the row from which to subtract something.
* Output: the new value of c (the number of torches to leave in that row)
*/
int GetNimMove(int a, int b, int c)
{
int nNewC = a^b; // the number of torches to remove
if ((nNewC^(a^b)) != 0) {
SpeakString("Error in GetNimMove, XOR check = "+IntToString(nNewC^(a^b)));
} else if (nNewC <= 0) {
SpeakString("Error in GetNimMove, nNewC = "+IntToString(nNewC));
}
return nNewC;
}
// the next two functions aren't really needed.
/* string IntToBitString(int nNum);
* Convert a non-negative integer into a bit string.
* Type: Wrapper
* Input: int nNum, the integer to convert
* Output: the bit string representation of nNum, "0" if nNum is 0.
*/
string _IntToBitStringCalc(int nNum);
string IntToBitString(int nNum)
{
if (nNum == 0) {
return "0";
} else {
return _IntToBitStringCalc(nNum);
}
}

/* string IntToBitStringCalc(int nNum);
* Convert a *positive* integer into a bit string.
* Type: Calculation
* Input: int nNum, the non-negative, non-zero integer to convert
* Output: the bit string representation of nNum.
*/
string _IntToBitStringCalc(int nNum)
{
//return ( (n > 0) && (_IntToBitString(n>>>1)+IntToString(n&1)) || "0");
if (nNum > 0) {
return _IntToBitStringCalc(nNum >>> 1) + IntToString(nNum & 1);
} else {
// if this condition returns "0", the output bit string will have a
// leading 0. That's undesireable, and so is outputting an empty string
// on a non-recursed 0 input, so this function is placed in a wrapper
// that deals with 0 inputs (above). Better solutions?
// Better solution: not using the fucking thing. Argh.
return "";
}
}

/* NimTriMax(int a, int b, int c);
* Return the maximum of three integers. Equal values are handled properly.
* Type: Calculation
* Input: int a, an integer to compare; int b, an integer to compare; inc c,
* an integer to compare
* Output: the maximum of the three integers
*/
int NimTriMax(int a, int b, int c)
{
if (a > b && a > c) return a;
if (b > c) return b;
return c;
}

/* Adapted from zep_torch, Copyright (c) 2001 Bioware Corp.
* Originally modified by Dan Heidel 1/21/04 for CEP
* More modifications by Neil MacMillan 09.05.05 for Game of Nim
* I think all changes have been marked.
*/
// This could be pruned for our purposes--we don't need to turn a light on.
/* void ToggleTorch(object oTorchVictim);
* Turn a torch on if it's off, or off if it's on. This is done by replacing
* a torch that's on with one that's off and vice versa.
* Type: Replace Object
* Input: object oTorchVictim, the torch to toggle
*/
void ToggleTorch(object oTorchVictim)
{
// these were changed to refer to oTorchVictim instead of OBJECT_SELF.
location lLoc = GetLocation(oTorchVictim);
string sResRef = GetResRef(oTorchVictim);
int nAmIOn = GetLocalInt(oTorchVictim, "CEP_L_AMION");
int nLightCycle = GetLocalInt(oTorchVictim, "CEP_L_LIGHTCYCLE");
int nInitialized = GetLocalInt(oTorchVictim, "CEP_L_LIGHTINITIALIZED");
int nLightDiurnal = GetIsNight();
string sLightConst = GetLocalString(oTorchVictim, "CEP_L_LIGHTCONST");
string sLightSwap = GetLocalString(oTorchVictim, "CEP_L_LIGHTSWAP");
int nLight = ColorInit(sLightConst);

// I changed this because this way's more efficient and easier to read.
// Although now that I think about it, some math nerd might think it's
// finding the derangement of nAmIOn, but since the derangement of a set
// of size 1 is zero, well, it works out anyway since we're only switching
// from 1 to 0. Hah, suck it, math.
nAmIOn = !nAmIOn;

object oNew = CreateObject(OBJECT_TYPE_PLACEABLE, sLightSwap, lLoc);
SetLocalInt(oNew, "CEP_L_AMION", nAmIOn);
// the CEP_L_LIGHTCYCLE setting is changed, because we want the torch to be
// off all the time.
SetLocalInt(oNew, "CEP_L_LIGHTCYCLE", 0);
SetLocalInt(oNew, "CEP_L_LIGHTINITIALIZED", nInitialized);
SetLocalInt(oNew, "CEP_L_LIGHTDIURNAL", nLightDiurnal);
SetLocalString(oNew, "CEP_L_LIGHTCONST", sLightConst);
SetLocalString(oNew, "CEP_L_LIGHTSWAP", sResRef);

// This branch isn't taken, since we're only turning torches off.
/*if (nAmIOn == 1)
{
effect eLight = EffectVisualEffect(nLight);
ApplyEffectToObject(DURATION_TYPE_PERMANENT, eLight, oNew);
} */
// free() is so much more peaceful and happy than DestroyObject(). :(
// I am concerned about the ethical implications of this. Are we freeing
// the objects by destroying them? A programmer would say yes, but we all
// know that programmers are sadistic bastards. Is destruction justified
// sometimes? If not, does the fact that entropy always increases make the
// Universe itself evil because physics demands that something, somewhere,
// is being destroyed? If so, how do we determine that destroying something
// will free it? From what are we freeing these objects by destroying them?
// Responsibility? Well, the heap, of course, and I suppose that depending
// on what it is a heap of, that would be an improvement of conditions.
// Meditate on this I shall.
DestroyObject(oTorchVictim, 0.0);
}

/* void RemoveTorches(int nRow,int nLeave);
* Remove some torches on the computer's turn.
* Type: Data Structure Deletion
* Input: int nRow, the number of the row from which to remove torches {0 to 2},
* int nLeave, the number of torches to leave in the row {0 to value-1}
*/
void RemoveTorches(int nRow,int nLeave)
{
int nColNum;
string sRowTag;
string sTorchTag;
object oMapPin;
object oTorch;

sRowTag = "0"+IntToString(nRow);
// Note that nLeave is the number of torches to leave, and this removes
// torches numbered from nLeave up to the number of torches in the row. The
// torches actually left end with the torch numbered nLeave-1, due to using
// 0-based indexing in torch labels.
for (nColNum = nLeave; nColNum <NUM_COLS; nColNum++) {
sTorchTag = "NIM_TORCH_"+sRowTag+((nColNum<10)?"0":"")+IntToString(nColNum);
// get the torch
oTorch = GetObjectByTag(sTorchTag);
// check if it's already been turned off--if it has, stop
if (!GetLocalInt(oTorch,"CEP_L_AMION")) {
break;
}
// and if it hasn't been turned off, turn it off
ToggleTorch(oTorch);
// also, turn off the map pin.
oMapPin = GetObjectByTag("WP"+sTorchTag);
SetMapPinEnabled(oMapPin,0);
}
// Speaking of more efficient and easier to read... well... ummm... at least
// this is more space efficient. Anyway, this just sets the new value of
// the row being changed in the corresponding NIM_PORTAL variable.
SetLocalInt(GetObjectByTag("NIM_PORTAL"),(nRow==0)?"nRow1Val":
((nRow==1)?"nRow2Val":"nRow3Val"),nLeave);
}


SP

Sir Penguin
12-05-2005, 22:15:51
/* void NimPickAnyMoveSmart();
* Called when the XOR is 0. From this point, a clever player could be
* guaranteed to win. The function picks any move that doesn't give an obvious
* win to the player.
* Type: Calculation (Side Effect)
*/
void NimPickAnyMoveSmart()
{
int nRow1Val; // current value of the top-most row
int nRow2Val; // current value of the middle row
int nRow3Val; // current value of the bottom row
int nNewMovePre; // the old value of the row to change
int nNewMoveVal; // the new value of the row to change
int nNewMoveRow; // the row to change
int nChecked; // bit field representing whether a row has been checked

nRow1Val = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow1Val");
nRow2Val = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow2Val");
nRow3Val = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow3Val");

// we don't want the computer to make the following moves, if possible:
// - remove all torches from a row
// - leave two equal rows

// this infinite loop will be broken out of when an appropriate move has
// been found.
while (TRUE) {
// pick a row
nNewMoveRow = Random(3);
// check whether or not this row has been picked, and if it hasn't, then
// set its bit in nChecked. Bits are set from LSB, by row number.

// figure out the value of the row we're changing
nNewMovePre = (nNewMoveRow==0)?nRow1Val:((nNewMoveRow==1)?nRow2V al:nRow3Val);
// if the row is already zero or 1, just give up and try again
if (nNewMovePre <= 1) continue;
// otherwise, pick a random non-zero value less than the old value
// maybe this should go in another while, so we only pick the row once?
nNewMoveVal = Random(nNewMovePre-1)+1;
// make sure that the value doesn't equal the other rows
if (nNewMoveVal != nRow1Val) {
if (nNewMoveVal != nRow2Val) {
if (nNewMoveVal != nRow3Val) {
break;
}
}
}
}

} // incomplete, probably wrong, as usual. Sigh.

/* void NimPickAnyMoveDumb();
* Called when the XOR is 0. From this point, a clever player could be
* guaranteed to win. The function picks a move that gives the player a clearer
* indication of what to do next.
* Type: Calculation (Side Effect)
*/
void NimPickAnyMoveDumb()
{
}

/* void NimPickWinningMove();
* Called when the XOR isn't 0. From this point, the computer is guaranteed to
* win the game. It calculates the winning move and makes it.
* Type: Calculation (Side Effect)
*/
void NimPickWinningMove()
{
int a; // the first row value
int b; // the second row value
int c; // the third row value
int nASig; // the significant portion of a
int nBSig; // the significant portion of b
int nCSig; // the significant portion of c
int nDiff; // the number of torches to extinguish from the victim
int nMaxSig; // the maximum of nASig, nBSig, and nCSig.
int nRowVictim; // the row from which to extinguish torches
int nXOR; // a^b^c

// here is an explanation of the algorithm:
// - retrieve the values of the rows, as stored in NIM_PORTAL
// - these are stored in variables a, b, and c.
// - find out nXOR = a^b^c
// - convert the XOR into a bit string and find its length (should be log(),
// not a string comparison--but then I can't use the clever function I
// spent hours copying from the Python Cookbook. :()
// - for a, b, and c, remove all bits more significant (farther to the left)
// than the most significant bit of the XOR. This is done because we know
// that those bits do not contribute to the XOR, and we're looking for
// the bits that we need to change to make the XOR = 0.
// - after stripping off the unused MSBs, find the largest stripped number.
// The row corresponding to this number is the one from which we will
// extinguish torches (the victim row). It is possible that another row
// could be used as the victim, but we select this row because it is
// guaranteed to be useful--since it contributes the MSB, that bit must
// be set from 1 to 0, and 0x, x being any bit string, is always less than
// 1x, so all it takes to get from 1x to 0x is a subtraction. That will,
// for each column, either toggle the bit on (if the row has no bit there)
// or toggle the bit off (if the row has a bit there) if the column has
// an odd number of bits. Note that 1^1^1=1, and 1=1 (odd numbers of
// bits). It will leave a bit the way it is if the bit's column has an
// even number of set bits, because 1^1=0 and 0^0=0. Remember, all bit
// columns must XOR to 0 for the whole bitwise XOR to be 0.
// - finally, we choose how many torches to leave lit in the victim row,
// using GetNimMove. The number to leave equals a^b, where a and b are
// the values of the rows that aren't being changed. This is true because
// x^x=0 => (a^b)^(a^b)=0 => (a^b)^c=0, where c is the new value of
// the changed row equal to a^b. Recall that any move that leaves a^b^c=0
// is a winning move.

// retrieve the row values and covert them to bit strings
a = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow1Val");
b = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow2Val");
c = GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow3Val");
nXOR = GetNimXOR();
// this should just be a log(), goddamnit >:(
nXORLen =GetStringLength(IntToBitString(nXOR));
// calculate which row gives the most significant bit, and victimise it
nASig = 0; nBSig = 0; nCSig = 0;
// the following does this: nASig = a & (2**nXORLen)-1, WLOG
// in other words, it extracts the nXORLen least significant bits from a.
nASig = a & FloatToInt( pow(2.0f,IntToFloat(nXORLen))-1 );
nBSig = b & FloatToInt( pow(2.0f,IntToFloat(nXORLen))-1 );
nCSig = c & FloatToInt( pow(2.0f,IntToFloat(nXORLen))-1 );
// note that in the case where two rows are of equal value and are of
// greater value than the third row, this will select the top-most row to be
// the victim.
nMaxSig = NimTriMax(nASig,nBSig,nCSig);
if (nMaxSig == nASig && a > GetNimMove(b,c,a)) {
nRowVictim = 0;
nDiff = GetNimMove(b,c,a);
} else if (nMaxSig == nBSig && b > GetNimMove(a,c,b)) {
nRowVictim = 1;
nDiff = GetNimMove(a,c,b);
} else {
nRowVictim = 2;
nDiff = GetNimMove(a,b,c);
}
RemoveTorches(nRowVictim,nDiff);
// DEBUG
SpeakString("Selected row "+IntToString(nRowVictim)+" as victim, set to "+IntToString(nDiff));
string nRow1Val = IntToString(GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow1Val"));
string nRow2Val = IntToString(GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow2Val"));
string nRow3Val = IntToString(GetLocalInt(GetObjectByTag("NIM_PORTAL"),"nRow3Val"));
SpeakString("Row A value: "+nRow1Val);
SpeakString("Row B value: "+nRow2Val);
SpeakString("Row C value: "+nRow3Val);
// END DEBUG
}

/* void NimGameMove();
* Decide what kind of move to make in response to the player move.
* Type: Control Router
*/
void NimGameMove()
{
if (GetNimXOR() == 0) {
// if we can't pick a winning move, pick a non-winning move.
// if the difficulty is not on easy or very easy, make a smart move
// (not written yet)
NimPickAnyMoveSmart(); // incomplete
} else {
// otherwise, the computer can pick a winning move
if (GetGameDifficulty() == GAME_DIFFICULTY_EASY ||
GetGameDifficulty() == GAME_DIFFICULTY_VERY_EASY) {
// if the difficulty is on easy or very easy, there's a 30% chance
// of the computer picking a move that may not be a winning move.
// Uh, maybe a 31% chance. Meh, off-by-one error, whatever.
if (d100() <= 30) {
NimPickAnyMoveDumb();
} else {
NimPickWinningMove();
}
} else {
// and if the game's set on normal or harder, pick a winning move
// all the time.
NimPickWinningMove();
}
}
}

SP

Sir Penguin
12-05-2005, 22:18:05
/* filename: sp_nim_torch author: Neil MacMillan
* project: Game of Nim date: 12.05.05
* description: Script to be used by a lit, usable torch's OnUsed handle.
*/

#include "sp_nim_game"

void main()
{
string sColNum; // a torch's column number in string format
string sRowNum; // a torch's row number in string format

// retrieve the used torch's row and column numbers
sRowNum = GetLocalString(OBJECT_SELF,"sRowNum");
sColNum = GetLocalString(OBJECT_SELF,"sColNum");
// remove the torch and all the ones to its right
RemoveTorches(StringToInt(sRowNum),StringToInt(sCo lNum));
// and let the computer have a turn.
NimGameMove();
}

SP

Japher
12-05-2005, 22:23:23
don't share anything

any more

MattHiggs
12-05-2005, 22:24:42
What's Nim?

Sir Penguin
12-05-2005, 22:55:26
Originally posted by Japher
don't share anything

any more
:lol:

NIM == Never Ingest Mice.

SP

Lazarus and the Gimp
12-05-2005, 23:00:42
What? What gibberish is this?

mr.G
12-05-2005, 23:07:08
SP, you are strange.

jsorense
12-05-2005, 23:07:29
:rolleyes:

mr.G
12-05-2005, 23:09:28
:rolleyes:

mr.G
12-05-2005, 23:11:04
if we can't pick a winning move, pick a non-winning move
seee, that's the spirit
just dooooooooooo di doooooooooo something

Sir Penguin
12-05-2005, 23:53:27
Did you actually read it? :hmm

SP

The Mad Monk
13-05-2005, 00:45:38
Is there a secret in it?

Immortal Wombat
13-05-2005, 00:46:21
I have in the past wondered how hard it would be to program a NIM game. Now I know, I shall of course not bother.

Sir Penguin
13-05-2005, 01:26:17
Not worth the effort?

SP

Immortal Wombat
13-05-2005, 01:56:58
Indeed.

Sir Penguin
13-05-2005, 02:02:19
Hmm... I'm not sure if I meant it's too simple to be worth the overhead, or too hard to be worth the time spent. It's actually deceptively non-complex. I might have overcommented.

SP

Greg W
13-05-2005, 03:45:04
Summary?

Funko
13-05-2005, 09:03:14
Originally posted by Sir Penguin
:lol:

NIM == Never Ingest Mice.

SP

That's my first post ever.

What does all the other gibberish mean?

Oerdin
13-05-2005, 09:16:21
Originally posted by MattHiggs
What's Nim?

http://www.imdb.com/title/tt0084649/

Drekkus
13-05-2005, 09:16:58
it has speaking strings

Funko
13-05-2005, 09:24:18
Greg told me what NIM meant when he was in London and I promptly forgot it.

Sir Penguin
13-05-2005, 09:35:16
"Nim" (from the German "Nimm" I think, which means "Take!") is used to describe any game where you remove items from piles and win or lose based on who removed the last items. The script I posted is used as the core logic of an implementation of the most common form of Nim game (generally just called the Game of Nim), using the Neverwinter Nights toolset. It creates three rows of 16 torches (actually, candle sconces). Each row has a random number of torchs from 1 to 16 lit, starting from the left. The player and computer take turns extinguishing torches. Any number of torches can be extinguished in a single row during a turn, and only the rightmost torches in the row can be extinguished. Whoever extinguishes the last torch wins.

http://www.csc.uvic.ca/~nrqm/transfer/nim.jpg

SP

Greg W
13-05-2005, 10:15:07
Right. So, nothing to do with NIM then.

Sir Penguin
13-05-2005, 10:23:18
Only if you have no vision or imagination.

SP

Greg W
13-05-2005, 10:26:39
I am teh master of NIM! Respect my authoritah!

Drekkus
13-05-2005, 10:42:49
So it's sort of a birthday cake game.

mr.G
13-05-2005, 11:03:03
:lol: like blaasvoetbal

Drekkus
13-05-2005, 11:53:02
I think NIM is Roosendaals, btw.

Greg W
13-05-2005, 12:29:58
Nah...

The Mad Monk
14-05-2005, 03:56:26
I see you were getting philosophical somewhere in the middle of all that. Too much coffee, or too little?

Sir Penguin
14-05-2005, 08:53:31
I don't drink coffee. So, too little.

SP

notyoueither
14-05-2005, 09:02:00
Someone is going to spill the secret of Nim, sometime.

Sir Penguin
14-05-2005, 09:17:20
a^b^c=0

SP

Greg W
14-05-2005, 10:23:13
Originally posted by notyoueither
Someone is going to spill the secret of Nim, sometime. I've told 2 people. :D

jsorense
14-05-2005, 16:15:07
:coolgrin:

mr.G
15-05-2005, 11:06:45
Originally posted by Drekkus
I think NIM is Roosendaals, btw. Nim ter nog mar jintje