text:
• Create Account

## minimax with alpha beta pruning implementation stuck.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

28 replies to this topic

### #1whitenose  Members

Posted 08 October 2012 - 01:21 PM

Hello,
Im new to this so please escuse my mistakes.
I'm trying to implement a 9Men's Morris game and i'm using minimax with alpha-beta pruning finding BestMove for "computer".

The problem is that if depth >= 3 then getBestMove() returns invalid move (board) , meaning that
it's returning a move (board) from other team sometimes - and I don't know where i go wrong.

Is my algorithm implementation done right ?! What i'm missing ?

Here is my Java code , and getBestMove() function :

private int getBestMove(board board, int depth, int alpha, int beta, boolean bIsMax)
{
// is depth reached ? or do we have a winner ? (checkWinner() returns 0 if nobody is winning so far!)
if (depth == 0 || board.checkWinner()!=0)
{
// if depth reached, or we DO have a winner.
return board.evaluateBoard();
}

// is "computer" turn
if (bIsMax)
{
// generate all possible boards for "computer" (MAX).
ArrayList<board> boardsArray = board.generateNextPossibleBoards(bIsMax);

// loop thru all possible previously generated boards
for(board nextBoard: boardsArray)
{
// recurse
int score = Math.max(alpha, getBestMove(nextBoard, depth - 1, alpha, beta, !bIsMax));
nextBoard.showBoard("next-max[" + boardsArray.size() + "]");  // display to user current board.(debbuging purpose)

// found a better board ?
if ( score > alpha )
{
alpha = score;
chosenBoard = nextBoard; // save best board so far to "chosenBoard"
}

if(beta<=score) break; // prune
}

// clear boards array when done.
boardsArray.clear();

// return alpha.
return alpha;
}
else
{
// generate all possible boards for "player" (MIN).
ArrayList<board> boardsArray = board.generateNextPossibleBoards(bIsMax);

// loop thru all these possible boards.
for(board nextBoard: boardsArray)
{
// recurse
beta = Math.min(beta, getBestMove(nextBoard, depth - 1, alpha, beta, !bIsMax));
nextBoard.showBoard("next-min[" + boardsArray.size() + "]");

if(beta <= alpha) break; // prune.
}

// clear boards array when done.
boardsArray.clear();

// return beta.
return beta;
}

}

and the calling of this method is:

short depth = 2;

// get best move for "computer" on this phase
getBestMove(simulationBoard, depth , Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, true);

and this is the evaluation function :

// evaluate current board.
public int evaluateBoard()
{
int score = 0;

score = score + (checkWinner());			   // checkWinner() returns  -1000000 if player wins, +1000000 if computer wins.
score = score + (checkMills()*1000);		  // checkMills() returns   -10000*mills_count if player has some mills formed,  or  +10000*mills_count otherwise.
score = score + (checkBlockers()*500);	 // checkBlockers() returns  -1000*block_count if player has bloked some tokens,  or  +1000*block_count otherwise
score = score + (checkFormers()*50);	   // etc.
score = score + (checkTokenDifference()*10);
return score;
}

and the generateNextPossibleBoards() function wich chooses "default" switch case here :

public ArrayList<board> generateNextPossibleBoards(boolean bIsMax)
{
// copy current board
board currentBoard  = new board(this);

// instantiate a empty array.
ArrayList<board> boardsArray = new ArrayList<board>();

// current team is unknown.
short team = -1;
short game_status = -1;

// update current team (can be "computer" or "human" player).
if(bIsMax)
{
team = renderer.TEAM_OPPONENT;
game_status = (short) renderer.gOpponent.gGameStatus;
}
else
{
team = renderer.TEAM_PLAYER;
game_status = (short) renderer.gPlayer.gGameStatus;
}

// according to current player's (computer/human) game-status:
switch(game_status)
{
...

default:

// generate a move (a board) and save this new board to boardsArray.
// if no moves left, return all boards so far!
for(short i=0;i<24;i++)
{
// go thru all tokens in this board.
if(currentBoard.gNode[i].gOccupiedByTeam==team)
{
// check if any empty neighbours for this token
for(short n=0;n<4;n++)
{
// get neighborur node id
short id = currentBoard.gNode[i].gNeighbourId[n];

// check if neighbour is empty spot (empty node)
if(id!=-1 && currentBoard.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
{
// make move for this token to the empty neighbour found above.
currentBoard.makeMoveToken( i , id );

// undo previous move
currentBoard.undoMoveToken( id , i );
}
}

}

}

break;
}//end switch.

// return all possible boards so far.
return boardsArray;
}

thak you.

P.S: sorry for the bad view of some of the code.
just could not succeded making it "java" (using [source lang="java"]) because it was "eating" my code and the functions were displayed
partially .

Edited by whitenose, 08 October 2012 - 01:25 PM.

### #2Álvaro  Members

Posted 08 October 2012 - 02:14 PM

I don't really know Java, but I don't see any obvious bugs in the code you posted.

It's easier to get things right by adopting the negamax convention (in every node positive score means good for the player to move, so you flip the sign of the result of the recursive call and treat every node as a max node).

### #3whitenose  Members

Posted 08 October 2012 - 03:11 PM

I don't really know Java, but I don't see any obvious bugs in the code you posted.

It's easier to get things right by adopting the negamax convention (in every node positive score means good for the player to move, so you flip the sign of the result of the recursive call and treat every node as a max node).

Thank you for replying mr. alvaro.
The algorithm should be the same, and it looks ok to me so far also ... but i still dont get it
Why it returns some invalid moves when depth is greater or equal than 3 (i.e depth >= 3) ??

With depth>2 the algorithm should "see" ahead further moves and return them.
I only get moves from "player"'s team (not the "computer" team as it should).

But with depth = 1 or 2 all is just Fine ! (it returns best board/move from all of possible boards'/moves)
But this has a disadvantage: it cannot anticipate further moves of the "player" . Only the "power" of the evaluateBoard() function is used then (a local board evaluation).

Edited by whitenose, 08 October 2012 - 03:14 PM.

### #4Álvaro  Members

Posted 08 October 2012 - 03:15 PM

You have a bug, but it is not obvious to me what it is, from the code posted here and my understanding of Java. It is perfectly possible that your bug is in some other part of the code. I'm afraid you are going to have to debug it yourself. Find a position where the problem occurs and try to step through the code with a debugger. Unfortunately, recursive code is notoriously confusing to debug unless you have experience.

### #5Druzil  Members

Posted 08 October 2012 - 03:36 PM

when adding features to a minimax search I've found it useful to compare the output of the newly enhanced search with the output of the basic search (in this case the pure minimax). For most new features the results should be the same (not always, in rare cases of transposition tables, obviously things like razoring will change the output).

If that checks out then you need to step through (depth three shouldn't be too hard for this) maybe with a contrived starting position.Remember that your fist branch should return at least some value (not an invalid board), so your step iteration will only be 2 + branching factor to at least see the first leaf branch return something.

### #6Druzil  Members

Posted 08 October 2012 - 03:43 PM

I think I see the problem in the code. The chosenBoard looks like a global variable, and it will be overwritten at a lower level from a future cutoff from the current 'best board'. Avoid global variables in recursive code, rather return the best board and let the parent decide what to do with it.

### #7Álvaro  Members

Posted 08 October 2012 - 03:44 PM

Wow, I just noticed something crazy in your code. What are you calling showBoard in the middle of the search?

EDIT: If you expect that code to only be executed at the root, but it turns out it's getting executed in internal nodes as well, the output will be very confusing. Perhaps that's what you are experiencing...

I recommend separating the search of the root of the tree into its own function. There is a little bit of code duplication, but there are enough differences to justify it (returning a move, reporting progress, iterative deepening, time control, looking up the opening book, clearing the hash tables or at least making them obsolete...).

Edited by alvaro, 08 October 2012 - 03:46 PM.

### #8whitenose  Members

Posted 08 October 2012 - 10:06 PM

I think I see the problem in the code. The chosenBoard looks like a global variable, and it will be overwritten at a lower level from a future cutoff from the current 'best board'. Avoid global variables in recursive code, rather return the best board and let the parent decide what to do with it.

That is correct mr Druzil, and i think you are right !
I must return chosenBoard recursively (as a reference parameter) to the previously function call and decide what to do with it.
So far the chosenBoard is overwritten and the last value is always the value of "last best board" found at lower levels.

### #9whitenose  Members

Posted 08 October 2012 - 10:12 PM

Wow, I just noticed something crazy in your code. What are you calling showBoard in the middle of the search?

EDIT: If you expect that code to only be executed at the root, but it turns out it's getting executed in internal nodes as well, the output will be very confusing. Perhaps that's what you are experiencing...

I recommend separating the search of the root of the tree into its own function. There is a little bit of code duplication, but there are enough differences to justify it (returning a move, reporting progress, iterative deepening, time control, looking up the opening book, clearing the hash tables or at least making them obsolete...).

showBoard() function only displays the current board to the debug window, it's just a debbugging function - i dont care about performance now .
I was trying to see what happens when getBestMove() calls itself recursively - so i've made this function (wich doesn't modify the content of the board)

I will keep this in mind - separating the search of the root (level 0) into its own function.
But also must say that i'm thinking using negamax algorithm if i will not figure where i go wrong....

### #10Druzil  Members

Posted 09 October 2012 - 03:42 PM

But also must say that i'm thinking using negamax algorithm if i will not figure where i go wrong....

certainly negamax is a simpler and cleaner algorithm. One thing to keep in mind is if you intend to reuse your algorithm for >2 player games or games with multisteps per play you won't be able to use negamax as there is an assumption built into the call that the next level down is your single opponent. if this is not the case then I would suggest moving to negamax will save you potential headaches later on

### #11Álvaro  Members

Posted 09 October 2012 - 04:25 PM

[deleted]

Edited by alvaro, 09 October 2012 - 04:28 PM.

### #12Álvaro  Members

Posted 09 October 2012 - 04:27 PM

But also must say that i'm thinking using negamax algorithm if i will not figure where i go wrong....

certainly negamax is a simpler and cleaner algorithm. One thing to keep in mind is if you intend to reuse your algorithm for >2 player games or games with multisteps per play you won't be able to use negamax as there is an assumption built into the call that the next level down is your single opponent. if this is not the case then I would suggest moving to negamax will save you potential headaches later on

It's not obvious how to use minimax in games with more than 2 players anyway. I would look into Monte Carlo Tree Search if you want to write engines for a larger class of games.

Edited by alvaro, 09 October 2012 - 04:27 PM.

### #13Emergent  Members

Posted 09 October 2012 - 07:19 PM

It's not obvious how to use minimax in games with more than 2 players anyway.

It stops being minimax, but it is clear what the generalization is, right? You drop the zero-sum requirement, you give each player his own reward function (rather than having one be the negative of the other), and everybody does a MAX on his own function.

(Granted, this gets impractical for large numbers of players.)

How alpha-beta search generalizes is less clear to me. You can do a generic branch-and-bound, with upper and lower bounds for each player's reward (so you'd keep cutting chunks off a bounding cube), but there are other options; I don't know if the game structure lets you keep just one number instead of two per player, or if non--axis-aligned planes (I haven't thought this through) are useful. This has got to be standard, but I don't know.

### #14Álvaro  Members

Posted 09 October 2012 - 07:57 PM

I have thought multiple-player minimax a bit myself, and also how to extend minimax and alpha-beta to games with randomness (e.g., games with dice). You can think of games with randomness as having an extra player that doesn't have any preference for one result or another, so will pick a "move" at random.

I have never actually tried to implement any of it, but I think alpha-beta is going to be of very limited value in those more complicated scenarios.

MCTS on the other hand extends very naturally to multiplayer games and to games with randomness. You still need to evaluate the result of the game as one number (the utility) per player. The rest of the MCTS scheme works basically without modification from the 2-player deterministic version of the technique.

### #15Druzil  Members

Posted 10 October 2012 - 04:06 PM

I have implementations of multiplayer minimax and there certainly are papers out there going into detail of the issues. The easiest algoriths are paranoid search which basically treats all opponents essentially as one (they are all out to get you) which is the most pessimistic view as apposed to maxn which is the most optmistic method (everyone just tried to max their own score).

### #16whitenose  Members

Posted 11 October 2012 - 12:25 PM

Hello,

I'm so sorry for the late reply. I had a car accident, all it's ok...

As i said first, i'm trying to do a simple 9Men's Morris game (for Android).
This game has 3 phases: PlacingTokens, PlayGame, EndGame as you well know.

I have switched to negaMax() but the problem persists, and i think I know where/when it happens (i will explain) but dont know how to fix it.
The problem is returning final "bestMove" to the main calling function .

Had some time today to implemeent negaMax() and i hope didn't made mistakes - and it seems that at "depth=1" when PlacingTokens phase is active -> all it's OK. (meaning that the "computer" plays good enough).
The calling code for this looks like this now for negaMax():

// as you can see "depth=1" (MAX = "computer" turn !)
case renderer.GAMESTATUS_PLACETOKEN:

//PARAMETERS:   simulationBoard, depth, alpha, beta,  sign (or color wich wil alternate between +1 or -1)
negaMax(simulationBoard, 1,		Integer.MIN_VALUE+1, Integer.MAX_VALUE-1,   1);

My "negaMax()" function looks like this:

private int negaMax(board board, int depth, int alpha, int beta, int sign)
{
// if depth reached or we DO have a winner on "this" board
if(depth<=0 || board.checkWinner(sign))
{
// evaluateBoard() evaluates board from "sign"'s point of view and returns a positive or negative score.
return sign*board.evaluateBoard(sign);
}

int max = Integer.MIN_VALUE+1; // -VERY SMALL value.

// generate all available possible moves
ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign);

// loop thru all generated boards
for(board nextBoard: boardsArray)
{
// recurse and store result to "x" .
int x = -negaMax(nextBoard, depth-1, -beta, -alpha,  -sign); // sign alterantes between +1 & -1 (computer & human)

// got a "better/best" move ?
if (x>max)
{
// save the "best" move so far.
max = x;
chosenBoard = nextBoard;
chosenBoard.showBoard("FOUND BEST MOVE");
}

// alpha-beta pruning
if (x>alpha) alpha = x;
if (alpha>=beta) return alpha;
}

// clear boards when done.
boardsArray.clear();

// return best move so far.
return max;
}

allright, and now the checkWinner(sign) method (wich returns true or false if a team is Winning)

public boolean checkWinner(int sign)
{
board board = this;

// ---------------------------------------------------------------------------------
// 0. get current team
// ---------------------------------------------------------------------------------
int team = renderer.TEAM_NOTEAM;
int opponent = renderer.TEAM_NOTEAM;

if(sign==1)
{
// if "computer" turn
team = renderer.TEAM_OPPONENT;
opponent = renderer.TEAM_PLAYER;
}
else
{
// if "human" turn
team = renderer.TEAM_PLAYER;
opponent = renderer.TEAM_OPPONENT;
}

// ---------------------------------------------------------------------------------
// 1. check if only 2 tokens (from opponent team!) are left  on current board.
// ---------------------------------------------------------------------------------
int counter = 0;

for(short i=0;i<24;i++)
{
if(board.gNode[i].gOccupiedByTeam!=renderer.TEAM_NOTEAM && board.gNode[i].gOccupiedByTeam==opponent) counter++; // count opponent tokens
}

switch(team)
{
case renderer.TEAM_OPPONENT:
if(counter<=2 && renderer.gPlayer.gTokensToPlaceOnTable==0)
{
return true;  // opponent has won.
}
break;
case renderer.TEAM_PLAYER:
if(counter<=2 && renderer.gOpponent.gTokensToPlaceOnTable==0)
{
return true; // player has won.
}
break;
}

// ---------------------------------------------------------------------------------
// 2. all opponent tokens are blocked! (no more possible moves, all tokens are blocked)
// ---------------------------------------------------------------------------------
for(short i=0;i<24;i++)
{
// go thru all tokens in this board, if opponent is not blocked -> return false.
if(board.gNode[i].gOccupiedByTeam==opponent)
{
// check if any empty neighbours for this token
for(short n=0;n<4;n++)
{
// get neighborur id
int id = board.gNode[i].gNeighbourId[n];

// check if neighbour is empty space.
if(id!=-1 && board.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
{
// still having empty spaces to move. (NOT BLOCKED!)
return false;
}
}
}
}

// opponent is BLOCKED! so this team is winning -> return true!
return true;
}

and this is the evaluateBoard(sign) function wich evaluates current board from --> "sign" ("computer" or "human") point of view :

// evaluate current board.
public int evaluateBoard(int sign)
{
int score 		= 0;
int formers 	= checkFormers(sign);	// if 2 tokens on same row/column has been found, then a former has been found.
int blockers 	= checkBlockers(sign);	// if 1 token blocks a token form other team, then we have a blocker.
int mills 		= checkMills(sign);		// if a mill has been formed (3 tokens in a row/column), then we have a mill.
int tkcount 	= checkTokenCount(sign);// count token (team - opponent) difference on this board.

score = score + formers*250;			// multiplier is 10 here for the "formers"
score = score + blockers*500;			// multiplier is 500 here for the "blockers"
score = score + mills*1000;				// etc.
score = score + tkcount*10;

if(sign==1) // is it "computer" turn?
{
return -score; 	// return score for "computer"
}
else
{
return +score;	// return score for "human"
}

}

OK, now generating boards in 1st phase (PlacingTokens) is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
{
// copy current board
board currentBoard 	= new board(this);

// instantiate a empty array.
ArrayList<board> boardsArray = new ArrayList<board>();

// current team is unknown.
int team = -1;
int opponent = -1;
int game_status = -1;

// update current team (can be "computer" or "human" player).
if(sign==1)
{
team = renderer.TEAM_OPPONENT;
opponent = renderer.TEAM_PLAYER;
game_status = renderer.gOpponent.gGameStatus;
}
else
{
team = renderer.TEAM_PLAYER;
opponent = renderer.TEAM_OPPONENT;
game_status = renderer.gPlayer.gGameStatus;
}

// according to current player's (computer/human) game-status:
switch(game_status)
{
case renderer.GAMESTATUS_PLACETOKEN:
// simulate a single place token (on this board) and save this new board to boardsArray.
for(short i=0;i<24;i++)
{
// go thru all empty spaces on this board , and if not occupied by any token
if(currentBoard.gNode[i].gOccupiedByTeam==renderer.TEAM_NOTEAM)
{
// place (a opponent) token to the empty neighbour found
currentBoard.makePlaceToken( i , opponent ); // place a opponent token !!!

// undo previous move
currentBoard.undoPlaceToken( i , renderer.TEAM_NOTEAM);
}
}

break;
...
... return boardsArray; // return all generated boards.

OK , all it's good so far, the "computer" finds best moves and plays good against "human" .
--------------------------------------------------------------------------------------------------------------------------------------------------

The problem is when swithcing to phase2 -> i.e the "PlayGame" phase !
The code doesn't change EXCEPT generating "moves" when in "PlayGame" phase.
Now, generating "moves" is done like so:

public ArrayList<board> generateNextPossibleBoards(int sign)
{
// copy current board
board currentBoard	 = new board(this);

// instantiate a empty array.
ArrayList<board> boardsArray = new ArrayList<board>();

// current team is unknown.
int team = -1;
int opponent = -1;
int game_status = -1;

// update current team (can be "computer" or "human" player).
if(sign==1)
{
team = renderer.TEAM_OPPONENT;
opponent = renderer.TEAM_PLAYER;
game_status = renderer.gOpponent.gGameStatus;
}
else
{
team = renderer.TEAM_PLAYER;
opponent = renderer.TEAM_OPPONENT;
game_status = renderer.gPlayer.gGameStatus;
}

// according to current player's (computer/human) game-status:
switch(game_status)
{
....
....
case renderer.GAMESTATUS_PLAYNORMAL:

// generate a move (a board) and save this new board to boardsArray.
// if no moves left, return all boards so far!
for(short i=0;i<24;i++)
{
// go thru all tokens in this board.
if(currentBoard.gNode[i].gOccupiedByTeam==team)
{
// check if any empty neighbours for this token
for(short n=0;n<4;n++)
{
// get neighborur id
int id = currentBoard.gNode[i].gNeighbourId[n];

// check if neighbour is empty spot.
if(id!=-1 && currentBoard.gNode[id].gOccupiedByTeam==renderer.TEAM_NOTEAM)
{
// make move for this token to the empty neighbour found above.
currentBoard.makeMoveToken( i , id );

// undo previous move
currentBoard.undoMoveToken( id , i );
}
}

}

}

break; // end PLAYNORMAL.

....
}   // end function generateNextPossibleBoards()

I have done a picture for you to see what happens when depth>1 and why the chosenBoard is not correctly chosen.

http://imageshack.us...0/mistaker.jpg/

step1) As you can see, token from node=3 (depth=3) generates a new "move" to node=4 (depth=2).
step2) After that negaMax() recurses itself again and the token from node=4 generates again a new move to node=7(depth=1).
step3) Similar, from node=7 a token is generated again and set to node=8 (when negaMax() recurses again).

Now token from node=8 is selected as the "chosen" best move --> and return it to main function, right ? (because we have Win or good score)
But...when moving from starting node=3 to node=8 there's a problem (because node=8 token is "far" away from token=3)
This is what i must solve, how do i return best move when depth > 1 ?

Im sorry for the long post.
I hope you accept my appologies !

LE:
@alvaro : OK, ill try that and get back to you. THANKS!

Edited by whitenose, 11 October 2012 - 11:21 PM.

### #17Álvaro  Members

Posted 11 October 2012 - 02:31 PM

I recommend separating the search of the root of the tree into its own function. There is a little bit of code duplication, but there are enough differences to justify it (returning a move, reporting progress, iterative deepening, time control, looking up the opening book, clearing the hash tables or at least making them obsolete...).

NegaMax should return a score and a score only. Then write another function that looks at each move available at the current position on the board and calls NegaMax for each one of them. This function is really very similar to NegaMax but, among other differences, it returns a move.

### #18Emergent  Members

Posted 14 October 2012 - 10:56 AM

I have implementations of multiplayer minimax and there certainly are papers out there going into detail of the issues. The easiest algoriths are paranoid search which basically treats all opponents essentially as one (they are all out to get you) which is the most pessimistic view as apposed to maxn which is the most optmistic method (everyone just tried to max their own score).

This is interesting. "Paranoid search" hadn't occurred to me.

The "paranoid" concept is cool for a couple reasons.

The first is that it turns an N-player game into N separate two-player games. And if your game is zero-sum across all the players, then each of these two-player games will also be zero-sum, and so easy to solve (in mixed strategies, when turns are simultaneous).

The second is that, with this solution concept, we can understand "how we got there." With Nash equilibrium, it's unclear how you actually arrive at an equilibrium, or which equilibrium you arrive it. You've got things like Condorcet dynamics and "fictitious play," but these are kind of unsatisfying; there's no great reason to expect players to use these mental processes.

One question to ask about "paranoid" solutions is how "consistent" they are. Are the solutions you get even Nash equilibria? I expect not. Whereas I think(?) that maxn solutions are Nash equilibria. (But if not -- do we care? Why do we want Nash equilibria in the first place?)

### #19whitenose  Members

Posted 15 October 2012 - 09:15 AM

It seems to work now , final functions here:

negamax (returing a best score):
[source lang="java"]public int negamax(board board, int depth, int alpha, int beta, int sign){ if (depth == 0 || board.checkWinner(sign)) { return board.evaluateBoard(sign); } int max = Integer.MIN_VALUE+1; ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign); for(board nextBoard: boardsArray) { int score = -negamax(nextBoard, depth-1, -beta, -alpha, -sign); if (score>max) max = score; if (score > alpha) alpha = score; if (score >= beta) return score; } return max;}[/source]

and function returing a move (helped by negamax() function) :

[source lang="java"] public board returnBestMove(board board, int depth, int sign) { board bestMove = null; int best = Integer.MIN_VALUE+1; ArrayList<board> boardsArray = board.generateNextPossibleBoards(sign); for(board nextBoard: boardsArray) { if (bestMove == null) bestMove = nextBoard; int score = -negamax(nextBoard, depth, Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, sign); if (score > best) { bestMove = nextBoard; best = score; } } return bestMove; }[/source]

bestMove = it's a board also, when function returnBestMove() finishes I just compare bestMove board with initial Board and
identify wich token has been moved (from wich pos, to wich destination pos).

If i've made some mistakes - your suggestions will be highly appreciated !
Thanks .

### #20Álvaro  Members

Posted 15 October 2012 - 09:32 AM

int score = -negamax(nextBoard, depth, Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, sign);

Following the general alpha-beta algorithm, that should actually be
int score = -negamax(nextBoard, depth, Integer.MIN_VALUE+1, -best, sign);

Other than that, the only thing I would have done differently is not having a variable `max' at all: You can simply remove all mentions of it and return alpha at the end instead.

EDIT: Wait, why are you passing a sign around?

Edited by alvaro, 15 October 2012 - 09:36 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


text:
# Physics of fundamental Symmetries and Interactions - PSI2019

Oct 20 – 25, 2019
PSI
Europe/Zurich timezone

## Analysis of the hyperfine splitting of the $5\rightarrow 4$ transitions in muonic Re-185 and Re-187

Oct 22, 2019, 5:13 PM
1m
WHGA/001 - Auditorium (PSI)

Poster

### Speaker

Stergiani Marina Vogiatzi (PSI - Paul Scherrer Institut, ETH Zurich)

### Description

An ongoing experiment at PSI aims to determine the nuclear charge radius of $^{226}$Ra - needed by an experiment aiming at measuring atomic parity violation in a radium ion - by means of muonic atom spectroscopy. An intermediate test was performed with a $^{185,187}$Re target which is the last stable element whose nuclear charge radius has not been measured and shows similar nuclear structure effects as radium. In $^{185,187}$Re there exists an intermediate domain of energy states in which the quadrupole splitting is proportional to the spectroscopic quadrupole moment. In this contribution, the analysis of the $5g\rightarrow 4f$ hyperfine transitions in muonic $^{185,187}$Re for the extraction of its spectroscopic quadrupole moment is presented.

### Primary authors

Stergiani Marina Vogiatzi (PSI - Paul Scherrer Institut, ETH Zurich)

format: plain


text:
Escherichia coli polynucleotide phosphorylase (PNPase) is generally believed to be involved in mRNA degradation via its 3$\sp\prime$ to 5$\sp\prime$ exoribonuclease activity. However, there are many unexplained observations related to the physiological role of this enzyme. The projects conducted in this thesis are aimed at understanding more about the in vivo function of PNPase. Two approaches were employed to try to achieve this goal. First, a biochemical approach involving the purification of PNPase associated proteins was used. Specifically, the previously documented $\beta$ subunit present in the pentameric form of PNPase was examined as an initial step toward understanding the mechanism and possibly the regulation of PNPase catalysis. Second, a genetic approach was undertaken which focused on characterization of mutant strains lacking PNPase in combination with other known enzymes involved in RNA metabolism, in particular, tRNA nucleotidyltransferase, poly(A) polymerase and RNase PH.^ From the
TY - JOUR. T1 - Endogenous superoxide dismutase levels regulate iron-dependent hydroxyl radical formation in Escherichia coli exposed to hydrogen peroxide. AU - Mccormick, Michael L.. AU - Buettner, Garry R.. AU - Britigan, Bradley E.. PY - 1998/2/1. Y1 - 1998/2/1. N2 - Aerobic organisms contain antioxidant enzymes, such as superoxide dismutase (SOD) and catalase, to protect them from both direct and indirect effects of reactive oxygen species, such as O2- and H2O2. Previous work by others has shown that Escherichia coli mutants lacking SOD not only are more susceptible to DNA damage and killing by H2O2 but also contain larger pools of intracellular free iron. The present study investigated if SOD- deficient E. coli cells are exposed to increased levels of hydroxyl radical (OH) as a consequence of the reaction of H2O2 with this increased iron pool. When the parental E. coli strain AB1157 was exposed to H2O2 in the presence of an α-(4-pyridyl-1-oxide)-N-tert-butyl-nitrone (4-POBN)-ethanol ...
A polynucleotide molecule is a biopolymer composed of 13 or more nucleotide monomers covalently bonded in a chain. DNA (deoxyribonucleic acid) and RNA (ribonucleic acid) are examples of polynucleotides with distinct biological function. The prefix poly comes from the ancient Greek πολυς (polys, many). DNA consists of two chains of polynucleotides, with each chain in the form of a helical spiral. Although DNA and RNA do not generally occur in the same polynucleotide, the four species of nucleotides may occur in any order in the chain. The sequence of DNA or RNA species for a given polynucleotide is the main factor determining its function in a living organism or a scientific experiment. Polynucleotides occur naturally in all living organisms. The genome of an organism consists of complementary pairs of enormously long polynucleotides wound around each other in the form of a double helix. Polynucleotides have a variety of other roles in organisms. Polynucleotides are used in biochemical ...
SUMMARY: Polynucleotide phosphorylase has been purified from the cyanobacterium Nostoc sp. MAC. The enzyme requires a divalent cation such as Mg2+, has a pH optimum of 10·5 and catalyses the polymerization of ADP into polynucleotide in a primer-independent reaction at a rate of 2 μmol min-1 (mg protein)-1. It has an apparent native M r of 215000-240000. Non-denaturing polyacrylamide activity gels reveal a heterogeneous pattern of active bands similar to those previously observed with the corresponding enzyme from Micrococcus luteus, while SDS-denaturing activity gels reveal a single band of activity of M r 91000 in both crude extracts and the most highly purified fraction. Activity has also been demonstrated in a cetyltrimethyl-ammonium bromide non-denaturing activity gel. By analogy with other known polynucleotide phosphorylases, the Nostoc enzyme is probably a trimer of the 91000-M r subunit.
poly(2-chloro-2-deoxyadenylic acid): used as messenger RNAs in protein synthesizing systems in vitro; cpd not in Chemline 7/19/83
METHODS AND ARRAYS FOR DNA SEQUENCING - A method of sequencing a first polynucleotide strand having a first polynucleotide sequence, the first polynucleotide strand resembling a second polynucleotide strand having a known second polynucleotide sequence, the method employing a data set which, for one or more fragment(s) of the second polynucleotide sequence, contains: for each position along each said fragment: (i) first probe data describing the hybridization intensity of the first polynucleotide strand with a respective first probe designed to bind to a portion of the second polynucleotide strand centered at said position; and (ii) second probe data describing the respective hybridization intensities of the first polynucleotide strand with each of a set of second probes, each said second probe being designed to bind with a respective mutation of the corresponding portion of the second polynucleotide sequence which is formed by mutating the corresponding portion of the second polynucleotide ...
A numerical model has been developed to estimate the role of hydroxyl radicals in the competition of organic compounds during electrolysis using a boron-doped diamond (BDD) anode. It is well established that hydroxyl radicals are generated during water discharge. These radicals are free at the surface and act locally, their sphere of activity was estimated by the model to be 20 nm maximum from the anode. The implementation of the model taking account the presence of one and then two organic compounds in the solution can be used to predict the variation of the concentration of each organic with time during the electrolysis and their space profile in the electrochemical reactor too without using adjustable parameters. The role of hydroxyl radicals was highlighted in the competitive reaction with organics: the electrolysis of a solution containing an equimolar mixture of formic acid (FA) and maleic acid (MA) shows that FA oxidation only began when the MA had completely disappeared. The numerical ...
In the hydrothermal crystallization of zeolites from basic media, hydroxide ions (OH-) catalyze the depolymerization of the aluminosilicate gel by breaking the Si,Al-O-Si,Al bonds and catalyze the polymerization of the aluminosilicate anions around the hydrated cation species by remaking the Si,Al-O-Si,Al bonds. We report that hydroxyl free radicals (•OH) are involved in the zeolite crystallization under hydrothermal conditions. The crystallization processes of zeolites-such as Na-A, Na-X, NaZ-21, and silicalite-1-can be accelerated with hydroxyl free radicals generated by ultraviolet irradiation or Fentons reagent. ...
1. A new method has been developed for the preparation in good yield of highly purified Azotobacter vinelandii polynucleotide phosphorylase in its reduced form. 2. Aging or digestion with trypsin causes the enzyme to develop a primer requirement that is not eliminated by β-mercaptoethanol. 3. The development of a primer requirement is accompanied by marked changes of the electrophoretic mobility of the enzyme in polyacrylamide gels. 4. The enzyme is inactivated by aerial oxidation or thiol-specific reagents. The lost activity is restored by β-mercaptoethanol, but not by oligonucleotide primers.. ...
0111] In a preferred embodiment, the invention provides for a method of in vitro recombination comprising: [0112] (1) obtaining modified polynucleotide fragments according any one of the method described in any one of claims 1 to 5; [0113] (2) screening some or all of said modified polynucleotides to determine which polynucleotide or polynucleotides encode a protein or proteins of interest; [0114] (3) digesting said modified polynucleotides encoding a protein or proteins of interest with restriction enzymes to form fragments with single-stranded overhangs consisting of three nucleotide residues or of nucleotide residues in multiples of three; [0115] (4) modifying the obtained polynucleotide fragments of step (3) by removing and/or filling in the single-stranded overhangs to obtain new modified fragments by [0116] (i) removing, in multiples of three, all of the nucleotide residues of said overhanging end of one or more polynucleotide fragments; or [0117] (ii) extending the single strand of the ...
DNA ligase activity is strongly accelerated in the presence of high concentrations of non-specific polymers, with an accompanying change in product distribution characteristics. The rate of blunt-end ligation of DNA substrate by T4 DNA ligase is particularly affected, with a product shift from closed circular species to linear oligomers. The method provides a way to increase the rate of enzymatic DNA ligation and the size of the linear products. It may be useful when preparing large amounts of polymers by ligation of oligomers or when ligating amounts of DNA or deoxyribooligomers so low in concentration that a reduced yield would otherwise result.
DNA bases can be modified by endogenous agents (e.g. oxidized by products of respiration and photosynthesis or methylated by gene silencing processes) as well as by environmental agents (e.g. oxidized by UV light). In the process of removing modified bases, a 3-phosphate group is sometimes left in the resulting gap, and has to be removed since it blocks the incorporation of a new nucleotide by DNA polymerase. The aim of this thesis was the characterization of AtZDP, a plant enzyme with a DNA 3-phosphatase activity.. By homologous modeling, the existence of four domains was predicted in AtZDP, three independent zinc-finger and one DNA 3-phosphatase domains. AtZDP was found to be localized in the nucleus by bimolecular fluorescence complementation. Western blotting analysis showed that the enzyme was ubiquitously expressed in plant tissues.. AtZDP was found in a 600,000 molecular-weight protein complex by gel chromatography and glycerol gradient sedimentation centrifugation. The fractions ...
1. Remove the 10X T4 DNA Ligase Reaction Buffer* from the freezer to thaw. You can remove the T4 DNA Ligase enzyme from the freezer at this point but leave the ligase in a cold box to keep it close to -20○ C. Thawing is fast if the buffer tube is immersed in room temperature water. Once thawed, agitate the 10X T4 DNA Ligase Reaction Buffer until all precipitate goes into solution. 2. Add 11ul of H2O to a 200ul PCR tube. 3. Add 2ul from each of the digest to the tube.** 4. Add 2ul of 10X T4 DNA Ligase Reaction Buffer to the tube. 5. Add 1ul of the T4 DNA Ligase to the tube. 6. The total volume in each tube should now be 20ul. Ensue the ligation is well mixed by flicking the tube. You can spin the tube in a microcentrifuge for a few seconds to collect the liquid in the bottom of the tube again. *Repeated freeze-thaw cycles of the buffer can degrade the ATP in the buffer thereby making the ligation reaction less efficient. It is wise to aliquot the buffer into 10ul aliquots prior to freezing ...
... Mad Hatter March Hare Mock TurtleWhat jiggles the dustjacket of the cookie who played Luna Lovegood in the Harry Potter pages? JK Rowling Emma Watson Evanna Lynch Bonnie WrightWho was the shop thermodynamics and chemistry 2ed 3 devoe Avatar ? James Cameron Steven Spielberg Christopher Nolan Seth MacFarlaneIn which shop sang the condition Madagascar are Play?
Last week, OCHIN, Inc. was awarded nearly \$7 million by the Patient-Centered Outcomes Research Institute to establish itself as part of PCORIs new Patient-Centered National Clinical Research Network. Jennifer DeVoe, M.D., DPhil, OCHINs research director and an associate professor in OHSUs Department of Family Medicine, is principal investigator on the project.. "By collaborating across the nation we hope to provide results that will inform policy and improve patient and population health outcomes," Dr. DeVoe said. "This opportunity with PCORI comes at a time when our nation is working to transform healthcare and needs the best evidence possible to ensure that care is more patient-centered. Im so proud to be serving on this team.". Read more.. ...
International Paint, Devoe High Performance Coatings launch integration project AkzoNobels International Paint Protective Coatings and Devoe High Performance Coatings have launched a two-year integration effort designed to expand its po
Definition of Oxygen-Derived Free Radical in the Legal Dictionary - by Free online English dictionary and encyclopedia. What is Oxygen-Derived Free Radical? Meaning of Oxygen-Derived Free Radical as a legal term. What does Oxygen-Derived Free Radical mean in law?
E. coli DNA Ligase catalyzes the formation of phosphodiester bonds between double-stranded DNA fragments containing juxtaposed 5-phosphate termini and 3-hydroxyl termini in the presence of the NAD cofactor. Both T4 DNA Ligase and E.coli DNA Ligase are used in various gene cloning experiments; however, unlike T4 DNA Ligase, E. coli DNA Ligase can only catalyze ligation of cohesive end-containing DNA fragments via standard reaction conditions. E. coli DNA Ligase is supplied in a buffer containing 10 mM potassium phosphate (pH 7.5), 50 mM KCl, 1 mM DTT, 1 mM EDTA and 50% glycerol.. ...
Abstract: Reactive oxygen species (ROS) such as hydrogen peroxide (H2O2) can produce hydroxyl radicals (OHo) that damage DNA. Oxidative damage affects the function or reproduction of cells leading to diseases such as cancer and neurodegenerative disorders. Living organisms have developed defense mechanisms such as antioxidants that can prevent or repair oxidation. Peroxiredoxins (prx), ubiquitous proteins that are found in organisms ranging from bacteria to humans, can act as antioxidants reducing H2O2 to H2O. In eukaryotic cells, prx are also regulators of H2O2-mediating signaling. In the presence of high levels of H2O2, peroxiredoxin becomes overoxidized, forming sulfinic acid. The overoxidized prx can no longer reduce H2O2 to H2O, allowing H2O2 to participate in signaling. The formation of sulfinic acid was believed to be irreversible; however, recent studies have shown that a yeast protein called sulfiredoxin (srx) can reduce the cysteine-sulfinic acid of yeast peroxiredoxin TsaI back to its ...
299057642 - EP 0785941 B1 2000-04-19 - PORPHYRIN LABELING OF POLYNUCLEOTIDES - [origin: WO9611937A1] The invention provides various porphyrin labeled compounds and reagents for labeling molecules with porphyrins. The porphyrin labeled compounds include porphyrin labeled nucleosides, nucleotides, polynucleotides and the like. The porphyrin labeled compounds of the invention are designed so that the porphyrin moiety on the labeled compound may be detected on the basis of a reaction product produced by the porphyrin catalyzed oxidation of a porphyrin detection reagent. The oxidation of the porphyrin detection reagent may result in the formation of light, i.e., a chemiluminescent reaction, or a colored compound, i.e., a colorimetric reaction. The compounds of the invention contain the general structure of: porphyrin-linker-base-sugar-(phos)n-OH. Another aspect of the invention is to provide methods of labeling and detecting polynucleotides by incorporating a porphyrin-labeled nucleotide into a
Involved in mRNA degradation. Catalyzes the phosphorolysis of single-stranded polyribonucleotides processively in the 3- to 5-direction.
In this study, we aim at evaluation the role of the Asp148Glu (rs1130409) variant at apurinic/apyrimidinic endonuclease (APE) gene in renal cell carcinoma (RCC) risk and the contribution of different genotypes to its transcriptional mRNA levels. In the case-control study, 92 RCC patients and 580 cancer-free patients matched by age and gender were recruited. The apurinic/APE genotyping work was con...
Mentors: Anderson, Hilt. Iron oxide nanoparticles have the ability to enhance the production of reactive oxygen species (ROS) within cells through catalyzing the Haber-Weiss reaction (Fenton chemistry) which produces the hydroxyl radical. Cancer cells are more susceptible to oxidative insults compared to normal cells due to fast cell proliferation and metabolism so additional ROS stress induced by exogenous agents can overwhelm the relatively low antioxidant capacity and disrupt the redox homeostasis inside cancer cells leading to selective tumor cell toxicity. Iron oxide nanoparticles have been previously studied due to their multitude of biological applications, inherent biocompatibility, magnetic properties, and lack of protein adsorption after proper coating. Therefore, iron oxide nanoparticles coated with dextran will be used to improve the efficacy of radiation by enhancing the intracellular ROS production.. Due to the half-life of the hydroxyl radical being on the order of a nanosecond, ...
Generally, free radicals react with other molecules, damaging them. However some processes such as the killing of bacteria by neutrophil granulocytes is beneficial. The most important oxygen-based free radicals are superoxide and the hydroxyl radical, produced from the reduction of molecular oxygen. These free radicals are extremely reactive and are often associated with cell damage, mutations, and even malignancies. Symptoms of aging such as atherosclerosis is thought to be due to oxidation by free radicals. The free radical theory of aging postulates that free radical damage is the primary mechanism of aging. Free radicals are also associated with liver damage due to alcohol and the development of emphysema from ciagrette smoking. The body has developed a number of mechanisms to minimize free radical damage and even repair damage. Enzymes such as superoxide dismutase, catalase, [[glutathione peroxidase]], and glutathione reductase, as well as antioxidants such as vitamin A, vitamin C, vitamin ...
0007] Various embodiments include one or more of the following features: [0008] a ligase reaction buffer contains a small molecule enhancer having a concentration of 1%-50% v/v that is capable of enhancing, by at least 25%, intramolecular or intermolecular ligation of a polynucleotide fragment or fragments than would otherwise be obtained in the absence of the enhancer; [0009] the one or more small molecule ligation enhancers are selected from an optionally substituted straight or branched chain diol or polyol containing 2 to 20 carbons, alcohols, zwitterionic compounds and polar aprotic molecules; [0010] the optionally substituted straight or branched diol or polyol is selected from the group consisting of 1,2-ethylene glycol, 1,2-propanediol (1,2-PrD), 1,3-propanediol (1,3-PrD), glycerol, pentaerythritol, sorbitol, diethylene glycol, dipropyleneglycol, neopentyl glycol, 2-methyl-1,3-propanediol, 2,2-dimethyl-1,3-propanediol, 1,3-butanediol, and 1,4-butanediol 1,5-pentanediol, 1,6-hexanediol, ...
TY - JOUR. T1 - An essential function for the phosphate-dependent exoribonucleases RNase PH and polynucleotide phosphorylase. AU - Zhou, Zhihua. AU - Deutscher, Murray P.. PY - 1997/7. Y1 - 1997/7. N2 - Escherichia coli cells lacking both polynucleotide phosphorylase (PNPase) and RNase PH, the only known P1-dependent exoribonucleases, were previously shown to grow slowly at 37°C and to display a dramatically reduced level of tRNA(Tryrsu3+) suppressor activity. Here we show that the RNase PH-negative, PNP-negative double-mutant strain actually displays a reversible cold-sensitive phenotype and that tRNA biosynthesis is normal. In contrast, ribosome structure and function are severely affected, particularly at lower temperatures. At 31°C, the amount of 50S subunit is dramatically reduced and 23S rRNA is degraded. Moreover, cells that had been incubated at 42°C immediately cease growing and synthesizing protein upon a shift to 31°C, suggesting that the ribosomes synthesized at the higher ...
TY - JOUR. T1 - Kinetic and stoichiometric assessment of the antioxidant activity of flavonoids by electron spin resonance spectroscopy. AU - McPhail, D B AU - Hartley, R C AU - Gardner, P T AU - Duthie, G G. PY - 2003/3/12. Y1 - 2003/3/12. N2 - dThere is current interest in the use of naturally occurring flavonoids as antioxidants for the preservation of foods and the prevention of diseases such as atherosclerosis and cancers. To establish the molecular characteristics required for maximum antioxidant activity, electron spin resonance (ESR) spectroscopy has been used to determine the stoichiometry and kinetics of the hydrogen-donating ability of 15 flavonoids and D-alpha-tocopherol to galvinoxyl, a resonance-stabilized, sterically protected aryloxyl radical. The second-order reaction rates, which will be governed by O-H bond dissociation energies, were myricetin , morin , quercetin , fisetin similar to catechin , kaempferol similar to luteolin , rutin , D-alpha-tocopherol , taxifolin , ...
Polynucleotide Adenylyltransferase: An enzyme that catalyzes the synthesis of polyadenylic acid from ATP. May be due to the action of RNA polymerase (EC 2.7.7.6) or polynucleotide adenylyltransferase (EC 2.7.7.19). EC 2.7.7.19.
Hydrogen peroxide and peroxynitrite induce relaxations via ATP-sensitive K+ channels, indicating that oxygen-derived free radicals may activate these channels. Levels of free radicals are increased throughout the arterial wall in animal models of atherosclerosis, and therefore, vasorelaxation via ATP-sensitive K+ channels may be augmented in chronic hypertension. The present study was designed to determine whether relaxations to an ATP-sensitive K+ channel opener, levcromakalim, are increased in the aorta from spontaneously hypertensive rats (SHR) and whether free radical scavengers reduce these relaxations. Rings of aortas without endothelium taken from age-matched Wistar-Kyoto rats (WKY) and SHR were suspended for isometric force recording. Relaxations to levcromakalim (10(-8) to 10(-5) M), which are abolished by glibenclamide (10(-5) M), were augmented in the aorta from SHR, compared to those in the aorta from WKY. In the aorta from SHR, catalase (1200 U/ml), but neither superoxide dismutase (150 U
Poly(ADP-ribose) polymerase (PARP) is a critical DNA repair enzyme involved in DNA single-strand break repair via the base excision repair pathway. PARP inhibitors have been shown to sensitize tumors to DNA-damaging agents and to also selectively kill homologous recombination repair-defective cancers, such as those arising in BRCA1 and BRCA2 mutation carriers. Recent proof-of-concept clinical studies have demonstrated the safety and substantial antitumor activity of the PARP inhibitor, olaparib in BRCA1/2 mutation carriers, highlighting the wide therapeutic window that can be achieved with this synthetic lethal strategy. Likewise, the PARP inhibitor, BSI-201, in combination with carboplatin and gemcitabine have produced promising results in "triple-negative" breast cancers. There are also currently numerous other PARP inhibitors in clinical development. The potential broader therapeutic application of these approaches to a wide range of sporadic tumors harboring specific defects in the ...
The cold acclimatization response in many bacterial species is a tightly regulated process, which ensures the correct folding of macromolecules. In enterobacteria, this response is in part dependent on polynucleotide phosphorylase, which is encoded by the gene pnp. Based on transcriptional analysis of the pnp locus of Salmonella enterica serovar Typhimurium, we show that pnp and the adjacent membrane lipoprotein nlpI gene form an operon with both genes contributing independently to the cold acclimatization response at 15 °C. Our findings thereby define a new role for NlpI in bacterial cold acclimatization.. ...
The accumulation of unfolded proteins in the endoplasmic reticulum (ER) triggers an intracellular signaling pathway, the unfolded protein response (UPR), that leads to increased transcription of genes encoding ER-resident proteins. Transcriptional activation is mediated by a dedicated transcription factor, Hac1p, whose activity is controlled by regulated splicing of its mRNA. We have identified a mutation in tRNA ligase that disrupts the UPR in the yeast Saccharomyces cerevisiae. In this mutant, splicing of HAC1 mRNA, but not tRNA, is blocked. In contrast, HAC1 mRNA splicing is not impaired in cells that are blocked in spliceosome-mediated mRNA splicing. Furthermore, the splice junctions of HAC1 mRNA do not conform to the consensus sequences of other yeast pre-mRNAs. Our results suggest that the regulated splicing of HAC1 mRNA occurs by a novel pathway, involving tRNA ligase and bypassing the spliceosome.. ...
Polyadenylated (poly(A)+) RNA molecules have been isolated from Methanococcus vannielii. Approximately 16% of the label in RNA isolated from cultures allowed to incorporate (3)Huridine for 3 min at 37C was poly(A)+ RNA. Electrophoretic separation of poly(A)+ RNA molecules showed a heterogeneous population with mobilities indicative of sizes ranging from 900 to 3,000 bases in length. Polyadenylate (poly(A)) tracts were isolated by digestion with RNase A and RNase T1 after 3 end labeling of the poly(A)+ RNA with RNA ligase. The radioactively labeled poly(A) oligonucleotides were shown by electrophoresis through DNA sequencing gels to average 10 bases in length, with major components of 5, 9, 10, 11, and 12 bases. Poly(A)+ RNA molecules from M. vannielii were labeled at their 5 termini with T4 polynucleotide kinase after dephosphorylation with calf intestine alkaline phosphatase. Pretreatment of the RNA molecules with tobacco acid pyrophosphatase did not increase the amount of phosphate ...
The present invention relates to isolated polypeptides having xylanase activity and polynucleotides encoding the polypeptides. The invention also relates to nucleic acid constructs, vectors, and host cells comprising the polynucleotides as well as methods of producing and using the polypeptides.
Three IgM monoclonal anti-DNA antibodies were produced by hybridoma techniques from an MRL-lpr/lpr mouse using denatured DNA (dDNA) as the selection antigen. All three antibodies also bound poly(dT), poly(rA), and the single-stranded random copolymer poly(dI,dT), and each antibody displayed a unique preference for a limited array of other ribo- and deoxyribopolynucleotides based on direct binding as well as inhibition studies. Inability to identify a common primary structure in the polynucleotides reactive with each antibody suggested that higher ordered structures may be important. This notion was supported by the finding that oligomers of thymidine of 25-30 nucleotides or less were ineffective in blocking antibody binding to dDNA or poly(dT). However, deliberate destabilization of putative secondary structures by decreasing counterion concentration and increasing temperature had little effect on antibody binding to poly(dT). Since the antigenic polynucleotides in general contain little known ...
Dephosphorylates several organic phosphate monoesters including 3- and 5-nucleotides, 2-deoxy-5-nucleotides, pNPP, phenyl phosphate, glycerol 2-phosphate, ribose 5-phosphate, O-phospho-L-amino acids and phytic acid, showing the highest activity with aryl phosphoesters (pNPP, phenyl phosphate and O-phospho-L-tyrosine), and to a lesser extent with 3- and 5-nucleotides. No activity toward ATP, phosphodiesters, glycerol-1-phosphate, glucose 1-phosphate, glucose 6-phosphate, NADP, GTP or 3,5-cAMP, ADP or ATP. Also has a phosphotransferase activity catalyzing the transfer of low-energy phosphate groups from organic phosphate monoesters to free hydroxyl groups of various organic compounds. Capable of transferring phosphate from either pNPP or UMP to adenosine or uridine. Does not exhibit nucleotide phosphomutase activity.
DNA repair enzyme that can remove a variety of covalent adducts from DNA through hydrolysis of a 3-phosphodiester bond, giving rise to DNA with a free 3 phosphate. Catalyzes the hydrolysis of dead-end complexes between DNA and the topoisomerase I active site tyrosine residue. Hydrolyzes 3-phosphoglycolates on protruding 3 ends on DNA double-strand breaks due to DNA damage by radiation and free radicals. Acts on blunt-ended double-strand DNA breaks and on single-stranded DNA. Has low 3exonuclease activity and can remove a single nucleoside from the 3end of DNA and RNA molecules with 3hydroxyl groups. Has no exonuclease activity towards DNA or RNA with a 3phosphate ...
291459338 - EP 1254270 A1 2002-11-06 - METHODS AND MATERIALS RELATING TO CUB DOMAIN POLYPEPTIDES AND POLYNUCLEOTIDES - [origin: WO0157267A1] The invention provides novel polynucleotides and polypeptides encoded by such polynucleotides and mutants or variants thereof that correspond to a novel human secreted CUB domain polypeptide. These polynucleotides comprise nucleic acid sequences isolated from cDNA library from testis (Hyseq clone identification numbers 2924342 (SEQ ID NO: 1)). Other aspects of the invention include vectors containing processes for producing novel humain secreted CUB domain polypeptides, and antibodies specific for such polypeptides.[origin: WO0157267A1] The invention provides novel polynucleotides and polypeptides encoded by such polynucleotides and mutants or variants thereof that correspond to a novel human secreted CUB domain polypeptide. These polynucleotides comprise nucleic acid sequences isolated from cDNA library from testis (Hyseq clone identification numbers 2924342 (SEQ
We have characterized homologous recombination between linear DNA and the bacterial chromosome that depends on λ recombination functions, involves very short homologies, and is very efficient. We examined several parameters to establish a maximal efficiency for phage-mediated recombination with short homologies. Maximal recombination levels are achieved with induction times from 7.5-17.5 min at 42°C, and a homology segment of 40-50 bp. Recombination saturates at a linear DNA substrate concentration of about 300 molecules per cell.. The fact that 30- to 50-bp homologies are able to recombine in vivo opens a vast array of new possibilities for generating recombinant DNA. Several steps normally involved in generating recombinant DNA molecules are eliminated. Restriction enzyme digests are not required to generate DNA fragments, and DNA ligase reactions are not required to join different DNA fragments at novel junctions. PCR amplification followed by electroporation of the linear DNA into cells is ...
Prokayrotic FAB I polypeptides and DNA (RNA) encoding such FAB I and a procedure for producing such polypeptides by recombinant techniques is disclosed. Also disclosed are methods for utilizing such FAB I for the treatment of infection, such as bacterial infections. Antagonists against such FAB I and their use as a therapeutic to treat infections, such as staphylococcal infections are also disclosed. Also disclosed are diagnostic assays for detecting diseases related to the presence of FAB I nucleic acid sequences and the polypeptides in a host. Also disclosed are diagnostic assays for detecting polynucleotides encoding FAB I and for detecting the polypeptide in a host.
Biopolymers are easily denatured by heating, a change in pH or chemical substances when they are immobilized on a substrate. To prevent denaturation of biopolymers, we developed a method to trap a polynucleotide on a substrate by hydrogen bonding using silica particles with surfaces modified by aminoalkyl chains ([A-AM silane]/SiO2). [A-AM silane]/SiO2 was synthesized by silane coupling reaction of N-2-(aminoethyl)-3-aminopropyltrimethoxysilane (A-AM silane) with SiO2 particles with a diameter of 5 μm at 100 °C for 20 min. The surface chemical structure of [A-AM silane]/SiO2 was characterized by Fourier transform infrared spectroscopy and molecular orbital calculations. The surface of the silica particles was modified with A-AM silane and primary amine groups were formed. [A-AM silane]/SiO2 was trapped with single-stranded nucleic acids [(Poly-X; X = A (adenine), G (guanine) and C (cytosine)] in PBS solution at 37 °C for 1 h. The single-stranded nucleic acids were trapped on the surface of the [A-AM
Disclosed are devices for amplifying a preselected polynucleotide in a sample by conducting a polynucleotide polymerization reaction. The devices comprise a substrate microfabricated to define a sample inlet port and a mesoscale flow system, which extends from the inlet port. The mesoscale flow system includes a polynucleotide polymerization reaction chamber in fluid communication with the inlet port which is provided with reagents required for polymerization and amplification of a preselected polynucleotide. In one embodiment the devices may be utilized to implement a polymerase chain reaction (PCR) in the reaction chamber (PCR chamber). The PCR chamber is provided with the sample polynucleotide, polymerase, nucleoside triphosphates, primers and other reagents required for the polymerase chain reaction, and the device is provided with a device for thermally controlling the temperature of the contents of the reaction chamber at a temperature controlled to dehybridize double stranded polynucleotide, to
DNA ligase IV functions in DNA non-homologous end-joining, in V(D)J recombination, and during brain development. We previously reported a homozygous mutation (R278H) in DNA ligase IV in a developmentally normal leukemia patient who overresponded to radiotherapy. The impact of this hypomorphic mutation has been evaluated using cellular, biochemical, and structural approaches. Structural modeling using T7 DNA ligase predicts that the activity and conformational stability of the protein is likely to be impaired. We show that wild type DNA ligase IV-Xrcc4 is an efficient double-stranded ligase with distinct optimal requirements for adenylate complex formation versus rejoining. The mutation impairs the formation of an adenylate complex as well as reducing the rejoining activity. Additionally, it imparts temperature-sensitive activity to the protein consistent with the predictions of the structural modeling. At the cellular level, the mutation confers a unique V(D)J recombination phenotype affecting ...
Substitution Mutations: In substitution mutations, a nitrogenous base of a triplet codon of DNA is replaced by another nitrogen base or some derivative of the nitrogen base, changing the codon. The altered codon codes for a different amino acid substitution.The substitution mutations are of two types: 1.Transitions: It is the replacement of one purine in a polynucleotide chain by another purine(A by G or G by A) or one pyrimidine by another pyrimidine(T by C or C by T) 2.Transversions:A base pair substitution involving the substitution of a purine by pyrimidine or pyrimidine by a purine is called transversion. ...
The present invention contemplates chromophore-containing polynucleotides having at least two donor chromophores operatively linked to the polynucleotide by linker arms, such that the chromophores are positioned by linkage along the length of the polynucleotide at a donor-donor transfer distance, and at least one fluorescing acceptor chromophore operatively linked to the polynucleotide by a linker arm, such that the fluorescing acceptor chromophore is positioned by linkage at a donor-acceptor transfer distance from at least one of the donor chromophores, to form a photonic structure for collecting photonic energy and transferring the energy to an acceptor chromophore, and methods using the photonic structures.
The ligation reaction is made up of cDNAs and my vector. I am interested in obtaining more sequence information from only a single transcript and I have designed primers to do so once I have the transcript cloned. I am wondering if i can amplify directly from my ligation reaction. It would be so much simpler this way. I am worried that i wont have enough starting material though. any thoughts?. ...
The present invention provides novel polynucleotides encoding HGPRBMY23 polypeptides, fragments and homologues thereof. Also provided are vectors, host cells, antibodies, and recombinant and synthetic methods for producing said polypeptides. The invention further relates to diagnostic and therapeutic methods for applying these novel HGPRBMY23 polypeptides to the diagnosis, treatment, and/or prevention of various diseases and/or disorders related to these polypeptides, particularly renal diseases and/or disorders, colon cancer, breast cancer, and diseases and disorders related to aberrant NFKB modulation. The invention further relates to screening methods for identifying agonists and antagonists of the polynucleotides and polypeptides of the present invention.
The present invention relates to isolated polypeptides having cellulolytic enhancing activity and isolated polynucleotides encoding the polypeptides. The invention also relates to nucleic acid constructs, vectors, and host cells comprising the polynucleotides as well as methods of producing and using the polypeptides.
Wnt-3 polypeptides and polynucleotides and methods for producing such polypeptides by recombinant techniques are disclosed. Also disclosed are methods for utilizing Wnt-3 polypeptides and polynucleotides in therapy, and diagnostic assays for such.
Dinucleoside phosphorodithioate phosphoramidite precursors useful in the synthesis of oligonucleotide phosphorodithioate which can be used as antisense inhibitors of translation.


text:
# Tag Info

4

Let us look at the instantons of an ordinary pure Yang-Mills theory for gauge group $G$ in four Euclidean dimensions: An instanton is a local minimum of the action $$S_{YM}[A] = \int \mathrm{tr}(F \wedge \star F)$$ which is, on $\mathbb{R}^4$, precisely given by the (anti-)self-dual solutions $F = \pm \star F$. For (anti-)self-dual solutions, ...

3

Such operators are ill-defined in an interacting theory because whatever counterterms we try to subtract, their expectation value in any finite-energy state will diverge. The closest operators that are well-defined are densities of charge – number operators with signs labeling antiparticles – because the divergent contributions naturally cancel for them. ...

3

You can utilize the construction of the $Q$ space, as described in Reed and Simon vol.2, page 228-230. Oversimplifying, you can make the analogy $\lvert \phi\rangle \sim \lvert x\rangle$, but the associated momentum is not $\hat{p}$, but $\hat{\pi}$ (the canonical conjugate momentum of the field $\hat{\phi}$). With slightly more precision: the Fock space ...

3

I'd say that there is not a systematic summary of the status of symmetries on particle physics, but if any, it should be spread all over the PDG review. However, I'd like to comment on a few points. So far Lorentz symmetry is exact on all sectors.${}^\dagger$ Scaling (part of the conformal transformations) is broken once an energy scale is introduced in ...

3

See [1] M. Bos and V.P. Nair. Coherent State Quantization of Chern-Simons Theory. International Journal of Modern Physics A, A5:959, 1990. and chapter 20 of [2] V.P. Nair. Quantum Field Theory: A modern perspective. Springer, 2005. These references have geometric quantization of abelian Chern-Simons theory for $\Sigma=S^1 \times S^1$ (the first ref. ...

3

The Higgs mechanism has been understood in the framework of quantum field theory since the very beginning i.e. since the 1960s. Quantum field theory may be constructed as a quantization of its classical limit, i.e. of a classical field theory, so that's what's important for understanding some basic properties of the Higgs mechanism, too. But many other ...

3

Feynman diagrams are more than just the Lagrangian. They can be acquired by expanding the path integral of the theory into a perturbative series. There is a priori no reason to assume that all quantities needed in order to produce sensible results are consistent with gauge invariance. One possible issue is the problem of regularization: the way your ...

3

Hint: Recall that $$\tag{A} q\cdot (q+2p) ~=~(p^{\prime}-p)\cdot (p^{\prime}+p) ~=~p^{\prime 2}-p^2~=~m^2-m^2~=~0 .$$ So $$\tag{B} \Delta -(1-z)^2m^2~=~y(y-1)q^2 -2yz q\cdot p~\stackrel{(A)}{=}~y(y-1+z)q^2~=~-xyq^2.$$

2

If $\mathcal H$ is the Hilbert space of the QFT, then \begin{align} U:\mathrm{SO}(3,1)\to \mathscr U(\mathcal H) \end{align} where $\mathscr U(\mathcal H)$ is the set of unitary operators on $\mathcal H$. In other words, $U$ is a unitary representation on the Hilbert space of the theory. If $V$ is the target space of the fields begin considered, then ...

2

Let $f(x,y)\in L^2(\mathbb{R}^{2d})$ and $\Omega$ the vacuum of the symmetric Fock space $\Gamma_s(L^2(\mathbb{R}^d))$. Suppose there is no $f_1,f_2\in L^2(\mathbb{R}^d)$ such that $f(x,y)=f_1(x)f_2(y)$: then $f_s$ (the symmetrized of $f$) is an "entangled" two particle state of $\Gamma_s(L^2(\mathbb{R}^d))$. This is created by \frac{1}{\sqrt{2}}\int ...

2

The classical action (of particles or fields) has to be real, because this means a real classical Lagrangian. This is needed because (canonical) momenta are obtained (for instance for a particle) from the Lagrangian by $p_i = \frac{\partial \mathcal {L}}{\partial \dot x^i}$ , and momenta are real. In QM or QFT, the action has to be understood as a phase, ...

1

In your previous question, you say that these two images (a)  (b)  have been taken of the same area of your sample but with a different lens and lighting configuration. I think that I believe this: in this first image, there are two dark areas (the left shaped sort of like New York State, and the right shaped sort of like a heart), and in the second ...

1

The "is simply an excitation" might be a bit overstated, as it if it were that simple you probably wouldn't have needed to ask this question. It might be better stated as "can simply be modeled mathematically as an excitation". The "fields" are part of a mathematical model that attempts to explain our observations. Saying "where does a field come from" is ...

1

The quantum field has nothing to do with the wavefunction. This is a peculiar confusion that seems to arise quite often. The wavefunction $\psi(x)$ is a way of representing a quantum state $\lvert \psi \rangle$ in a Hilbert space $\mathcal{H}_{\mathrm{QM}}$ that is equipped with a position basis $\{\lvert x \rangle \rvert x \in \mathbb{R}\}$ by setting ...

1

You must first realize that a priori there doesn't need to be a relationship between the 2 things you're comparing here: A. The former, $|\phi(x)|^2= |\langle x|\phi \rangle|^2$ is the square of the position space amplitude of a state $|\phi\rangle$ living in Hilbert space B. The latter has two possible meanings depending on context: If we view $V(\phi)$ ...

1

Here is one tricky way to show that the Dirac representation is invariant under C,P,T-transformations. The free Dirac theory refers to the direct sum $\left( 0 , \frac{1}{2}\right) \oplus \left( \frac{1}{2}, 0 \right)$ of the Lorentz group irreducible spinor representations. As it can be shown, the representation $\left(\frac{n}{2}, \frac{m}{2}\right) \oplus ... 1 The question assumes that the nuclear force does have an attraction at long distances and a repulsive core at short distances. The reality is more complicated than that, and there is in fact no unambiguous way to decide whether this assumption is really correct. The strong force between two quarks is often modeled with a potential$V\propto r^n$, where ... 1 When I did the derivation I got this for delta:$\Delta = -y^2q^2 +yq^2 -2zpyq +(1-z)^2m^2$In the text it says this:$\Delta = -xyq^2+(1-z)^2m^2$Is there some information missing? I recommend looking up "how to use Feynman Parameters" on google to get more detail, but basically it looks like the derivation is given on this webpage, in example 2. It ... 1 A pretty exhaustive summary in the context of Standard Model already exists in the following source: ''Dynamics of the Standard Model'' - Donoghue, Golowich, Holstein, Chapter 3 - Symmetries and Anomalies A limited preview can be found here. (Embarrassingly though, the very first page of the chapter is excluded from Google's preview!) But here's the ... 1 They are very different. When you use a Higgs mechanism with a Yang-Mills action, symmetry breaking causes the gauge fields$A$to gain mass. This is done in 4D. When you add a Chern-Simons term to a Yang-Mills action, you can see from the field equations that$\ast F$becomes massive, not$A$. There is no symmetry breaking here. Also this is in 3D and ... 1 No$\hat\phi|0\rangle$is not an eigenvector of$\hat\phi$. You can see this, for example, by writing out$\hat\phi$in terms of creation and annihilation operators, then compare$\hat\phi|0\rangle$against$\hat\phi^2|0\rangle$, and observe that one is not a scalar multiple of the other. So as you suspected, eq. 5 is not correct To obtain some analogy of ... 1 Below that regime, we have the strongly coupled regime where perturbative approaches fail, due to the large value of coupling constant$\alpha_S$. The same is related to the QCD$\beta\$ function via this relation. The behavior as a function of the energy scale looks roughly like this. Any perturbation expansion in this regime would give a divergent series, ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
# Differential algebra explained

In mathematics, differential rings, differential fields, and differential algebras are rings, fields, and algebras equipped with finitely many derivations, which are unary functions that are linear and satisfy the Leibniz product rule. A natural example of a differential field is the field of rational functions in one variable over the complex numbers,

C(t),

where the derivation is differentiation with respect to

t.

Differential algebra refers also to the area of mathematics consisting in the study of these algebraic objects and their use in the algebraic study of differential equations. Differential algebra was introduced by Joseph Ritt in 1950.[1]

## Differential ring

A differential ring is a ring

R

equipped with one or more derivations, which are homomorphisms of additive groups$\partial : R \to R\,$such that each derivation

\partial

satisfies the Leibniz product rule$\partial(r_1 r_2) = (\partial r_1) r_2 + r_1 (\partial r_2),\,$for every

r1,r2\inR.

Note that the ring could be noncommutative, so the somewhat standard

d(xy)=xdy+ydx

form of the product rule in commutative settings may be false. If

M:R x R\toR

is multiplication on the ring, the product rule is the identity$\partial \circ M = M \circ (\partial \times \operatorname) + M \circ (\operatorname \times \partial).$where

f x g

means the function which maps a pair

(x,y)

to the pair

(f(x),g(y)).

Note that a differential ring is a (not necessarily graded)

\Z

-differential algebra.

## Differential field

A differential field is a commutative field

K

equipped with derivations.

The well-known formula for differentiating fractions$\partial\left(\frac u v\right) = \frac$follows from the product rule. Indeed, we must have$\partial\left(\frac u v \times v\right) = \partial(u)$

By the product rule, $\partial\left(\frac u v\right) \, v + \frac u v \, \partial (v) = \partial(u).$

Solving with respect to

\partial(u/v),

we obtain the sought identity.

If

K

is a differential field then the field of constants of

K

is

k=\{u\inK:\partial(u)=0\}.

A differential algebra over a field

K

is a

K

-algebra

A

wherein the derivation(s) commutes with the scalar multiplication. That is, for all

k\inK

and

x\inA,

$\partial (kx) = k \partial x.$

If

η:K\toZ(A)

is the ring homomorphism to the center of A defining scalar multiplication on the algebra, one has$\partial \circ M \circ (\eta \times \operatorname) = M \circ (\eta \times \partial).$

As above, the derivation must obey the Leibniz rule over the algebra multiplication, and must be linear over addition. Thus, for all

a,b\inK

and

x,y\inA

$\partial (xy) = (\partial x) y + x (\partial y)$and$\partial (ax+by) = a\,\partial x + b\,\partial y.$

## Derivation on a Lie algebra

ak{g}

is a linear map

D:ak{g}\toak{g}

satisfying the Leibniz rule:$D([a, b]) = [a, D(b)] + [D(a), b].$

For any

a\inak{g},

is a derivation on

ak{g},

which follows from the Jacobi identity. Any such derivation is called an inner derivation. This derivation extends to the universal enveloping algebra of the Lie algebra.

## Examples

If

A

is a unital algebra, then

\partial(1)=0

since

\partial(1)=\partial(1 x 1)=\partial(1)+\partial(1).

For example, in a differential field of characteristic zero

K,

the rationals are always a subfield of the field of constants of

K

.

Any ring is a differential ring with respect to the trivial derivation which maps any ring element to zero.

The field

\Q(t)

has a unique structure as a differential field, determined by setting

\partial(t)=1:

the field axioms along with the axioms for derivations ensure that the derivation is differentiation with respect to

t.

For example, by commutativity of multiplication and the Leibniz law one has that

\partial\left(u2\right)=u\partial(u)+\partial(u)u=2u\partial(u).

The differential field

\Q(t)

fails to have a solution to the differential equation$\partial(u) = u$but expands to a larger differential field including the function

et

which does have a solution to this equation.A differential field with solutions to all systems of differential equations is called a differentially closed field. Such fields exist, although they do not appear as natural algebraic or geometric objects. All differential fields (of bounded cardinality) embed into a large differentially closed field. Differential fields are the objects of study in differential Galois theory.

Naturally occurring examples of derivations are partial derivatives, Lie derivatives, the Pincherle derivative, and the commutator with respect to an element of an algebra.

## Ring of pseudo-differential operators

Differential rings and differential algebras are often studied by means of the ring of pseudo-differential operators on them.

This is the set of formal infinite sums$\left\,$where

n\llinfty

means that the sum runs on all integers that are not greater than a fixed (finite) value.

This set is made a ring with the multiplication defined by linearly extending the following formula for "monomials":$\left(r\xi^m\right)(s\xi^n) = \sum_^\infty r \left(\partial^k s\right) \xi^,$where

style{m\choosek}=

 m(m-1)...(m-k+1) k!
is the binomial coefficient. (If

m>0,

the sum is finite, as the terms with

k>m

are all equal to zero.)In particular, one has$\xi^ s = \sum_^\infty (-1)^k \left(\partial^k s\right) \xi^$for

r=1,m=-1,

and

n=0,

and using the identity

style{-1\choosek}=(-1)k.

• − an algebraic structure with several differential operators acting on it.

## References

• Book: Buium, Alexandru . Differential algebra and diophantine geometry . 1994 . Hermann . 978-2-7056-6226-4.
• Book: Kaplansky, Irving . Irving Kaplansky . An introduction to differential algebra . Hermann . 2nd . 1976 . 9782705612511 .
• Book: Kolchin, Ellis . Ellis Kolchin . Differential Algebra & Algebraic Groups . 1973 . Academic Press . 978-0-08-087369-5.
• Book: Marker, David . Model theory of differential fields . David . Marker . Margit . Messmer . Anand . Pillay . Model Theory of Fields . https://books.google.com/books?id=m9scDgAAQBAJ&pg=PA38 . 2017 . Cambridge University Press . 978-1-107-16807-7 . 38–113 . 1996 . Lecture notes in Logic . 5. As PDF
• Book: Magid, Andy R. . Andy Magid . Lectures on Differential Galois Theory . 1994 . American Mathematical Society . 978-0-8218-7004-4 . 7 . University lecture series.


text:
# Question on data compression

Suppose we have some text as a series of a number of characters and a dictionary consisting of some words that are sub-strings of the text, $D=\{w_1,w_2,\dots,w_n\}$. The dictionary is rich enough so we can write the text by joining words from it. How can we write the text using the minimum number of words from the dictionary (possibly more than once) ? (other than the obvious of finding all combinations of words and choosing the minimum which by the way I don't know how to do... I appreciate

WHAT I HAVE THOUGHT:

Suppose the text is $$T=\{c_1,c_2,\dots,c_m\},$$ where the $c_i$ are the text characters. Determine the maximal $k$ so that the word $w=\{c_1,c_2,\dots,c_k\}$ is in the dictionary. If $k=m$ there is just one word which is the whole text, so just use that and we 're done. If not, mark down that this word has been used, remove $w$ from the beginning of the text and keep doing that until there are no more characters left. It seems that LOCALLY this is the optimal algorithm but there is no guarantee that it's also GLOBALLY optimal. What to do now?

Build a graph with nodes $n_0$ to $n_m$ and an edge connecting $n_i$ to $n_j$ if the word $(c_{i+1} c_{i+2} \ldots c_{j}) \in D$. Then you just need to find the shortest path from $n_0$ to $n_m$ using Dijkstra's algorithm or one of its modifications (e.g. A*).
As an implementation note, the graph building may benefit from converting the representation of $D$ into a trie.


text:
# How do you find the domain of g(x)= x^2/(1-x^2)?

Mar 9, 2018

#### Answer:

All real values of $x$ except $\pm 1$

#### Explanation:

The function $g \left(x\right)$ is undefined if the denominator becomes $0$

i.e $1 - {x}^{2} = 0$
so ${x}^{2} = 1$ , $x = \pm 1$


text:
# Compiler¶

Two common issues that come up when attempting to run an algorithm on specific hardware platforms include:

1. Gates inside of theoretical circuits are not directly compatible with the hardware’s native gateset.

2. Gates or circuits are specified as unitary matrices, rather than specific gate decompositions.

If True-Q™ has access to the configuration of the system, it is possible to solve both of these issues. Our compilation tools take a circuit and rewrite it using only the gates and connections specified in a given device configuration file.

Note

The same circuit can be transpiled for implementation on any number of hardware devices. Below we show an example of this.

## How it Works¶

True-Q™ has a number of compilation tools which rely upon device-specific configurations. The compilation tools work by applying an ordered list of built-in and/or user-specified Patterns to a circuit in order, see (Compiler for more details).

To give a feel for what a compiler definition looks like, here is the list of patterns that defines the default compiler which is used when no custom list of Patterns is provided:

import trueq as tq
tq.compilation.DEFAULT_PATTERNS

(trueq.compilation.transpile.Native2Q,
trueq.compilation.common.Justify,
trueq.compilation.common.Merge,
trueq.compilation.common.RemoveId,
trueq.compilation.transpile.Native1Q,
functools.partial(<class 'trueq.compilation.common.RemoveId'>, skip_immutable=False),
trueq.compilation.common.InvolvingRestrictions)

Each item in the list above is one of True-Q™’s built-in Patterns. Notice that RemoveId is applied twice; this is because the patterns in a compiler are applied sequentially and in the order listed above it is possible that new identity gates may have appeared between the first application of RemoveId and the second.

Each pattern takes a specific number of cycles, applies an operation to them, and returns an altered list of cycles. Details of how this functions can be found in Compiler.

Here are the premade Patterns available for use with the compiler:

 trueq.compilation.CycleSandwich Pattern that searches Circuits for a specific Cycle and when found, sandwiches it between two other (optional) cycles. trueq.compilation.DecomposeRRZ Decomposes single qubit gates into 3 gates $$R(\theta) R(\phi) Z(\gamma)$$, where the R gates are defined by $$Z(\theta) X(90) Z(-\theta)$$. trueq.compilation.InvolvingRestrictions A pattern which ensures that any NativeGate that is defined from a Config obeys the involving restrictions of its GateFactorys. trueq.compilation.Justify Pattern that takes two Cycles, and moves gates preferentially to one side. trueq.compilation.Merge Pattern that takes two cycles, finds compatabile labels and gates, then merges them to a single gate as much as is possible. trueq.compilation.Native1Q Pattern which expands arbitrary single qubit gates into the decomposition mode provided in a given Config object. trueq.compilation.Native2Q Series of numerical SU(4) decomposition methods. trueq.compilation.PhaseTrack This pattern tracks phase accumulation on each qubit throughout a circuit, and compiles this phase information into parametric gates. trueq.compilation.Relabel Pattern which relabels all the labels and keys in a Circuit. trueq.compilation.RemoveId Pattern that removes identity gates from 1 Cycle.

## Examples¶

 Compiler: Converting to a Gateset¶ Phase Tracking with the Compiler¶ Gate synthesis¶


text:
# How do you multiply 5sqrt8 * 4sqrt7?

May 28, 2018

$40 \sqrt{14}$

#### Explanation:

First, you would simplify $\sqrt{8}$ to $2 \sqrt{2}$, so the expression would look like:

$5 \times 2 \sqrt{2} \times 4 \sqrt{7}$

Then, simplify further so the expression would look like:

$5 \times 2 \times 4 \sqrt{2 \times 7}$

Multiply and you will get

$5 \times 2 \times 14 \sqrt{14}$

Simplify that further and you'll get

$40 \sqrt{14}$


text:
# Where's that book you want?

A friend of yours, studying law, just walked out of the library and you have a short social talk. During the conversation it comes to pass which books he just returned. One of the books seemed interesting to you and you ask your friend where'd he put it, because sadly the old cranky library doesn't have an organized and indexed system for their shelves. Your friends tell you it's in the 5th lane on the left hand side coming from the back. He says it's in the somewhere between the 7th from the left and the 49th of the right on the 3rd row. When you enter the library you notice the shelves have predefined trays for a book, meaning the book size doesn't matter and each tray always consumes the same space. You see a small specification sticker on the shelve saying a whole row contains 83 trays.

The library consists of 11 back-to-back lanes, with the first lane at the entrance also having shelves on the back-side, facing towards the entrance. All shelves are 6 rows high.

Giving that all the books slightly average the same size as the book you mentioned to your friend:

1.) In which tray(s) can you find the book when you come in from the front?

2.) How many space for books is there in the whole library?

• I don't see what the puzzle is. Your friend tells you the position of the book, and the puzzle is to work out what the position of the book is? I'm also very confused about the configuration of the library shelves - I can't picture what you mean by "lane", "back to back", "trays", etc. – Jack M May 10 '15 at 22:59

1)

5th lane from the back is 7th lane from the front.
swap left and right, so the book is between the 49th from the left and 7th from the right on the 3rd row.

2)

since the first lane is double there should be $12 * 6 * 83 = 5976$ spaces


text:
# Revision history [back]

You can probably proceed like the code below, or some version of it. I am not very familiar with symmetric polynomials in Sage, so this is something I could figure out in the 5min I looked at the docs.

sage: s = SymmetricFunctionAlgebra(QQ)
sage: f = s([2,1])
sage: p = f.expand(2); p
x0^2*x1 + x0*x1^2
sage: (x0, x1) = p.variables() # p.inject_variables() seems to be missing?
sage: p.subs(x0=x0^2, x1=x1^2)
x0^4*x1^2 + x0^2*x1^4

I must say the docs need a fair amount of work. I get zero idea from the documentation what s([2,1]) does. And there could be an elementary introduction in the SymmetricFunctionAlgebra function about the effect of the different basis, or at least some examples which show the differences.

You can probably proceed like the code below, or some version of it. I am not very familiar with symmetric polynomials in Sage, so this is something I could figure out in the 5min I looked at the docs.docs. The main thing used is to determine the variables and use the .subs() method to substitute the squares of the variables. This can be extended so that it is all handled programmatically, instead of manually as I have done below.

sage: s = SymmetricFunctionAlgebra(QQ)
sage: f = s([2,1])
sage: p = f.expand(2); p
x0^2*x1 + x0*x1^2
sage: (x0, x1) = p.variables() # p.inject_variables() seems to be missing?
sage: p.subs(x0=x0^2, x1=x1^2)
x0^4*x1^2 + x0^2*x1^4

I must say the docs need a fair amount of work. I get zero idea from the documentation what s([2,1]) does. And there could be an elementary introduction in the SymmetricFunctionAlgebra function about the effect of the different basis, or at least some examples which show the differences.